Li Zhenghao🚴

原问题 一个DRMDP（s-rec）可以表示为： sup⁡π(⋅∣s)∈Δ(A) inf⁡Ps∑a∈Aπ(a∣s)EPs,a[R(s,a,S)+γv(S)]s.t. ∑a∈ADf(Ps,a∥P‾s,a)≤∣A∣ρPs,a∈Δ(S)for all a∈A\begin{align} \sup_{\pi(\cdot|s)\in\Delta(\mathcal{A})}~&\inf_{P_s}\sum_{a\in\mathcal{A}}\pi(a|s)\mathbb{E}_{P_{s,a}}\left[R(s,a,S)+\gamma v(S)\right]\\ {\rm s.t.}~ &\sum_{a\in\mathcal{A}}D_f(P_{s,a}\|\overline{P}_{s,a})\leq |\mathcal{A}|\rho\\ &P_{s,a}\in\Delta(\mathcal{S}) \quad\text{for all~} a \in...

复习用，后续再添加内容 convex set definition ∀x,y∈S⇒αx+(1−αy)∈S\forall x,y\in S\Rightarrow \alpha x+(1-\alpha y) \in S ∀x,y∈S⇒αx+(1−αy)∈S 一些凸集的例子 epi(f){\rm epi}(f)epi(f)是convex set epi(f):={(xa)∈Rn+1∣f(x)≤a}{\rm epi}(f):=\left.\left\{\begin{pmatrix}x\\a\end{pmatrix}\in\mathbb R^{n+1}\right|f(x)\leq a\right\} epi(f):={(xa​)∈Rn+1​f(x)≤a} 即f(x)上方的全部区域 凸集的交集是凸的，但是并集不一定 如果fff是凸函数，则∂f(x)\partial f(x)∂f(x)是凸集 proof 根据∂f\partial f∂f定义，有 f(y)≥f(x)+⟨u,y−x⟩f(y)≥f(x)+⟨v,y−x⟩\begin{gather*} f(y)\geq...

