MIT OCW, Machine Learning 03日目 logistic regression

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 4. Classification Errors, Regularization, Logistic Regression

The Support Vector Machine and Regularization

$$\begin{aligned}&\text{minimize} \frac{1}{2}\|\theta\|^2 + C\sum_{t=1}^n \xi_t \\ &\text{subect to } y_t(\theta^T \mathbf{x}_t +\theta_0)\geq 1-\xi_t \text{ and } \xi_t \geq 0 \text{ for all } t= 1, ..., n \end{aligned}$$
が,relaxationを入れた線形分離のパラメータを求める最適化問題であった.
$y_t(\theta^T \mathbf{x}_t + \theta_0) \geq 1-\xi_t$を変形して,$\xi_t \geq 1 -y_t(\theta^T\mathbf{x}_t + \theta_0)$. $\xi_t \geq 0$だから,$()^+: r \mapsto \max(0, r)$として,example $\mathbf{x}_t$に対するhinge loss
$$\hat{\xi}_t = (1-y_t(\theta^T\mathbf{x}_t + \theta_0))^+$$
を定義する. 束縛条件とrelaxation項をまとめて,
$$\text{minimize } \frac{1}{2}\|\theta\|^2 + C \sum_{t=1}^n \underline{(1-y_t(\theta^T\mathbf{x}_t+\theta_0))^+}_{\hat{\xi_t}}$$
とできる. これは,$\frac{1}{2}\|\theta\|^2$をregularization penaltyとして$C\sum_{t=1}^n \hat{\xi_t}$を目的関数とする最適化問題と見ることが出来る. このように,classification lossのような目的関数とregularization penaltyを含む最適化問題をregularization problemという. 多くの機械学習アルゴリズムはregularization problemと見ることができて,regularization項は目的関数の最小化を安定させたり,事前の知識をアルゴリズムに組み込むために導入される.

Logistic Rgeression, Maximum Likelihood Estimation

labellingの間違いに対処するもう一つの方法に,labelの間違い(ノイズ)がどのように生成されるかをモデル化するというのがある. linear classificatioにおけるノイズの単純なモデルにlogistic regressionがある. decision boundaryから遠く離れたexampleのラベルはより正しい確率が高いというふうに,２つのラベルにprobability distributionを与えるのである.形式的には
$$P(y=1|\mathbf{x}, \theta, \theta_0) = g(\theta^T \mathbf{x}+ \theta_0)$$
とする. ここで$g(z) = (1+\exp(-z))^{-1}$で, logistic functionという. この関数は
$$\log \frac{P(y=1|\mathbf{x}, \theta, \theta_0)}{P(y=-1|\mathbf{x}, \theta, \theta_0)} = \theta^T \mathbf{x} +\theta_0$$
から導かれる.例えば$P(y=1|\mathbf{x}, \theta, \theta_0) = P(y=-1|\mathbf{x}, \theta, \theta_0)=1/2$ならばlog-oddsは$0$であり,$\mathbf{x}$はdecision boundary上に有る.左辺をlog-oddsという.log-oddsの厳密な正当化は後でclass-conditional distributionの仮定をもとに行う.

