作者 |?我是韓小琦

鏈接 | https://zhuanlan.zhihu.com/p/43270830

3.1 試分析在什么情況下，在以下式子中不比考慮偏置項b。

答：

在樣本??中有某一個屬性??為固定值時。那么此時??等價于偏置項，此時??與??等價。

3.2 試證明，對于參數?，對率回歸（logistics回歸）的目標函數（3.18）是非凸的，但其對數似然函數（3.27）是凸的。（待填坑）

答：

3.18：??，

3.27：??。

對實數集上的函數，可通過求二階導數來判別：若二階導數在區間上非負，則稱為凸函數；若二階導數在區間上恒大于 0，則稱為嚴格凸函數。原書p54）

對于多元函數，其Hessian matrix為半正定即為凸函數。

對于式3.27，關于??的二階導有 （原書p60）?

?

其中第一個等號是原書中的，第二個等號中??為??矩陣，每一列對應一個樣本，??為對角矩陣，??。

18-11-13更新：

關于??，對于任意向量??都有：?

?

因此其海森矩陣為半正定。

對于式3.18，這里，??理解為標量，而??為??的列向量。則其一階導?

?。二階導??

（即海森矩陣)，其中??秩為1，非零特征值只有一個，其正負號取決于?，顯然當 在(0,1)之間變化時，特征值正負號會發生變化，于是3.18式關于??的海森矩陣非半正定，因此非凸。

3.3 編程實現對率回歸，并給出西瓜數據集3.0α上的結果

https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch3--%E7%BA%BF%E6%80%A7%E6%A8%A1%E5%9E%8B/3.3