复习用，后续再添加内容 次梯度定义： ∂g(x)={u∈Rn∣g(y)≥g(x)+⟨u,y−x⟩}\partial g(x) =\{u\in\mathbb R^{n}|g(y)\geq g(x)+\langle u,y-x\rangle\} ∂g(x)={u∈Rn∣g(y)≥g(x)+⟨u,y−x⟩} 次梯度最优性条件 x∗=argmin⁡x∈Rng(x)⟺0∈g(x∗)x^*=\operatorname*{argmin}_{x\in\mathbb R^n}g(x)\Longleftrightarrow 0\in g(x^*) x∗=x∈Rnargmin​g(x)⟺0∈g(x∗) 邻近点算子 proxαg(y)=argmin⁡x∈Rn(12∥x−y∥22+αg(x)){\rm prox}_{\alpha g}(y) =\operatorname*{argmin}_{x\in\mathbb R^n} \left(\frac 12 \|x-y\|_2^2+\alpha...

Motivation Hadoop是一个比较基础的语言，需要一个高级语言 Hadoop每次map/map+reduce之后需要将数据存储到hdfs中，io开销过大 此外，spark还支持更多复杂的、多步骤的数据处理（如机器学习）以及实时流数据分析 RDD RDD，全称为Resilient Distributed Dataset（弹性分布式数据集），是Spark中的一个非常重要的概念。RDD具有以下几个关键特性： 不可变性（Immutability）：RDD是不可变的，一旦创建便不能更改。 分区（Partitioned）：RDD是分区的，数据存储在多个分区中以实现并行处理。 延迟计算（Lazy Evaluation）：RDD的转换操作是延迟执行的，只有当执行Action操作时，才会触发实际的计算。 依赖关系（Lineage）：Spark通过记录RDD的依赖关系的方式来跟踪其生成过程，当数据丢失时可以通过血统重新计算丢失的分区。 RDD是 Set of Partitions（分区集合） List of Dependencies on Parent RDDs：RDD...

从item-freq数据构建FP Tree 假设我们目前有如下数据，假设Threshold为3： 首先统计频率 筛选掉小于threshold的item，按照frequency倒序和alphabet顺序进行排序 根据该顺序重新对原数据进行排列 随后构建FP-tree。一开始只有一个root节点，然后根据节点到来的顺序，构建FP-tree，对于第一条数据，其结果如下： 对于后续的数据，如果前缀相同，则对于元素加1，如果不同，则分叉。最终如下： 我们需要一个Horizontal link来连接所有分支中的相同元素（如上图所示） FP-growth Algorithm 构建FP Tree 对于每个Item，构建conditional FP Tree，具体而言就是对于前缀为当前元素的所有序列构建FP Tree，这个conditional FP Tree以前缀元素作为根节点 如果conditional FP Tree不是只有一个分支，那么对于所有节点，继续构建conditional FP Tree，直到只有一个分支 根据所有的conditional FP...

Data Warehouse 考虑这样一系列视图（view），我们希望存储其中的若干个使得总cost相比于只存储top节点节约的最多。可以使用贪婪算法来处理。 具体而言，每一轮迭代中，对于每个节点，计算储存当前节点所带来的增益，选取增益最大的并进行存储。 ε\varepsilonε-deficient synopsis No False Negatives The difference between the estimated frequency and the true frequency is at most εN\varepsilon NεN. f−f~≤εNf-\tilde f\leq \varepsilon N f−f~​≤εN All items whose true frequencies less than (s−ε)N(s-\varepsilon)N(s−ε)N are classified as infrequent items in the algorithm output f~≤(s−ε)N→negative\tilde...

HITS 得到Authority score 和 hub score之后，有多种方式进行排名，如按authority score降序，按hub score 降序，等等。 Page Rank

不等式 sup inf 不等式 inf⁡A=−sup⁡(−A)\inf A = -\sup(-A) infA=−sup(−A) ∣sup⁡Af−sup⁡Ag∣≤sup⁡A∣f−g∣,∣inf⁡Af−inf⁡Ag∣≤sup⁡A∣f−g∣.\left|\sup_Af-\sup_Ag\right|\leq\sup_A|f-g|,\quad\left|\inf_Af-\inf_Ag\right|\leq\sup_A|f-g|. ​Asup​f−Asup​g​≤Asup​∣f−g∣,​Ainf​f−Ainf​g​≤Asup​∣f−g∣. 概率 Markov’s Inequality Markov’s inequality - Wikipedia Suppose XXX is a nonnegative random variable and a>0a>0a>0, then, P(X≥a)≤E[X]aP(X\geq a)\leq \frac{\mathbb E[X]}{a} P(X≥a)≤aE[X]​ Chernoff Bound Chernoff bound -...

基本概念 MapReduce MapReduce借用functional programming概念，map阶段将一部分data作为输入，通过map函数得到输出，在reduce阶段一步一步聚合Map阶段的输出。 [!NOTE] 这里ggg需要满足交换律（commutativity）和结合律（Associativity），否则输出顺序会影响结果。 具体而言， 在map阶段(k1,v1)→[⟨k2,v2⟩](k_1,v_1)\rightarrow [\langle k_2,v_2\rangle](k1​,v1​)→[⟨k2​,v2​⟩] 在reduce阶段(k2,[v2])→[⟨k3,v3⟩](k_2,[v_2])\rightarrow [\langle k_3,v_3\rangle](k2​,[v2​])→[⟨k3​,v3​⟩]。 就是说，map阶段接收一个(k1,v1)(k_1,v_1)(k1​,v1​)的输入，生成若干键值对⟨k2,v2⟩\langle...

Gradient Descent 方法1 对于光滑函数f(x)f(x)f(x)，在xkx^kxk处，希望找到一个方向dkd^kdk使得函数下降最快。因此考虑 ϕ(α)=f(xk+αdk)\phi(\alpha)=f(x^k+\alpha d^k) ϕ(α)=f(xk+αdk) 在xkx^kxk处进行一阶泰勒展开，得： ϕ(α)=f(xk)+α(∇f(xk))⊤dk+O(α2∥dk∥2)\phi(\alpha) = f(x^k)+\alpha \left(\nabla f(x^k)\right)^\top d^k + \mathcal O(\alpha^2\|d^k\|^2) ϕ(α)=f(xk)+α(∇f(xk))⊤dk+O(α2∥dk∥2) 根据柯西不等式，当α\alphaα足够小时，取dk=−∇f(xk)d^k=-\nabla f(x^k)dk=−∇f(xk)会使得函数下降最快。 (∇f(xk))⊤⋅dk≥−∥∇f(xk)∥⋅∥dk∥\left(\nabla f(x^k)\right)^\top \cdot d^k \geq -\|\nabla f(x^k)\|...