習題6.1

首先解釋什么是指數分布族，組數分布族，也稱指數族分布（后面用這個名詞替代），指數族分布為滿足 \(f(x|\theta) = h(x) *exp(\eta(\theta)*T(x) - A(\eta))\) 形式的概率分布 （\(f(x|\theta)\) 可為概率分布的概率密度函式），

考慮邏輯斯諦分布，并且不考慮偏置的問題（或者將 \(x\) 增加一個維度為常數1）， \(P(Y=1|x) = \frac{exp(w*x)}{1 + exp(w*x)}\) ， \(P(Y=0|x) = \frac{1}{1 + exp(w*x)}\)

所以，邏輯斯諦分布可以寫為

\(P(Y|x) = (\frac{exp(w*x)}{1 + exp(w*x)})^y*(\frac{1}{1 + exp(w*x)})^{(1-y)} \\ =exp(y*log(\frac{exp(w*x)}{1 + exp(w*x)}) + (1-y)*log(\frac{1}{1 + exp(w*x)})) \\ = exp(y*w*x - log(1 + exp(w*x)))\)

可以發現 \(h(y)=1\) ，\(T(y) = y\)，\(\eta(x) = w*x\) ，\(A(\eta) = log(1 + exp(\eta))\)

因此，邏輯斯諦分布屬于指數族分布，

習題6.2

假設要估計的邏輯斯諦回歸模型為 \(h_{\theta}(x) = P(Y=1|x) = \frac{1}{1 + e^{(-\theta*x)}}\)

損失函式為 \(L(\theta) = \sum \limits_i -y^{(i)}*log(h_{\theta}(x^{(i)})) - (1-y^{(i)})*log(1 - h_{\theta}(x^{(i)})) = \sum \limits_i -y^{(i)}*log(\frac{e^{x^{(i)}\theta}}{1 + e^{x^{(i)}\theta}}) + y^{(i)}*log(\frac{1}{1 + e^{x^{(i)}\theta}}) -log(\frac{1}{1 + e^{x^{(i)}\theta}}) = \sum \limits_i -y^{(i)}*x^{(i)}*\theta +log(1+e^{x^{(i)}\theta})\)

所以， \(\frac{\partial}{\partial \theta} L(\theta) = \sum \limits_i -y^{(i)}*x^{(i)} + \frac{e^{x^{(i)}\theta}}{1 + e^{x^{(i)}\theta}}x^{(i)} = \sum \limits_i x^{(i)}*(h_{\theta}(x^{(i)} - y^{(i)}))\)

假設 \(f(\theta) = L(\theta)\) ， \(g(\theta) = \frac{\partial}{\partial \theta} L(\theta)= \nabla f(\theta)\)

邏輯斯諦回歸模型學習的梯度下降演算法

輸入：目標函式\(f(\theta)\) ，梯度函式\(g(\theta)\) ，學習率 \(\eta\) ，計算精度\(\epsilon\)

輸出：\(f(\theta)\) 的極小值 \(\theta^*\)

（1）選取初值 \(\theta^{(0)}\) ，并令 \(k=0\)

（2）計算 \(f(\theta^{(k)})\)

（3）計算梯度 \(g(\theta^{(k)})\) ，當 \(\left\| g(\theta^{(k)}) \right\| < \epsilon\) 時，停止迭代，令 \(\theta^* = \theta^{(k)}\) ；否則，令 \(\theta^{(k+1)} = \theta^{(k)} -\eta*g(\theta^{(k)})\)

