【機器學習】Softmax Regression簡介

本文我們來介紹Softmax Regression。

本文目錄如下：

• Motivation
• Introduction
• Equation
  • 1 Restatement
  • 2 Probability Estimation
  • 3 Cost Function
• Reference
• Appendix
  • 1 Cost function求梯度

1. Motivation

Softmax Regression主要應用于多标簽分類，它的主要作用是将多個标量映射為一個機率分布。

N features→K labels 

2. Introduction

為了更好地闡述Softmax，讓我們首先來回顧一下Logistic regression。在Logistic regression中，我們要解決的實際上是一個二分類問題：

y(i)∈{0,1}

現在，假設我們有m個帶标簽的訓練資料：

(x(1),y(1)),...,(x(m),y(m))

其中， x(i)∈Rn ， y(i)∈{0,1} 。那麼我們有如下結論，首先是我們的假設：

hθ(x)=11+exp(−θTx)

可以将輸入資料映射為一個0-1分布，得到機率的估計公式：

P(y=0|x;θ)=11+exp(−θTx)

P(y=1|x;θ)=exp(−θTx)1+exp(−θTx)

接下來，就來到我們熟悉的步驟了：設定cost function，梯度下降法求參數。為了明确起見，我們把cost function也羅列如下：

J(θ)=−[∑i=1my(i)loghθ(x(i))+(1−y(i))log(1−hθ(x(i)))]

θ=argmaxθJ(θ)

其中參數 θ∈Rn 。

現在明白了吧？在logistic regression中，由于我們面對的是一個二分類問題，是以我們可以将輸入映射為這樣的機率分布，通過最大似然準則，求解參數。

現在我們希望在多标簽分類問題中，也能夠應用類似的架構求解問題。Softmax Regression應運而生！

3. Equation

3.1. Restatement

問題重述如下，給定一組訓練資料集 {(x(1),y(1)),...,(x(m),y(m))} 。此時，輸入資料仍為 x(i)∈Rn 。而輸出标簽從0,1兩類，變成了 K 類：y(i)∈{0,...,K}。

3.2. Probability Estimation

我們要做首先就是估計這 K 類中每一類的輸出機率。是以，我們要輸出的是一個K維的向量，向量中的每一個值即為該類的輸出機率。下面我們直接給出結果：

hθ(x)=⎡⎣⎢⎢P(y=1|x;θ)⋮P(y=K|x;θ)⎤⎦⎥⎥=1∑Kj=1exp(−θ(j)Tx)⋅⎡⎣⎢⎢⎢exp(−θ(1)Tx)⋮exp(−θ(K)Tx)⎤⎦⎥⎥⎥

這裡面，我們将之前的 θ∈Rn 擴充到了 K 維，即我們有：θ(1),...,θ(K)∈Rn。為了簡潔起見（同時也是為了我們之後的矩陣化程式設計友善起見，我們這裡仍使用 θ 表示所有的參數。我們使用一個n-by-K的矩陣表示所有的參數，如下所示：

θ=⎡⎣⎢|θ(1)||θ(2)|⋯⋯⋯|θ(K)|⎤⎦⎥

此時參數矩陣： θ∈Rn×K

這個時候，我們已經有了hypothesis function，接下來就可以進一步地向前推進了，下面讓我們來關注cost function吧。

3.3. Cost Function

在給出cost function之前，首先介紹一下訓示函數（indicator function）。所謂的訓示函數其實和我們學習C語言中的if語句有點像。 1{true statement}=1 , 1{false statement}=0 。有了這個幫手，我們就可以簡介地描述cost function啦。

J(θ)=−[∑i=1m∑K=1K1{y(i)=k}⋅logP(y=K|x;θ)]=−⎡⎣∑i=1m∑K=1K1{y(i)=k}⋅logexp(−θ(k)Tx)∑Kj=1exp(−θ(j)Tx)⎤⎦

很遺憾，與Linear Regression不同，我們并不能使用解析解來求得參數。此處，我們使用批梯度下降法（Batch Gradient Descent，BGD）方法來進行求解：

θ(i):=θ(i)−∇θ(i)J(θ)

在這裡，每一個 θ(i) 都是一個n維的向量。

對于 ∇θ(i)J(θ) 的計算是比較的複雜的，這裡我們不加證明地直接給出，如果希望了解推導過程的同學可以檢視附錄（Appendix）部分。

∇θ(k)J(θ)=−∑i=1m[x(i)(1{y(i)=k}−P(y(i)=k|x;θ))]

此時，所有我們需要的内容皆已具備，隻要有足夠多的分類資料，我們就可以使用梯度下降法訓練自己的多标簽分類資料啦！

我們将算法重述如下：

Algorithm1. Softmax Regression

輸入：訓練資料 {(x(1),y(1)),...,(x(m),y(m))} 。其中， x(i)∈Rn ， y(i)∈{0,...,K} 。

輸出：估計标簽值 y^(i) 。

(1) 初始化參數 θ(i) ，對 i∈{1,2,...,K} ， θ(k)=0n×1 。

(2) 對 i=1,...,#training ：

對 j=1,...,K ：

設若 y(j)=k，k∈{1,...,K} ，更新 θ(k) :