''' 與原書不同，原書中一個樣本xi 為列向量，本代碼中一個樣本xi為行向量 嘗試了兩種優化方法，梯度下降和牛頓法。兩者結果基本相同，不過有時因初始化的原因， 會導致牛頓法中海森矩陣為奇異矩陣，np.linalg.inv(hess)會報錯。以后有機會再寫擬牛頓法吧。 '''import numpy as np import pandas as pd from matplotlib import pyplot as plt from sklearn import linear_modeldef sigmoid(x):s = 1 / (1 + np.exp(-x))return sdef J_cost(X, y, beta):''':param X: sample array, shape(n_samples, n_features):param y: array-like, shape (n_samples,):param beta: the beta in formula 3.27 , shape(n_features + 1, ) or (n_features + 1, 1):return: the result of formula 3.27'''X_hat = np.c_[X, np.ones((X.shape[0], 1))]beta = beta.reshape(-1, 1)y = y.reshape(-1, 1)Lbeta = -y * np.dot(X_hat, beta) + np.log(1 + np.exp(np.dot(X_hat, beta)))return Lbeta.sum()def gradient(X, y, beta):'''compute the first derivative of J(i.e. formula 3.27) with respect to beta i.e. formula 3.30----------------------------------:param X: sample array, shape(n_samples, n_features):param y: array-like, shape (n_samples,):param beta: the beta in formula 3.27 , shape(n_features + 1, ) or (n_features + 1, 1):return:'''X_hat = np.c_[X, np.ones((X.shape[0], 1))]beta = beta.reshape(-1, 1)y = y.reshape(-1, 1)p1 = sigmoid(np.dot(X_hat, beta))gra = (-X_hat * (y - p1)).sum(0)return gra.reshape(-1, 1)def hessian(X, y, beta):'''compute the second derivative of J(i.e. formula 3.27) with respect to beta i.e. formula 3.31----------------------------------:param X: sample array, shape(n_samples, n_features):param y: array-like, shape (n_samples,):param beta: the beta in formula 3.27 , shape(n_features + 1, ) or (n_features + 1, 1):return:'''X_hat = np.c_[X, np.ones((X.shape[0], 1))]beta = beta.reshape(-1, 1)y = y.reshape(-1, 1)p1 = sigmoid(np.dot(X_hat, beta))m, n = X.shapeP = np.eye(m) * p1 * (1 - p1)assert P.shape[0] == P.shape[1]return np.dot(np.dot(X_hat.T, P), X_hat)def update_parameters_gradDesc(X, y, beta, learning_rate, num_iterations, print_cost):'''update parameters with gradient descent method--------------------------------------------:param beta::param grad::param learning_rate::return:'''for i in range(num_iterations):grad = gradient(X, y, beta)beta = beta - learning_rate * gradif (i % 10 == 0) & print_cost:print('{}th iteration, cost is {}'.format(i, J_cost(X, y, beta)))return betadef update_parameters_newton(X, y, beta, num_iterations, print_cost):'''update parameters with Newton method:param beta::param grad::param hess::return:'''for i in range(num_iterations):grad = gradient(X, y, beta)hess = hessian(X, y, beta)beta = beta - np.dot(np.linalg.inv(hess), grad)if (i % 10 == 0) & print_cost:print('{}th iteration, cost is {}'.format(i, J_cost(X, y, beta)))return betadef initialize_beta(n):beta = np.random.randn(n + 1, 1) * 0.5 + 1return betadef logistic_model(X, y, num_iterations=100, learning_rate=1.2, print_cost=False, method='gradDesc'):''':param X::param y:~:param num_iterations::param learning_rate::param print_cost::param method: str 'gradDesc' or 'Newton':return:'''m, n = X.shapebeta = initialize_beta(n)if method == 'gradDesc':return update_parameters_gradDesc(X, y, beta, learning_rate, num_iterations, print_cost)elif method == 'Newton':return update_parameters_newton(X, y, beta, num_iterations, print_cost)else:raise ValueError('Unknown solver %s' % method)def predict(X, beta):X_hat = np.c_[X, np.ones((X.shape[0], 1))]p1 = sigmoid(np.dot(X_hat, beta))p1[p1 >= 0.5] = 1p1[p1 < 0.5] = 0return p1if __name__ == '__main__':data_path = r'C:\Users\hanmi\Documents\xiguabook\watermelon3_0_Ch.csv'#data = pd.read_csv(data_path).valuesis_good = data[:, 9] == '是'is_bad = data[:, 9] == '否'X = data[:, 7:9].astype(float)y = data[:, 9]y[y == '是'] = 1y[y == '否'] = 0y = y.astype(int)plt.scatter(data[:, 7][is_good], data[:, 8][is_good], c='k', marker='o')plt.scatter(data[:, 7][is_bad], data[:, 8][is_bad], c='r', marker='x')plt.xlabel('密度')plt.ylabel('含糖量')# 可視化模型結果beta = logistic_model(X, y, print_cost=True, method='gradDesc', learning_rate=0.3, num_iterations=1000)w1, w2, intercept = betax1 = np.linspace(0, 1)y1 = -(w1 * x1 + intercept) / w2ax1, = plt.plot(x1, y1, label=r'my_logistic_gradDesc')lr = linear_model.LogisticRegression(solver='lbfgs', C=1000) # 注意sklearn的邏輯回歸中，C越大表示正則化程度越低。lr.fit(X, y)lr_beta = np.c_[lr.coef_, lr.intercept_]print(J_cost(X, y, lr_beta))# 可視化sklearn LogisticRegression 模型結果w1_sk, w2_sk = lr.coef_[0, :]x2 = np.linspace(0, 1)y2 = -(w1_sk * x2 + lr.intercept_) / w2ax2, = plt.plot(x2, y2, label=r'sklearn_logistic')plt.legend(loc='upper right')plt.show()

3.4 選擇兩個 UCI 數據集，比較 10 折交叉驗證法和留一法所估計出的對率回歸的錯誤率。

https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch3--%E7%BA%BF%E6%80%A7%E6%A8%A1%E5%9E%8B/3.4

import numpy as np from sklearn import linear_model from sklearn.model_selection import LeaveOneOut from sklearn.model_selection import cross_val_scoredata_path = r'C:\Users\hanmi\Documents\xiguabook\Transfusion.txt'data = np.loadtxt(data_path, delimiter=',').astype(int)X = data[:, :4] y = data[:, 4]m, n = X.shape# normalization X = (X - X.mean(0)) / X.std(0)# shuffle index = np.arange(m) np.random.shuffle(index)X = X[index] y = y[index]# 使用sklarn 中自帶的api先 # k-10 cross validation lr = linear_model.LogisticRegression(C=2)score = cross_val_score(lr, X, y, cv=10)print(score.mean())# LOO loo = LeaveOneOut()accuracy = 0 for train, test in loo.split(X, y):lr_ = linear_model.LogisticRegression(C=2)X_train = X[train]X_test = X[test]y_train = y[train]y_test = y[test]lr_.fit(X_train, y_train)accuracy += lr_.score(X_test, y_test)print(accuracy / m)# 兩者結果幾乎一樣# 自己寫一個試試 # k-10 # 這里就沒考慮最后幾個樣本了。 num_split = int(m / 10) score_my = [] for i in range(10):lr_ = linear_model.LogisticRegression(C=2)test_index = range(i * num_split, (i + 1) * num_split)X_test_ = X[test_index]y_test_ = y[test_index]X_train_ = np.delete(X, test_index, axis=0)y_train_ = np.delete(y, test_index, axis=0)lr_.fit(X_train_, y_train_)score_my.append(lr_.score(X_test_, y_test_))print(np.mean(score_my))# LOO score_my_loo = [] for i in range(m):lr_ = linear_model.LogisticRegression(C=2)X_test_ = X[i, :]y_test_ = y[i]X_train_ = np.delete(X, i, axis=0)y_train_ = np.delete(y, i, axis=0)lr_.fit(X_train_, y_train_)score_my_loo.append(int(lr_.predict(X_test_.reshape(1, -1)) == y_test_))print(np.mean(score_my_loo))# 結果都是類似

