Fair AI/ML 5 PROP in Non-Centroid Clustering
Read the paper Proportional Fairness in Non-Centroid Clustering by Caragiannis et al. This paper was accepted in NeurIPS 2024! Introduction nnn points, kkk clusters C=(C1,⋯ ,Ck)C=(C_1,\cdots,C_k)C=(C1,⋯,Ck), distance metric ddd. kkk-means objective: ∑i=1k1∣Ci∣⋅∑x,y∈Cid(x,y)2\sum_{i=1}^k\frac{1}{|C_i|}\cdot\sum_{x,y\in C_i}d(x,y)^2∑i=1k∣Ci∣1⋅∑x,y∈Cid(x,y)2. Scenario in which there are no cluster centers. Question: Can we obtain PROP guarantee for non-centroid clustering? Do the algorithm ...
丹麦语 DU 3.3 9 Jobsøgning
Edison søger job krævende 苛求的 et par måneder 几个月 indtil 直到 vikariat -et, -er, -erne 临时职位 kvalifikation -en, -er, -erne 资格 rutinepræget -, …prægede 固定程序的，无脑的 utilfredsstillende 令人不满意的 afvekslende adv 交互，交替 udfordrende 有挑战的 allerførst -, -e 首先，第一 personlighed -en, -er, -erne 个性，性格 kompetence -n, -r, -rne 能力，权力，专长 overfladisk -, -e 皮毛的，浅层次的，表面的 nysgerrig -t, -e 好奇的 indadvendt -, - 内向的 udadvendt -, - 外向的 målrettet -, målrettede 坚定的，果断的 resultatorienteret 以结果为导向的 holdspiller -en, -e, -ne 团队成员 mene 认 ...
算法和计算复杂度 11 Probabilistic Checkable Proofs
Proof systems where a polynomial-time probabilistic verifier can spot-check a given written proof by inspecting a few randomly selected symbols of the proof. Cost: Introducing some error. 📖Definition 48 (PCP verifier). A (non-adaptive) PCP verifier VVV is a polynomial-time probabilistic Turing machine equipped with an additional random access proof tape together with a write-only query tape and a read-only answer tape. Two additional states: query state and continue state. The symbols on the pr ...
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 ...