$1-g(z)=g(-z)$から,
$$P(y=-1|\mathbf{x},\theta,\theta_0)=1-P(y=1|\mathbf{x},\theta,\theta_0) = 1-g(\theta^T\mathbf{x}+\theta_0)=g(-(\theta^T\mathbf{x}+\theta_0))$$
であって,故に
$$P(y|\mathbf{x}, \theta, \theta_0) = g(y(\theta^T\mathbf{x}+\theta_0))$$
である.こうして,labelを確率的に推測するlinear classifierが得られた.training dataのそれぞれのexampleを正しく推測する確率を最大にすることを考える.この確立たちの総乗を
$$L(\theta, \theta_0) = \prod_{t=1}^n P(y_t|\mathbf{x}_t, \theta, \theta_0)$$
と書く.また$L(\theta, \theta_0)$を(conditional) likelihood functionといって,固定されたtraining dataに対するパラメータの関数である. これを最大化する$\theta, \theta_0$をmaximum likelihood estimatesという. また,training dataからmaximum likelihood estimatesを探す手続き(写像)をmaximum likelihood estimatorという.
$L$を最大化するため,logをとって,
$$\begin{aligned}-l(\theta, \theta_0) &= \sum_{t=1}^n -\log P(y_t |\mathbf{x}_t, \theta, \theta_0) \\ &= \sum -\log g(y_t(\theta^T \mathbf{x}_t + \theta_0)) \\ &= \sum \log [1 + \exp(-y_t(\theta^T \mathbf{x}_t + \theta_0))] \end{aligned}$$
を最小化することになる. この関数は凸で,多くの最適化アルゴリズムが存在する. (stochastic) gradient descent(SGD)を導入する.
$-l(\theta, \theta_0)$で偏微分して,
$$\begin{aligned}\frac{d}{d\theta_0} \log[1+\exp(-y_t(\theta^T \mathbf{x}_t + \theta_0))] &= -y_t[1-P(y_t|\mathbf{x}_t,\theta,\theta_0)] \\ \frac{d}{d\theta} \log [1+\exp(-y_t(\theta^T \mathbf{x}_t+\theta_0))] &= -y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t,\theta,\theta_0)] \end{aligned}$$
右辺のベクトルは$\log[1+\exp(-y_t(\theta^T \mathbf{x}_t+\theta_0))]$が単位長さあたり最も増加する$\theta_0, \theta$の方向を表しており,
$$\begin{aligned} \theta_0 &\leftarrow \theta_0 +\eta \cdot y_t[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)] \\ \theta &\leftarrow \theta + \eta \cdot y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t, \theta, \theta_0)] \end{aligned}$$
によって更新を行う. ここで$\eta$は小さい正数で,learning rateという. $[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)]$は間違ったlabelに分類する確率で,perceptron mistake driven updatesに似ているが,どれほど間違っているかによって更新の大きさを変えるところが重大な相違点である.
stochasticでないgradient descentは, $\theta, \theta_0$を固定して,全ての$t$に$\eta \cdot y_t[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)], \eta \cdot y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t, \theta, \theta_0)]$を足し合わせて,その和によって$\theta, \theta_0$を更新する.
最適化が実現したときには
$$\begin{aligned}\frac{d}{d\theta_0} (-l(\theta, \theta_0))&= -\sum_{t=1}^n y_t[1-P(y_t|\mathbf{x}_t,\theta,\theta_0)]=0 &(19)\\ \frac{d}{d\theta}(-l(\theta, \theta_0)) &= -\sum_{t=1}^n y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t,\theta,\theta_0)] =0 \ \ \ &(20)\end{aligned}$$
が成立する.$(19)$は,”label 1のexapleを-1に間違えて分類する確率”と”label -1のexampleを+1に間違えて分類する確率 $\times -1$”の総和が$0$であるということであって,間違いが均衡しているということである. あるいは,$(y_1, ..., y_n)^T$というベクトルと,$(1-P(y_1|\mathbf{x}_1,\theta,\theta_0), ..., 1-P(y_n|\mathbf{x}_n,\theta,\theta_0))^T$というベクトルが直行しているということである.
同様に,$(20)$の等式は,exampleのそれぞれの次元$j$において,$(y_1 x_{1j},...,y_n x_{nj})^T$と$(1-P(y_1|\mathbf{x}_1,\theta,\theta_0), ..., 1-P(y_n|\mathbf{x}_n,\theta,\theta_0))^T$が直行しているということである.
この直交性によって$(19,20)$が成立しているとき,training setにはもはや$\theta, \theta_0$をより良くするための情報が無いということがわかる.

ところで,$y_t(\theta^T \mathbf{x}_t+\theta_0)$が常に正である$\theta, \theta_0$をみつけて両方を定数倍してこれらの値を際限なく大きくすると,$y_t[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)]$は$1$に収束し,わざわざ確率的なモデルを使う意味がなくなってしまうので,regularziation項$\|\theta\|/2$を加えて最適化する.すなわち

$$\frac{1}{2}\|\theta\|^2 + C\sum_{t=1}^n \log [1+\exp(-y_t(\theta^T\mathbf{x}_t+\theta_0))]$$
の最少化問題とする.またこれは
$$\frac{\lambda}{2}\|\theta\|^2 + \sum_{t=1}^n \log [1+\exp(-y_t(\theta^T\mathbf{x}_t+\theta_0))] \ \ \ (26)$$
の最小化と同じことであり,どれほどregularizationを強くするかの係数が$\lambda$であるのがわかりやすいので,(26)の記法がよく使われる.っている.