（4）計算 \(f(\theta^{(k+1)})\) ，當 \(\left\| f(\theta^{(k+1)} - f(\theta^{(k)} \right\| < \epsilon\) 或 \(\left\| \theta^{(k+1)} - \theta^{(k)}\right\| < \epsilon\) 時，停止迭代，令 \(\theta^* = \theta^{(k)}\) ，

（5）否則，令 \(k = k+1\) ，轉（3）

習題6.3

勘誤：《統計學習方法》附錄B 5.Broyden類演算法 從DFP演算法 \(G_k\) 的迭代公式應該是(B.24)

最大熵模型為 \(P_w(y|x) = \frac{1}{Z_w(x)} exp(\sum \limits_{i=1}^n w_if_i(x,y))\) ，其中 \(Z_w(x) = \sum \limits_y exp(\sum \limits_{i=1}^nw_if_i(x,y))\)

即 最大熵模型為 \(P_w(y|x) = \frac{exp(\sum \limits_{i=1}^n w_if_i(x,y))}{\sum \limits_y exp(\sum \limits_{i=1}^nw_if_i(x,y))}\)

最大熵模型的目標函式為 \(\mathop{min} \limits_w f(w) = \sum \limits_x \widetilde P(x) log \sum \limits_yexp(\sum \limits_{i=1}^n w_if_i(x,y)) - \sum \limits_{x,y} \widetilde P(x,y) \sum \limits_{i=1}^nw_if_i(x,y)\)

梯度為 \(g(w) = (\frac{\partial f(w)}{\partial w_1}, \frac{\partial f(w)}{\partial w_2},..., \frac{\partial f(w)}{\partial w_n})^T\) ，其中 \(\frac{\partial f(w)}{\partial w_i} = \sum \limits_{x,y} \widetilde P(x)P_w(y|w)f_i(x,y) - E_{\widetilde P}(f_i)\) ，

DFP演算法是擬牛頓法的一種，主要是通過用 \(G_k\) 作為 \(H_k^-\) 的近似，DFP演算法首先需要滿足每次迭代 \(G_k\) 是正定的，其次需要滿足 \(G_{k+1}y_k = \delta_k\) 這一擬牛頓條件，

其中 \(y_k = g_{k+1} - g_k\) ，\(\delta_k = x^{(k+1)} -x^k\) ，

假設每次迭代按照 \(G_{k+1} = G_k + \Delta G_k\) 去更新矩陣，

DFP演算法做了如下假設，假設 \(G_{k+1} = G_k +P_k + Q_k\) ，其中 \(P_k\) 和 \(Q_k\) 待定， 所以 \(G_{k+1} y_k = G_ky_k +P_ky_k + Q_ky_k\)

為使條件滿足，可令 \(P_ky_k = \delta_k\) ， \(Q_ky_k = -G_ky_k\) ，由此，可取 \(P_k = \frac{\delta_k \delta_k^T}{\delta_k^T y_k}\) ， \(Q_k = - \frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}\)

所以 \(G_{k+1} = G_k + \frac{\delta_k \delta_k^T}{\delta_k^T y_k} - \frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}\)

最大熵模型學習的DFP演算法

輸入：特征函式 \(f_1,f_2,...,f_n\) ；經驗分布 \(\widetilde P(x,y)\) ，目標函式 \(f(w)\)， 梯度 \(g(w) = \nabla f(w)\) ，學習率 \(\eta\) ，計算精度 \(\epsilon\)

輸出：最優引數 \(w^*\) ；最優模型 \(P_{w^*}(y|x)\)

（1）選擇初值 \(w^{(0)}\) ，同時取 \(G_0\) 為正定對稱矩陣，令 \(k=0\)

（2）計算 \(g_k = g(w^{(0)})\) ，當 \(\left\| g(w^{(k)}) \right\| < \epsilon\) 時，停止迭代，令 \(w^* = w^{(k)}\) ；否則轉（3）

（3）令 \(w^{(k+1)} = w^{(k)} - \eta * G_kg_k\)

（4）計算 \(g_{k+1} = g(w^{(k+1)})\) ，若 \(\left\| g(w^{(k+1)}) \right\| < \epsilon\) ，停止迭代，令 \(w^* = w^{(k)}\) ；否則，計算 \(G_{k+1} = G_k + \frac{\delta_k \delta_k^T}{\delta_k^T y_k} - \frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}\) ，其中 \(y_k = g_{k+1} - g_k\) ，\(\delta_k = x^{(k+1)} -x^k\) ，

（5）令 \(k = k+1\) ，轉（3）

標籤：其他

上一篇：[GYCTF2020]Blacklist-思路

下一篇：元學習——從MAML到MAML++