Machines

题意 有 \(N\) 张卡片，第 \(i\) 张卡片正面印着一个数 \(A_i\)，反面印着一个数 \(B_i\)。一开始所有数正面朝上。 有 \(M\) 种操作，第 \(i\) 种操作表示为： \(50\%\) 的概率将卡片 \(X_i\) 翻转，否则将 \(Y_i\) 翻转。 求一个集合 \(S ......

Problem StatementThere are $N$ cards numbered $1$ through $N$. Each face of a card has an integer written on it; card $i$ has $A_i$ on its front and $ ......

## 5.1 Linear classification 考虑如下问题：$\mathbb{R} ^N$ 上的 $\cal X$ 服从某个未知分布 $\cal D$，并由目标函数 $f:\cal X\to Y$ 映射到 $\{-1, +1\}$。根据采样 $S=(({\bf x} _1, y _1), ......

一种很新的折半/根号分治。 ~~手玩一下~~可以证明一个机器集合 $S$ 的期望，先把 $S$ 中 $x=y$ 的机器对应的卡片翻好面，对于剩下的机器，如果一张卡片被至少一个机器覆盖过（即 $x=i$ 或 $y=i$），那么它的期望是 $\dfrac{a+b}{2}$，否则就是 $a$。 首先把 $ ......