3.5 編輯實現線性判別分析，并給出西瓜數據集 3.0α 上的結果.

https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch3--%E7%BA%BF%E6%80%A7%E6%A8%A1%E5%9E%8B/3.5

import numpy as np import pandas as pd from matplotlib import pyplot as pltclass LDA(object):def fit(self, X_, y_, plot_=False):pos = y_ == 1neg = y_ == 0X0 = X_[neg]X1 = X_[pos]u0 = X0.mean(0, keepdims=True) # (1, n)u1 = X1.mean(0, keepdims=True)sw = np.dot((X0 - u0).T, X0 - u0) + np.dot((X1 - u1).T, X1 - u1)w = np.dot(np.linalg.inv(sw), (u0 - u1).T).reshape(1, -1) # (1, n)if plot_:fig, ax = plt.subplots()ax.spines['right'].set_color('none')ax.spines['top'].set_color('none')ax.spines['left'].set_position(('data', 0))ax.spines['bottom'].set_position(('data', 0))plt.scatter(X1[:, 0], X1[:, 1], c='k', marker='o', label='good')plt.scatter(X0[:, 0], X0[:, 1], c='r', marker='x', label='bad')plt.xlabel('密度', labelpad=1)plt.ylabel('含糖量')plt.legend(loc='upper right')x_tmp = np.linspace(-0.05, 0.15)y_tmp = x_tmp * w[0, 1] / w[0, 0]plt.plot(x_tmp, y_tmp, '#808080', linewidth=1)wu = w / np.linalg.norm(w)# 正負樣板店X0_project = np.dot(X0, np.dot(wu.T, wu))plt.scatter(X0_project[:, 0], X0_project[:, 1], c='r', s=15)for i in range(X0.shape[0]):plt.plot([X0[i, 0], X0_project[i, 0]], [X0[i, 1], X0_project[i, 1]], '--r', linewidth=1)X1_project = np.dot(X1, np.dot(wu.T, wu))plt.scatter(X1_project[:, 0], X1_project[:, 1], c='k', s=15)for i in range(X1.shape[0]):plt.plot([X1[i, 0], X1_project[i, 0]], [X1[i, 1], X1_project[i, 1]], '--k', linewidth=1)# 中心點的投影u0_project = np.dot(u0, np.dot(wu.T, wu))plt.scatter(u0_project[:, 0], u0_project[:, 1], c='#FF4500', s=60)u1_project = np.dot(u1, np.dot(wu.T, wu))plt.scatter(u1_project[:, 0], u1_project[:, 1], c='#696969', s=60)ax.annotate(r'u0 投影點',xy=(u0_project[:, 0], u0_project[:, 1]),xytext=(u0_project[:, 0] - 0.2, u0_project[:, 1] - 0.1),size=13,va="center", ha="left",arrowprops=dict(arrowstyle="->",color="k",))ax.annotate(r'u1 投影點',xy=(u1_project[:, 0], u1_project[:, 1]),xytext=(u1_project[:, 0] - 0.1, u1_project[:, 1] + 0.1),size=13,va="center", ha="left",arrowprops=dict(arrowstyle="->",color="k",))plt.axis("equal") # 兩坐標軸的單位刻度長度保存一致plt.show()self.w = wself.u0 = u0self.u1 = u1return selfdef predict(self, X):project = np.dot(X, self.w.T)wu0 = np.dot(self.w, self.u0.T)wu1 = np.dot(self.w, self.u1.T)return (np.abs(project - wu1) < np.abs(project - wu0)).astype(int)if __name__ == '__main__':data_path = r'C:\Users\hanmi\Documents\xiguabook\watermelon3_0_Ch.csv'data = pd.read_csv(data_path).valuesX = data[:, 7:9].astype(float)y = data[:, 9]y[y == '是'] = 1y[y == '否'] = 0y = y.astype(int)lda = LDA()lda.fit(X, y, plot_=True)print(lda.predict(X)) # 和邏輯回歸的結果一致print(y)

