Fair AI/ML 4 Endeavor to Bridge Gap between 2 and 2.414
We dedicated to solve the open problem left by Greedy Capture: Is there an algorithm that has better PROP guarantee 2≤ρ≤1+22\le\rho\le1+\sqrt22≤ρ≤1+2? My Initial Immature Idea Do some fine-tuning on results of Greedy Capture. Pseudo code X←X\getsX← Greedy Capture(N,M,k)(\mathcal N,\mathcal M,k)(N,M,k) N←∅N\gets\emptyN←∅ // NNN denotes “free” data points while ∃\exist∃ 2-approximate Block Coalition Nbc←N_{bc}\getsNbc← all data points in that 2-approx Block Coalition Xbc←X_{bc}\getsXbc← all ...
丹麦语 DU 3.3 7-8 Arbejdspladskultur
有趣的表达： tisse i bukserne for at holde varmen 直译：在裤子里撒尿来保持温暖 意译：饮鸩止渴 Johanna, Manu og Anya skilte -r, -de, -t 吹嘘，炫耀，张贴 pinlig -t, -e 尴尬的 omvendt -, -e 相反 eks. I Indien er det lige omvendt. titel titlen, titler, titlerne 头衔 hierarki -et, -er, -erne 层次结构；阶层 almindelig -t, -e 常见的，普通的 tvivl -en 怀疑 tvivl om at + SÆTNING/NOGET/hv+SÆTNING komme i tvivl forventning -en, -er, -erne 期望 overholde -r, …holdt, …holdt 遵守 erklæring -en, -er, -erne 声明 = Erklärung er vant til = vænne sig til 习惯于 egentlig -t, -e ...
算法和计算复杂度 10 Interactive Proofs
Interactive Turing Machine 📖Definition 44 (interactive Turing machine). An interactive TM MMM is a probabilistic TM equipped also with a write-only query tape and a read-only answer tape, and has two new special states, a query state and a continue state. The symbols allowed on the query and answer tape are given by a communication alphabet Λ\LambdaΛ. When MMM enters the query state, the contents mmm of the query tape as a message mmm sent by MMM. We say that we send a reply rrr to mmm by perf ...
Fair AI/ML 3 PROP Fair Clustering Revisited
Read the paper Proportionally Fair Clustering Revisited by Micha et Shah. kkk cluster centers must be placed given nnn points in a metric space. The cost to each point is its distance to the nearest cluster center. This paper: Focus on the case where cluster centers can be placed anywhere in metric space. E.g. L2L^2L2 distance over Rt\mathbb R^tRt, the approximation ratio of greedy capture improves to 222. For L1,L∞L^1,L^\inftyL1,L∞ metric, the approximation ratio remains 1+21+\sqrt 21+2. The p ...
Fair AI/ML 2 PROP Fair Clustering
Read the paper Proportionally Fair Clustering by Chen et al. Abstract nnn points, kkk centers. Proportionality: any n/kn/kn/k points are entitled to form own cluster if there is another center that is closer in distance for all n/kn/kn/k points. Clustering with no justified complaints from any subset of agents. Tradeoff between proportional solutions and kkk-means objective. Introduction In centroid clustering, we want to partition data into kkk clusters by choosing kkk centers and then matchi ...
算法和计算复杂度 9 Circuit Lower Bounds
Parity function is not in AC0AC^0AC0. MAJ∉AC0MAJ\not\in AC^0MAJ∈AC0. NEXP⊈ACC0NEXP\not\subseteq ACC^0NEXP⊆ACC0. Some unknown proposition: whether NP⊆ACC0NP\subseteq ACC^0NP⊆ACC0. whether EXP⊆ACC0EXP\subseteq ACC^0EXP⊆ACC0. whether NEXP⊆TC0NEXP\subseteq TC^0NEXP⊆TC0. whether all languages in NEXPNEXPNEXP can be computed by depth 222 circuits consisting of weighted linear threshold gates. The Razborov-Smolensky Lower Bound The lower bounds for class AC0[pr]AC^0[p^r]AC0[pr], where pp ...
丹麦语 DU 3.3 6 Foreninger og klubber
spild af penge 浪费钱 terning -en, -er, -erne 骰子 slå med terningen 掷骰子 Det er din/min tur. 轮到你/我了 brik -ken, -ker, -kerne 棋子，标志，令牌，“token” træls 悲惨的 辨析 om/i + 一段时间 om tre uger 在三周内 i tre uger 三周（一段时间） 逻辑连接词 både … og … 可以连接大于等于两个主体，表示“都”的意思。 Eks. Søren har både køer, grise og heste. 索亨有牛、猪和马。 Søren både sover og spiser i sengen. Søren hører altid musik, både når han er hjemme, og når han er på arbejde. hverken … eller … 表示“既不……也不……”，可以连接大于等于两个主体。 Eks. Søren har hverken køer, grise eller h ...
Efficient ReliK 3 Parallel For Loop
This week, I am mainly working on parallelization of enumerating xh′r′t′x_{h'r't'}xh′r′t′: for u,v in nx.DiGraph(M).subgraph(subgraph).edges(). Target Code 1234567891011121314151617181920212223for subgraph in subgraphs: count = 0 sib_sum = 0 sib_sum_h = 0 sib_sum_t = 0 start_uv = timeit.default_timer() for u,v in nx.DiGraph(M).subgraph(subgraph).edges(): w, w1, w2 = heur(u, v, M, models, entity_to_id_map, relation_to_id_map, all_triples_set, full_graph, ...
丹麦语 DU 3.3 5 At beskrive
Ordforråd om højskoler sabbatår -et, -, -ene gap 年 valgfri -t, - eller -e 可选的 valgfri fag 选修科目 tilbyde -r, tilbød, tilbudt 提供 vælge -r, valgte, valgt 选择 Du skal selv vælge din fag på højskolen. at kunne tænke sig = at have lyst til 有兴趣做某事，想做某事 Jeg kunne tænke mig, at gå på en kreativ højskole. Infinitivkæder Hun vil begynde at lære at køre bil. ‘at lære’ er objekt for ‘begynde’ ‘at køre bil’ er objekt for ‘at lære’ Han har lovet at prøve at holde op med at ryge. ‘at prøve’ er objekt f ...
Fair AI/ML 1 Core-Stability Federated Learning
I will begin a new project work 24 Fall: FAIRNESS IN AI/ML THROUGH THE LENS OF SOCIAL CHOICE The basic outline is following Tutorial: Fairness in AI/ML via Social Choice by Evi Micha & Nisarg Shah in EC 2024. The first paper I have read in last semester, Fairness in Federated Learning via Core-Stability, which was one of the possible topics. Brief notes is here. I will try to understand some mathematical proof in this semester. Core-Stability Revisit the definition of Core-Stability: A pred ...
