? 線性回歸（linear regression）：試圖學得一個線性模型以盡可能準確地預測實際值的輸出。
以一個例子來說明線性回歸，假設銀行貸款會根據 年齡 和 工資 來評估可放款的額度。即：
? 數據：工資和年齡（2個特征）
? 目標：預測銀行放款額度（標簽）
? 參數：考慮工資和年齡分別對放款額度的影響程度
可以寫成這樣： Y = X 1 θ 1 + X 2 θ 2 Y=X_1\theta_1+X_2\theta_2 Y=X1?θ1?+X2?θ2?，這里 X 1 、 X 2 就是特征， Y X_1、X_2 就是特征，Y X1?、X2?就是特征，Y就是銀行最終放款額度。
? 找到最合適的一個平面來擬合數據點：
? 擬合的平面方程： h θ ( x ) = θ 0 + θ 1 x 1 + θ 2 x 2 h_{\theta}(x)=\theta_0+\theta_1x_1+\theta_2x_2 hθ?(x)=θ0?+θ1?x1?+θ2?x2?，這里 θ 0 \theta_0 θ0?是偏置項。整合該方程可以寫成如下形式：
h θ ( x ) = ∑ i = 0 n θ i x i = θ ? x h_{\theta}(x)=\sum_{i=0}^n \theta_ix_i=\theta^\top x hθ?(x)=i=0∑n?θi?xi?=θ?x
注意這里 x 0 = 1 x_0=1 x0?=1，添加一個全為1的特征，方便表示。
? 真實值和預測值之間肯定存在誤差，用 ? \epsilon ?來表示誤差。對于每個樣本：
y i = θ ? x i + ? i y_i = \theta^\top x_i + \epsilon_i yi?=θ?xi?+?i?
這里 y i y_i yi? 為真實值， θ ? x i \theta^\top x_i θ?xi?為預測值， ? i \epsilon_i ?i?為誤差項
? 對于誤差的理解：誤差 ? i \epsilon_i ?i?是獨立同分布的，且服從均值為0方差為 θ 2 \theta^2 θ2的高斯分布
- 獨立：每個樣本 x i x_i xi?是沒有關系的（張三李四一起放款，他倆沒關系）
- 同分布：每個 x i x_i xi?都是對于同一個問題的（他倆都是來同一家銀行 ）
- 高斯分布：誤差可大可小，但是絕大多數情況下這個浮動不會太大，極小情況下浮動會比較大，符合正常情況。
? 由于誤差服從高斯分布：
p ( ? i ) = 1 2 π σ e ? 1 2 ( ? i σ ) 2 p(\epsilon_i) = \frac{1}{\sqrt{2\pi}\sigma } e^{-\frac{1}{2}\left(\frac{\epsilon_i}{\sigma}\right)^2} p(?i?)=2π?σ1?e?21?(σ?i??)2
將預測值和誤差帶入上式得：
y i = θ ? x i + ? i 帶入?? p ( ? i ) = 1 2 π σ e ? 1 2 ( ? i σ ) 2 ： p ( y i ∣ x i ; θ ) = 1 2 π σ e ? 1 2 ( y i ? θ ? x i σ ) 2 y_i = \theta^\top x_i + \epsilon_i \\ 帶入\ \ p(\epsilon_i) = \frac{1}{\sqrt{2\pi}\sigma } e^{-\frac{1}{2}\left(\frac{\epsilon_i}{\sigma}\right)^2}：\\ p(y_i|x_i;\theta)=\frac{1}{\sqrt{2\pi}\sigma } e^{-\frac{1}{2}\left(\frac{y_i-\theta^\top x_i}{\sigma}\right)^2} yi?=θ?xi?+?i?帶入??p(?i?)=2π?σ1?e?21?(σ?i??)2：p(yi?∣xi?;θ)=2π?σ1?e?21?(σyi??θ?xi??)2
上式的似然函數如下：
L ( θ ) = ∏ i = 1 m p ( y i ∣ x i ; θ ) = ∏ i = 1 m 1 2 π σ e ? 1 2 ( y i ? θ ? x i σ ) 2 L(\theta) = \prod_{i=1}^mp(y_i|x_i;\theta)=\prod_{i=1}^m \frac{1}{\sqrt{2\pi}\sigma } e^{-\frac{1}{2}\left(\frac{y_i-\theta^\top x_i}{\sigma}\right)^2} L(θ)=i=1∏m?p(yi?∣xi?;θ)=i=1∏m?2π?σ1?e?21?(σyi??θ?xi??)2
對似然函數的解釋：
? 什么樣的參數跟我們的數據組合后恰好是真實值
對數似然：
l o g L ( θ ) = l o g ∏ i = 1 m p ( y i ∣ x i ; θ ) = l o g ∏ i = 1 m 1 2 π σ e ? 1 2 ( y i ? θ ? x i σ ) 2 = m l o g 1 2 π σ ? 1 σ 2 ? 1 2 ? ∑ i = 1 m ( y i ? θ ? x i ) 2 log L(\theta) =log \prod_{i=1}^mp(y_i|x_i;\theta)=log \prod_{i=1}^m \frac{1}{\sqrt{2\pi}\sigma } e^{-\frac{1}{2}\left(\frac{y_i-\theta^\top x_i}{\sigma}\right)^2}\\=mlog\frac{1}{\sqrt{2 \pi}\sigma}-\frac{1}{\sigma ^2}*\frac12*\sum_{i=1}^m(y_i-\theta^\top x_i)^2 logL(θ)=logi=1∏m?p(yi?∣xi?;θ)=logi=1∏m?2π?σ1?e?21?(σyi??θ?xi??)2=mlog2π?σ1??σ21??21??i=1∑m?(yi??θ?xi?)2
目標是讓似然函數（對數變換之后）越大越好：
m a x l o g L ( θ ) → m i n J ( θ ) = 1 2 ∑ i = 1 m ( y i ? θ ? x i ) 2 （最小二乘法） max \ log L(\theta)\\ →min \ J(\theta)=\frac12 \sum_{i=1}^m(y_i-\theta^\top x_i)^2（最小二乘法） max?logL(θ)→min?J(θ)=21?i=1∑m?(yi??θ?xi?)2（最小二乘法）
J ( θ ) = 1 2 ∑ i = 1 m ( y i ? θ ? x i ) 2 J(\theta)=\frac12 \sum_{i=1}^m(y_i-\theta^\top x_i)^2 J(θ)=21?∑i=1m?(yi??θ?xi?)2即為最小二乘法。
? 將目標函數寫為矩陣形式：
J ( θ ) = 1 2 ∑ i = 1 m ( y i ? θ ? x i ) 2 = 1 2 ( X θ ? y ) ? ( X θ ? y ) 對 θ 求偏導 : ? θ J ( θ ) = X ? X θ ? X ? y 令 ? θ J ( θ ) = 0 得 : θ = ( X ? X ) ? 1 X ? y J(\theta)=\frac12 \sum_{i=1}^m(y_i-\theta^\top x_i)^2= \frac12(X\theta-y)^\top (X\theta-y)\\ 對\theta 求偏導:\\ \nabla_\theta J(\theta)=X^\top X\theta-X^\top y\\ 令\nabla_\theta J(\theta)=0得:\\ \theta=(X^\top X)^{-1}X^\top y J(θ)=21?i=1∑m?(yi??θ?xi?)2=21?(Xθ?y)?(Xθ?y)對θ求偏導:?θ?J(θ)=X?Xθ?X?y令?θ?J(θ)=0得:θ=(X?X)?1X?y
? 采用微分和跡的關系 d f = t r ( ( ? f ? X ) ? d X ) df= tr((\frac{\partial f}{\partial X})^\top dX) df=tr((?X?f?)?dX)進行求導，求導過程如下：
d J ( θ ) = t r ( d J ( θ ) ) = d [ 1 2 ( X θ ? y ) ? ( X θ ? y ) ] = t r [ d ( 1 2 ( θ ? X ? X θ ? 2 y ? X θ + y ? y ) ) ] = t r [ d ( 1 2 θ ? X ? X θ ) ] ? t r ( d ( 2 y ? X θ ) ) + t r ( d ( y ? y ) ) = t r ( 1 2 d θ ? X ? X θ ) + t r ( 1 2 θ ? X ? X d θ ) ? t r ( 2 y ? X d θ ) + 0 = t r ( 1 2 θ ? X ? X d θ ) + t r ( 1 2 θ ? X ? X d θ ) ? t r ( 2 y ? X d θ ) = t r ( θ ? X ? X d θ ? 2 y ? X d θ ) = t r ( ( θ ? X ? X ? 2 y ? X ) d θ ) = t r ( ( X ? X θ ? 2 X ? y ) ? d θ ) 故： ? J ( θ ) ? θ = X ? X θ ? 2 X ? y dJ(\theta)= tr(dJ(\theta))=d[\frac12(X\theta-y)^\top (X\theta-y)]\\ =tr[d(\frac12(\theta^\top X^\top X\theta-2y^\top X\theta+y^\top y))]\\ =tr[d(\frac12\theta^\top X^\top X\theta)]-tr(d(2y^\top X\theta))+tr(d(y^\top y))\\ =tr(\frac12d\theta^\top X^\top X\theta)+tr(\frac12\theta^\top X^\top Xd\theta)-tr(2y^\top Xd\theta)+0\\ =tr(\frac12\theta^\top X^\top Xd\theta)+tr(\frac12\theta^\top X^\top Xd\theta)-tr(2y^\top Xd\theta)\\ =tr(\theta^\top X^\top Xd\theta-2y^\top Xd\theta)=tr((\theta^\top X^\top X-2y^\top X)d\theta)\\ =tr(( X^\top X\theta - 2X^\top y)^\top d\theta)\\ 故：\\ \frac{\partial J(\theta)}{\partial \theta}=X^\top X\theta - 2X^\top y\\ dJ(θ)=tr(dJ(θ))=d[21?(Xθ?y)?(Xθ?y)]=tr[d(21?(θ?X?Xθ?2y?Xθ+y?y))]=tr[d(21?θ?X?Xθ)]?tr(d(2y?Xθ))+tr(d(y?y))=tr(21?dθ?X?Xθ)+tr(21?θ?X?Xdθ)?tr(2y?Xdθ)+0=tr(21?θ?X?Xdθ)+tr(21?θ?X?Xdθ)?tr(2y?Xdθ)=tr(θ?X?Xdθ?2y?Xdθ)=tr((θ?X?X?2y?X)dθ)=tr((X?Xθ?2X?y)?dθ)故：?θ?J(θ)?=X?Xθ?2X?y
當 X ? X X^\top X X?X為滿秩矩陣或者正定矩陣時，令偏導數 ? J ( θ ) ? θ = X ? X θ ? 2 X ? y = 0 \frac{\partial J(\theta)}{\partial \theta}=X^\top X\theta - 2X^\top y=0 ?θ?J(θ)?=X?Xθ?2X?y=0得到：
θ = ( X ? X ) ? 1 X ? y \theta=(X^\top X)^{-1}X^\top y θ=(X?X)?1X?y
?
其中 ( X ? X ) ? 1 (X^\top X)^{-1} (X?X)?1是矩陣 X ? X X^\top X X?X的逆矩陣。但是現實任務中， X ? X X^\top X X?X通常不是滿秩矩陣，例如在許多任務中會遇到大量的變量，其數目甚至超過樣例數，導致X的列數多于行數， X ? X X^\top X X?X ， X ? X X^\top X X?X顯然不滿秩。此時可以解出多個 θ \theta θ，他們都能使均方差最小化。選擇哪一個解作為輸出，將由機器學習算法的歸納偏好決定，常見的做法是引入正則化項。
![[C++歷練之路]優先級隊列||反向迭代器的模擬實現](http://pic.xiahunao.cn/[C++歷練之路]優先級隊列||反向迭代器的模擬實現)
![BUUCTF [ACTF新生賽2020]outguess 1](http://pic.xiahunao.cn/BUUCTF [ACTF新生賽2020]outguess 1)