3.6 線性判別分析僅在線性可分數據上能獲得理想結果，試設計一個改進方法，使其能較好地周于非線性可分數據。

答：

引入核函數，原書p137，有關于核線性判別分析的介紹。

3.7 令碼長為 9，類別數為 4，試給出海明距離意義下理論最優的 ECOC二元碼并證明之。

答：

原書對很多地方解釋沒有解釋清楚，把原論文看了一下《Solving Multiclass Learning Problems via Error-Correcting Output Codes》。

先把幾個涉及到的理論解釋一下。

首先原書中提到：

對同等長度的編碼，理論上來說，任意兩個類別之間的編碼距離越遠，則糾錯能力越強。因此，在碼長較小時可根據這個原則計算出理論最優編碼。

其實這一點在論文中也提到，“假設任意兩個類別之間最小的海明距離為??，那么此糾錯輸出碼最少能矯正??位的錯誤。

拿上圖論文中的例子解釋一下，上圖中，所有類別之間的海明距離都為4，假設一個樣本正確的類別為??，那么codeword應該為 ‘0 0 1 1 0 0 1 1’，若此時有一個分類器輸出錯誤，變成‘0 0 0 1 0 0 1 1’，那么此時距離最近的仍然為??，若有兩個分類輸出錯誤如‘0 0 0 0 0 0 1 1’，此時與??的海明距離都為2，無法正確分類。即任意一個分類器將樣本分類錯誤，最終結果依然正確，但如果有兩個以上的分類器錯誤，結果就不一定正確了。這是??的由來。

此外，原論文中提到，一個好的糾錯輸出碼應該滿足兩個條件：

行分離。任意兩個類別之間的codeword距離應該足夠大。

列分離。任意兩個分類器??的輸出應相互獨立，無關聯。這一點可以通過使分類器??編碼與其他分類編碼的海明距離足夠大實現，且與其他分類編碼的反碼的海明距離也足夠大（有點繞。）。

第一點其實就是原書提到的，已經解釋過了，說說第二點：

如果兩個分類器的編碼類似或者完全一致，很多算法（比如C4.5）會有相同或者類似的錯誤分類，如果這種同時發生的錯誤過多，會導致糾錯輸出碼失效。（翻譯原論文）

個人理解就是：若增加兩個類似的編碼，那么當誤分類時，就從原來的1變成3，導致與真實類別的codeword海明距離增長。極端情況，假設增加兩個相同的編碼，此時任意兩個類別之間最小的海明距離不會變化依然為??，而糾錯輸出碼輸出的codeword與真實類別的codeword的海明距離激增（從1變成3）。所以如果有過多同時發出的錯誤分類，會導致糾錯輸出碼失效。

另外，兩個分類器的編碼也不應該互為反碼，因為很多算法（比如C4.5，邏輯回歸）對待0-1分類其實是對稱的，即將0-1類互換，最終訓練出的模型是一樣的。也就是說兩個編碼互為補碼的分類器是會同時犯錯的。同樣也會導致糾錯輸出碼失效。

當然當類別較少時，很難滿足上面這些條件。如上圖中，一共有三類，那么只有??中可能的分類器編碼（??），其中后四種（??）是前四種的反碼，都應去除，再去掉全為0的，就只剩下三種編碼選擇了，所以很難滿足上述的條件。事實上，對于??種類別的分類，再去除反碼和全是0或者1的編碼后，就剩下??中可行的編碼。

原論文中給出了構造編碼的幾種方法。其中一個是：

回到題目上，在類別為4時，其可行的編碼有7種，按照上述方法有：

當碼長為9時，那么??之后加任意兩個編碼，即為最優編碼，因為此時再加任意的編碼都是先有編碼的反碼，此時，類別之間最小的海明距離都為4，不會再增加。

3.8 ECOC 編碼能起到理想糾錯作用的重要條件是：在每一位編碼上出錯的概率相當且獨立。試析多分類任務經 ECOC 編碼后產生的二類分類器滿足該條件的可能性及由此產生的影響。