θ(k):=θ(k)−∇θ(k)J(θ)

其中， ∇θ(k)J(θ) 的計算方法如下：

∇θ(k)J(θ)=−∑i=1m[x(i)(1{y(i)=k}−P(y(i)=k|x;θ))]

(3) 如果不是所有的 θ(k) 都收斂，重複步驟2。

4. Reference

[1] 李航. 統計學習方法[J]. 2012.

[2] Andrew Ng, et al. Softmax Regression. UFLDL Tutorial. http://ufldl.stanford.edu/tutorial/

5. Appendix

5.1. Cost function求梯度

問題描述如下，給定cost function：

J(θ)=−⎡⎣∑i=1m∑K=1K1{y(i)=k}⋅logexp(−θ(k)Tx)∑Kj=1exp(−θ(j)Tx)⎤⎦

試求解： ∇θ(a)J(θ) ，這裡解釋一下，由于我們在原有的cost function中已經使用了 i，j，k 的下标，此處我們使用a作為求梯度時的自變量，即 θ(a) 。當我們已經求梯度完畢後，再将這個臨時變量a替換成為k。二者隻是一個标号的不同。

首先分析一下，在cost function中可能涉及到 θ(a) 就是右邊log函數中的分子，分母。隻有當 k=a 的時候，分子才會對求梯度産生影響，而無論k取何值時，分母都一定會對求導産生影響。注意到最外層的 −∑i=1m 這一項實際上對求導并不産生任何影響，真正産生影響的是：

L(θ)=∑K=1K1{y(i)=k}⋅logexp(−θ(k)Tx)∑Kj=1exp(−θ(j)Tx)

是以我們有：

L(θ)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪1{y(i)=k}⋅logexp(−θ(k)Tx)∑Kj=1exp(−θ(j)Tx)1{y(i)=a}⋅logexp(−θ(a)Tx)∑Kj=1exp(−θ(j)Tx)k=1,...,a−1,a+1,...,Kk=a

對于上述兩式，我們使用 L1(θ) ， L2(θ) 來指代。

首先我們對于 L1(θ) 進行求導：

∇θ(a)L1(θ)=====1{y(i)=k}⋅∂∂θ(a)logexp(−θ(k)Tx(i))∑Kj=1exp(−θ(j)Tx(i))1{y(i)=k}⋅∑Kj=1exp(−θ(j)Tx(i))exp(−θ(k)Tx(i))⋅∂∂θ(a)exp(−θ(k)Tx(i))∑Kj=1exp(−θ(j)Tx(i))1{y(i)=k}⋅∑Kj=1exp(−θ(j)Tx(i))exp(−θ(k)Tx(i))⋅⎛⎝⎜⎜−exp(−θ(k)Tx(i))(∑Kj=1exp(−θ(j)Tx(i)))2⎞⎠⎟⎟⋅x⋅exp(−θ(a)Tx(i))1{y(i)=k}⋅⎛⎝⎜−exp(−θ(a)Tx(i))(∑Kj=1exp(−θ(j)Tx(i)))⎞⎠⎟⋅x(i)1{y(i)=k}⋅x(i)⋅(−P(y(i)=k|x;θ))

看上去有點兒複雜？是吧。其實就是我們在高中時候學過的很簡單的“鍊式求導”，斌斌在這裡強烈建議您拿出一張草稿紙，自己手動推導一下，你會很快發現，看上去有些可怖的公式推導，居然如此簡單！

下面我們再來推導 ∇θ(a)L2(θ) ，這個推導可能會比上面的推導更複雜一下，因為我們要同時顧及到分子分母，一起來看吧：

∇θ(a)L2(θ)=====1{y(i)=k}⋅∂∂θ(a)logexp(−θ(a)Tx(i))∑Kj=1exp(−θ(j)Tx(i))1{y(i)=k}⋅∑Kj=1exp(−θ(j)Tx(i))exp(−θ(a)Tx(i))⋅∂∂θ(a)exp(−θ(a)Tx(i))∑Kj=1exp(−θ(j)Tx(i))1{y(i)=k}⋅∑Kj=1exp(−θ(j)Tx(i))exp(−θ(a)Tx(i))⋅x(i)exp(−θ(a)Tx(i))∑Kj=1exp(−θ(j)Tx(i))−x(i)exp(−θ(a)Tx(i))2(∑Kj=1exp(−θ(j)Tx(i)))21{y(i)=k}⋅x(i)⋅∑Kj=1exp(−θ(j)Tx(i))−x(i)exp(−θ(a)Tx(i))∑Kj=1exp(−θ(j)Tx(i))1{y(i)=k}⋅x(i)⋅(1−P(y(i)=a|x(i);θ))

至此，我們已經完成了對于 L1(θ) ， L2(θ) 的梯度求導，隻要将這兩部分進行組合即可得到最終對于cost function的梯度，還有我們一開始将 −∑i=1m 去掉了，千萬不要忘記最後加回來哦~~~

最後，我們得到前述的結論：

∇θ(k)J(θ)=−∑i=1m[x(i)(1{y(i)=k}−P(y(i)=k|x(i);θ))]

2015.12.16 于浙大.