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 ...
Efficient ReliK 2 Possible Parallelization Idea
Some ideas from Maximilian. Recap Pseudo Code Look at the Pseudo code again: Input: KG K:⟨E,R,F⟩\mathcal K:\langle\mathcal E,\mathcal R,\mathcal F\rangleK:⟨E,R,F⟩, triple xhrt=(h,r,t)∈Fx_{hrt}=(h,r,t)\in\mathcal Fxhrt=(h,r,t)∈F, embedding score function s:E×R×E→Rs:\mathcal E\times\mathcal R\times\mathcal E\to\mathbb Rs:E×R×E→R, sample size k∈Nk\in\mathbb Nk∈N Output: ReliKLB(xhrt)ReliK_{LB}(x_{hrt})ReliKLB(xhrt) or ReliKApx(xhrt)ReliK_{Apx}(x_{hrt})ReliKApx(xhrt) SH←S_H\getsSH← sample k ...
丹麦语 DU 3.3 4 Højskoler
气死了！完整的笔记被覆盖掉了😡 Nyt ordforråd om højskoler og fællesskaber højskole “休闲中学”，丹麦专有的特殊的学校，没有考试和入学要求，通常是文理中学毕业的学生 gap year 的去处。 fællesskab -et, -er, -erne 社区 halvanden 一又二分之一 skynde -r, -de, -t 匆忙 netværk et, - eller -er, -ene eller -erne 网络 emne -t, -r, -rne 主题 hverken … eller … 既不……也不…… adgangskrav 入学要求 idræt -ten, -ter, -terne 体育 区分 tror, synes, tænke tror：表示相信或猜测，基于不确定的事实或推测。 synes：表示个人的主观看法或感受，通常用于表达意见。 tænke：表示思考的过程，可以是计划、反思或想念。 bl.a. 例如 vælge -r, valgte, valgt 选择 Sætningskløvninger ...
Efficient ReliK 1 Paper Reading
This is one of the two projects I undertake in 24 Fall semester, which is related to data mining. Supervisor: Assoc. Prof. Davide Mottin, PhD Student Maximilian Egger. Generally speaking, they have already developed a new method, ReliK, for measuring knowledge graph embeddings, but they want to speed it up with GPUs. So my project is focusing on this. I wish to speed them up with some tolerance on small accuracy loss. I need to first get familiar with the paper, ReliK: A Reliability Measure for ...