答：

條件分解為兩個：一是出錯的概率相當，二是出錯的可能性相互獨立。

先看第一個把，其實就是每個一位上的分類器的泛化誤差相同，要滿足這個條件其實取決于樣本之間的區分難度，若兩個類別本身就十分相似，即越難區分，訓練出的分類器出錯的概率越大，原書p66也提到：

將多個類拆解為兩個"類別子集“，所形成的兩個類別子集的區分難度往往不同，即其導致的二分類問題的難度不同。

所以每個編碼拆解后類別之間的差異越相同（區分難度相當），則滿足此條件的可能性越大。在實際中其實很難滿足。

第二個，相互獨立。在3.7中也提到過，原論文中也提出一個好的糾錯輸出碼應該滿足的其中一個條件就是各個位上分類器相互獨立，當類別越多時，滿足這個條件的可能性越大，在3.7中也解釋了當類別較少時，很難滿足這個條件。

至于產生的影響。西瓜書上也提到：

一個理論糾錯牲質很好、但導致的三分類問題較難的編碼，與另一個理論糾錯性質差一些、但導致的二分類問題較簡單的編碼，最終產生的模型性能孰強孰弱很難說。

3.9 使用 OvR 和 MvM 將多分類任務分解為二分類任務求解時，試述為何無需專門針對類別不平衡性進行處理。

答：

p66 其實已經給出答案了：

對 OvR 、 MvM 來說，由于對每個類進行了相同的處理，其拆解出的二分類任務中類別不平衡的影響會相互抵消，因此通常不需專門處理.

3.10 試推導出多分類代價敏感學習(僅考慮基于類別的誤分類代價)使用"再縮放"能獲得理論最優解的條件。

答：

這道題目其實是周志華教授的一篇論文《On Multi-Class Cost-Sensitive Learning》。把論文理論部分讀了一遍。現在嘗試概述一遍吧。

首先說一點關于“再縮放”的個人理解：無論是代價敏感學習還是非代價敏感學習中，“再縮放”各種方法（過采樣、欠采樣、閾值移動等）都是在調整各類別對模型的影響程度，即各類別的權重。

以??表示將??類樣本誤分類為??類樣本的損失，那么在二分類的問題中，?

?

表示分類器將樣本預測為1類的期望損失，其中?

?

那么當?

?

時即預測1類時的期望損失小于預測2類的期望損失，那么將樣本預測為1類根據合理，當取等號且假設正確分類時損失為0，即可得到最優決策閾值有?

?

即?

?

在《On Multi-Class Cost-Sensitive Learning》中，引用了另外一篇論文《The Foundations of Cost-Sensitive Learning》的一個理論：

通過這個理論來推導出在代價敏感學習中，最優“再縮放”之后，各類別的權重應該滿足的條件。看了原論文才看懂這個理論表達的意思。。關于理論的證明有興趣可以再看看原論文，這里就不再復述一遍了。它想說的是，假設有一個算法??生成的分類器是以??為決策閾值，那么如果當給定一個數據集??以及最優決策閾值??，這個理論表明通過增加負樣本的數量，使其是原來的??倍，創建數據集??，??通過??依然能生成一個以??為決策閾值且足夠好的分類器。以二分類為例，當樣本數量均衡時??。那么根據此理論，相比于一類，二類的再縮放比例應該為一類的??倍，表示一類的影響力為二類影響力的??的倍。以??表示對第??的再縮放比率，推廣到多分類時“再縮放”獲得最優理論解就應滿足：

即：

方程組有解。

其伴隨矩陣秩小于c。

ps. 這道題答的有點爛。有些地方理解確實不深。實在不想再卡在第三章了。懶得再研究了。。

相關閱讀：

周志華機器學習課后習題解析【第二章】

---

推薦閱讀

（點擊標題可跳轉閱讀）

干貨 | 公眾號歷史文章精選

我的深度學習入門路線

我的機器學習入門路線圖

重磅！

AI有道年度技術文章電子版PDF來啦！

掃描下方二維碼，添加?AI有道小助手微信，可申請入群，并獲得2020完整技術文章合集PDF（一定要備注：入群?+ 地點 + 學校/公司。例如：入群+上海+復旦。?

長按掃碼，申請入群

（添加人數較多，請耐心等待）

?

最新 AI 干貨，我在看?

總結

以上是生活随笔為你收集整理的周志华《机器学习》课后习题（第三章）：线性模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。