第2章線形モデル

この章の目標

• 線形回帰を直交射影として理解し、多重共線性が推定を不安定にする理由を特異値で説明できる
• リッジ回帰の閉形式を導き、特異値分解による縮小係数 $\sigma_i^2/(\sigma_i^2 + \lambda)$ で正則化の効果を説明できる
• 直交計画のラッソがソフト閾値で解けることを証明し、係数がちょうど $0$ になる理由を説明できる
• ロジスティック回帰とソフトマックス回帰の損失の勾配・ヘッセ行列を計算し、凸性を証明できる
• 標準化が必要な場面を見分け、評価指標を使い分けて、AUC の確率的解釈を証明できる

前提：第1章、02-linear-algebra 第7章（直交射影・最小二乗法）、02-linear-algebra 第8章（正定値性・特異値分解）、01-calculus 第7章（連鎖律・ヘッセ行列）、23-optimization 第2章（凸関数）。線形回帰の統計的推測は 22-statistics 第5章、ロジスティック回帰の最尤推定とニュートン法は 22-statistics 第6章、一般の計画行列でのラッソの解法は 23-optimization 第5章 で扱う。

予測関数を入力の 1 次式 $f(x) = w^{\top}x$ に限ったものを線形モデルという。計算と証明がすべて手の届く範囲にあり、ニューラルネットワークの最後の層やカーネル法（特徴空間での線形モデル）の部品でもあり、実務の最初の基準（ベースライン）としても欠かせない。「線形」はパラメータについての線形で、多項式やダミー変数を特徴量にすれば入力について非線形な関数も表せる。

記法. 第 $i$ 行が $x_i^{\top}$（$x_i \in \mathbb{R}^d$）の $n \times d$ 行列（計画行列, design matrix）を $X$、$y = (y_1, \dots, y_n)^{\top}$ とし、$X$ の第 $j$ 列を $x_{(j)}$ と書く（$P(Y = 1 \mid X = x)$ のような確率の式の中の $X$ は、第1章と同じく入力の確率変数である）。切片は値がつねに $1$ の特徴量として $w$ に含める。$A^{\top}$ は転置（02-linear-algebra の ${}^tA$）である。

2.1 線形回帰と射影

二乗損失の経験リスク $\frac{1}{n}\lVert y - Xw \rVert^2$ を最小にするのが最小二乗法（線形回帰）である。

定理 2.1（射影としての線形回帰）

1. $\hat{w}$ が $\lVert y - Xw \rVert^2$ を最小にするための必要十分条件は、正規方程式 $X^{\top}X\hat{w} = X^{\top}y$ である。最小点は必ず存在し、当てはめ値 $\hat{y} = X\hat{w}$ は最小点の選び方によらず、列空間 $\operatorname{Im}X$ への $y$ の直交射影に等しい。残差 $e = y - \hat{y}$ は $X$ のすべての列と直交する（$X^{\top}e = 0$）。
2. $\operatorname{rank}X = d$ ならば最小点は $\hat{w} = (X^{\top}X)^{-1}X^{\top}y$ ただ一つで、ハット行列 $H = X(X^{\top}X)^{-1}X^{\top}$ は $H^{\top} = H = H^2$、$\operatorname{tr}H = d$ を満たし、$\hat{y} = Hy$ である。
3. 最小点のうちノルムが最小のものは $X^{+}y$（$X^{+}$ はムーア–ペンローズ擬逆行列）である。

証明. (1) は 02-linear-algebra 第7章 定理 7.19 とその証明（最良近似の定理 7.17）である。(2) の式は定理 7.19 から従い、$H^2 = X(X^{\top}X)^{-1}(X^{\top}X)(X^{\top}X)^{-1}X^{\top} = H$、$\operatorname{tr}H = \operatorname{tr}((X^{\top}X)^{-1}X^{\top}X) = d$。(3) は 02-linear-algebra 第8章 定理 8.26 である。$\square$

$J(w) = \lVert y - Xw \rVert^2$ の勾配は $2X^{\top}(Xw - y)$、ヘッセ行列は半正定値な $2X^{\top}X$ なので $J$ は凸で、正規方程式は $\nabla J = 0$ にあたる。

以下、雑音の分散を $\sigma_\varepsilon^2$ と書き（特異値 $\sigma_i$ と区別するため）、$X$ の特異値分解（02-linear-algebra 第8章 定理 8.19）を $X = U\Sigma V^{\top} = \sum_{i=1}^{r}\sigma_iu_iv_i^{\top}$（$r = \operatorname{rank}X$、$\sigma_1 \geq \cdots \geq \sigma_r > 0$、$u_i, v_i$ は直交行列 $U, V$ の列）とする。$Xv_i = \sigma_iu_i$、$X^{\top}u_i = \sigma_iv_i$（$i \leq r$）である。

命題 2.2（最小二乗推定量の誤差）$y = Xw^{\ast} + \varepsilon$、$E[\varepsilon] = 0$、$\operatorname{Cov}(\varepsilon) = \sigma_\varepsilon^2 I_n$、$\operatorname{rank}X = d$ とすると、$E[\hat{w}] = w^{\ast}$、$\operatorname{Cov}(\hat{w}) = \sigma_\varepsilon^2(X^{\top}X)^{-1}$、$E\lVert \hat{w} - w^{\ast} \rVert^2 = \sigma_\varepsilon^2\sum_{i=1}^{d}\sigma_i^{-2}$。

証明. $\hat{w} - w^{\ast} = (X^{\top}X)^{-1}X^{\top}\varepsilon$ なので平均は $0$、共分散は $(X^{\top}X)^{-1}X^{\top}(\sigma_\varepsilon^2 I_n)X(X^{\top}X)^{-1} = \sigma_\varepsilon^2(X^{\top}X)^{-1}$ で、$E\lVert \hat{w} - w^{\ast} \rVert^2$ はそのトレースである。$X^{\top}X$ の固有値は $\sigma_i^2$ である。$\square$

特徴量の尺度をそろえても（2.6 節）なお小さな特異値があることは、特徴量どうしがほぼ 1 次従属であること（多重共線性, multicollinearity）を表し、推定は不偏でもその方向の誤差が非常に大きくなる（係数ごとの見方は 22-statistics 第5章 系 5.21 の分散拡大要因）。

例 2.3（相関の強い 2 つの特徴量）平均 $0$、分散 $1$ に標準化した 2 つの特徴量の相関係数が $0.98$、$n = 50$ なら、$X^{\top}X$ の対角成分は $50$、非対角成分は $49$ で、固有値は $\sigma_1^2 = 99$（固有ベクトル $v_1 = (1, 1)^{\top}/\sqrt{2}$）と $\sigma_2^2 = 1$（$v_2 = (1, -1)^{\top}/\sqrt{2}$）である。命題 2.2 の誤差 $\sigma_\varepsilon^2(1/99 + 1)$ の大部分は $v_2$ 方向、つまり係数の差 $w_1 - w_2$ の推定から来る。2 つの特徴量がほとんど同じ動きをするので、どちらがどれだけ効いているかを見分けられないのである。

2.2 リッジ回帰

定義 2.4（リッジ回帰, ridge regression）$\lambda > 0$ に対し、$J_\lambda(w) = \lVert y - Xw \rVert^2 + \lambda\lVert w \rVert^2$ を最小にする $\hat{w}_\lambda$ を求めることをリッジ回帰という。

定理 2.5（リッジ回帰の閉形式）$\lambda > 0$ ならば $A = X^{\top}X + \lambda I_d$ は正定値で、$J_\lambda$ の最小点は $\hat{w}_\lambda = A^{-1}X^{\top}y$ ただ一つである（$X$ の階数や $n, d$ の大小によらない）。さらに $J_\lambda(w) = J_\lambda(\hat{w}_\lambda) + (w - \hat{w}_\lambda)^{\top}A(w - \hat{w}_\lambda)$。

証明. $v \neq 0$ なら $v^{\top}Av = \lVert Xv \rVert^2 + \lambda\lVert v \rVert^2 > 0$ なので $A$ は正定値、特に正則である。$\hat{w} = A^{-1}X^{\top}y$ とおくと $X^{\top}y = A\hat{w}$ で、$A$ の対称性から

$w = \hat{w}$ とすれば等式を得て、$A$ の正定値性から $w \neq \hat{w}$ なら $J_\lambda(w) > J_\lambda(\hat{w})$。$\square$

定理 2.6（特異値分解による縮小）

$$\hat{w}_\lambda = \sum_{i=1}^{r}\frac{\sigma_i}{\sigma_i^2 + \lambda}(u_i^{\top}y)\,v_i, \qquad X\hat{w}_\lambda = \sum_{i=1}^{r}\frac{\sigma_i^2}{\sigma_i^2 + \lambda}(u_i^{\top}y)\,u_i$$

一方、最小二乗法の当てはめ値は $\hat{y} = \sum_{i=1}^{r}(u_i^{\top}y)u_i$、ノルム最小の最小二乗解は $X^{+}y = \sum_{i=1}^{r}\sigma_i^{-1}(u_i^{\top}y)v_i$ である。すなわちリッジ回帰は、最小二乗法の当てはめ値の $u_i$ 方向の成分を $\sigma_i^2/(\sigma_i^2 + \lambda)$ 倍に縮める。

証明. $A^{-1} = V(\Sigma^{\top}\Sigma + \lambda I_d)^{-1}V^{\top}$、$X^{\top}y = V\Sigma^{\top}U^{\top}y$ より $\hat{w}_\lambda = V(\Sigma^{\top}\Sigma + \lambda I_d)^{-1}\Sigma^{\top}U^{\top}y$ で、$d \times n$ 行列 $(\Sigma^{\top}\Sigma + \lambda I_d)^{-1}\Sigma^{\top}$ は $(i, i)$ 成分（$i \leq r$）が $\sigma_i/(\sigma_i^2 + \lambda)$、ほかは $0$ である。これで第 1 式を得て、$Xv_i = \sigma_iu_i$ から第 2 式を得る。$\hat{y}$ は $\operatorname{Im}X = \operatorname{span}(u_1, \dots, u_r)$ への直交射影 $\sum_{i \leq r}u_iu_i^{\top}y$ であり、$X^{+}y$ の式は擬逆行列の定義（02-linear-algebra 第8章 定義 8.24）による。$\square$

系 2.7

1. $\lambda \to +0$ で $\hat{w}_\lambda \to X^{+}y$、$\lambda \to \infty$ で $\hat{w}_\lambda \to 0$ であり、$\lVert \hat{w}_\lambda \rVert^2 = \sum_{i=1}^{r}\sigma_i^2(u_i^{\top}y)^2/(\sigma_i^2 + \lambda)^2$ は $\lambda$ について単調に減少する。
2. $H_\lambda = X(X^{\top}X + \lambda I_d)^{-1}X^{\top}$（$X\hat{w}_\lambda = H_\lambda y$）について $\operatorname{tr}H_\lambda = \sum_{i=1}^{r}\sigma_i^2/(\sigma_i^2 + \lambda)$。これを有効自由度 (effective degrees of freedom) という。

証明. 定理 2.6 から直ちに従う。(2) は $H_\lambda = \sum_{i \leq r}\frac{\sigma_i^2}{\sigma_i^2 + \lambda}u_iu_i^{\top}$ と $\operatorname{tr}(u_iu_i^{\top}) = \lVert u_i \rVert^2 = 1$ による。$\square$

有効自由度は最小二乗法のパラメータ数 $\operatorname{tr}H = d$ にあたり、$\lambda$ とともに $r$ から $0$ へ減る（第1章の問題 1.6 により訓練誤差の楽観性は $2\sigma_\varepsilon^2\operatorname{tr}H_\lambda/n$）。特徴量を中心化してあれば $\sigma_i^2/n$ は $v_i$ 方向（第3章の主成分の方向）のデータの分散であり、リッジ回帰はデータのばらつきが小さい方向ほど強く縮める。そこは最小二乗推定の分散 $\sigma_\varepsilon^2/\sigma_i^2$ が大きい方向であり（命題 2.2）、バイアスと引き換えにバリアンスを減らすのである。

定理 2.8（リッジ回帰の平均二乗誤差）$y = Xw^{\ast} + \varepsilon$、$E[\varepsilon] = 0$、$\operatorname{Cov}(\varepsilon) = \sigma_\varepsilon^2 I_n$、$\alpha_i = v_i^{\top}w^{\ast}$（$i = 1, \dots, d$）とすると

$$E\lVert \hat{w}_\lambda - w^{\ast} \rVert^2 = \sum_{i=1}^{r}\frac{\lambda^2\alpha_i^2 + \sigma_\varepsilon^2\sigma_i^2}{(\sigma_i^2 + \lambda)^2} + \sum_{i=r+1}^{d}\alpha_i^2$$

である。$\operatorname{rank}X = d$ のとき、右辺で $\lambda = 0$ とした値は最小二乗推定量の誤差 $\sigma_\varepsilon^2\sum_i\sigma_i^{-2}$ に等しく、$0 < \lambda \leq \sigma_\varepsilon^2/\max_i\alpha_i^2$（$w^{\ast} = 0$ なら任意の $\lambda > 0$）ならば $E\lVert \hat{w}_\lambda - w^{\ast} \rVert^2 < E\lVert \hat{w} - w^{\ast} \rVert^2$。

証明. $\lVert \hat{w}_\lambda - w^{\ast} \rVert^2 = \sum_{i=1}^{d}(v_i^{\top}\hat{w}_\lambda - \alpha_i)^2$。$i \leq r$ では $u_i^{\top}y = (X^{\top}u_i)^{\top}w^{\ast} + u_i^{\top}\varepsilon = \sigma_i\alpha_i + u_i^{\top}\varepsilon$ なので、定理 2.6 より

で、$E[u_i^{\top}\varepsilon] = 0$、$E[(u_i^{\top}\varepsilon)^2] = \sigma_\varepsilon^2$ より 2 乗の期待値は右辺の第 $i$ 項になる（$i > r$ では $v_i^{\top}\hat{w}_\lambda = 0$）。後半：$r = d$ とし、第 $i$ 項を $g_i(\lambda)$ とおくと $\sum_ig_i(0) = \sigma_\varepsilon^2\sum_i\sigma_i^{-2}$ は命題 2.2 の値である。$g_i'(\lambda) = 2\sigma_i^2(\lambda\alpha_i^2 - \sigma_\varepsilon^2)/(\sigma_i^2 + \lambda)^3$ なので、$\lambda_0 = \sigma_\varepsilon^2/\max_i\alpha_i^2$ とおくと $0 \leq \lambda < \lambda_0$ ですべての $g_i' < 0$ であり、$\sum_ig_i$ は $[0, \lambda_0]$ で狭義単調減少する（平均値の定理）。$w^{\ast} = 0$ ならすべての $\lambda \geq 0$ で $g_i' < 0$ である。$\square$

方向 $i$ ごとに見ると、$g_i$ は $\lambda = \sigma_\varepsilon^2/\alpha_i^2$（雑音と信号の比）で最小になる。定理 2.8 の $\lambda$ の範囲は十分条件であり、最小二乗に勝つ $\lambda$ の範囲全体ではない（例 2.9）。この結果は Hoerl と Kennard（1970 年）によるもので、22-statistics 第6章 定理 6.14 でも扱っている。

例 2.9（例 2.3 の続き）$\sigma_\varepsilon = 1$ なら最小二乗推定量の誤差は $1/99 + 1 \approx 1.0101$ である。$w^{\ast} = (1, 1)^{\top}$（$\alpha_1 = \sqrt{2}$、$\alpha_2 = 0$）なら定理 2.8 の値は $\lambda = 1$ で $0.2601$、$\lambda = 8$ で $0.0322$（最小は $\lambda \approx 8.3$）。$w^{\ast} = (1, -1)^{\top}$ なら $\lambda = 0.5$ で最小の $0.6767$、$\lambda = 8$ では $1.6012$ と最小二乗より悪い。最小二乗に勝つのは、$w^{\ast} = (1, 1)^{\top}$ なら $0 < \lambda < 242.8$、$w^{\ast} = (1, -1)^{\top}$ なら $0 < \lambda < 2.002$ のときで、どちらも定理 2.8 の十分条件 $\lambda \leq 0.5$ より広い（数値は計算機で確かめた）。最適な $\lambda$ も勝つ範囲も未知の $w^{\ast}$ によるので、実際には交差検証で選ぶ。

2.3 ラッソ

リッジ回帰は各方向を正の倍率で縮めるだけなので、係数がちょうど $0$ になることは偶然を除いて起こらない。効く特徴量が少数だと考えられるときは、係数の多くをちょうど $0$ にして特徴量を選びたい。

定義 2.10（ラッソ, lasso）$\lambda > 0$ に対し、$F_\lambda(w) = \frac{1}{2}\lVert y - Xw \rVert^2 + \lambda\lVert w \rVert_1$（$\lVert w \rVert_1 = \sum_j\lvert w_j \rvert$）を最小にする $\hat{w}$ を求めることをラッソという。

$F_\lambda(w) \leq F_\lambda(0)$ となる $w$ の集合は $\lambda\lVert w \rVert_1 \leq F_\lambda(0)$ を満たす有界閉集合なので、連続関数 $F_\lambda$ の最小点は存在する（01-calculus 第7章 定理 7.5・定理 7.7）。$F_\lambda$ は凸だが $w_j = 0$ で微分できず、最小点は一意とは限らない。

補題 2.11（ソフト閾値, soft thresholding）$z \in \mathbb{R}$、$\lambda \geq 0$ とすると、$g(t) = \frac{1}{2}(t - z)^2 + \lambda\lvert t \rvert$ の最小点はただ一つで、

$$S_\lambda(z) = \operatorname{sign}(z)\max(\lvert z \rvert - \lambda, 0) = \begin{cases} z - \lambda & (z > \lambda) \\ 0 & (\lvert z \rvert \leq \lambda) \\ z + \lambda & (z < -\lambda) \end{cases}$$

である。$S_\lambda$ をソフト閾値関数という。

証明. 平方完成すると

$z, t$ の符号を同時に変えても $g$ の形は変わらないので $z \geq 0$ としてよい。$t < 0$ では $t - (z + \lambda) < -(z + \lambda) \leq 0$ なので第 2 式の 2 乗の項は $t = 0$ のときより大きく、$g(t) > g(0)$。$z \leq \lambda$ なら、$t > 0$ でも $t - (z - \lambda) > \lambda - z \geq 0$ なので $g(t) > g(0)$ で、最小点は $0$ ただ一つ。$z > \lambda$ なら、$t \geq 0$ での最小点は $t = z - \lambda$ ただ一つで、$g(z - \lambda) = g(0) - \frac{1}{2}(z - \lambda)^2 < g(0)$ なので、これが全体の最小点である。$\square$

定理 2.12（直交計画のラッソ）$X^{\top}X = I_d$（列が正規直交）ならば、ラッソの最小点はただ一つで、最小二乗推定量 $z = X^{\top}y$ を使って $\hat{w}_j = S_\lambda(z_j)$（$j = 1, \dots, d$）と書ける。特に $\lvert z_j \rvert \leq \lambda$ なら $\hat{w}_j = 0$ である。

証明. $X^{\top}X = I_d$ より $\frac{1}{2}\lVert y - Xw \rVert^2 = \frac{1}{2}\lVert y \rVert^2 - w^{\top}z + \frac{1}{2}\lVert w \rVert^2 = \frac{1}{2}\lVert w - z \rVert^2 + \frac{1}{2}(\lVert y \rVert^2 - \lVert z \rVert^2)$ なので

各項は $w_j$ だけの関数なので、和の最小点は各項の最小点を並べたものであり、補題 2.11 から主張が従う。$\square$

例 2.13（3 種類の縮小）$X^{\top}X = I_d$、$z = (3, -0.5, 1.2, -2)$、$\lambda = 1$ とする。ラッソは $(2, 0, 0.2, -1)$ で、小さい成分を $0$ にし残りを $\lambda$ だけ $0$ に近づける。リッジ回帰は定理 2.5 より $z/(1 + \lambda) = (1.5, -0.25, 0.6, -1)$ で、すべてを同じ割合で縮める。$0$ でない成分の個数 $\lVert w \rVert_0$ への罰則 $\frac{1}{2}\lVert y - Xw \rVert^2 + \lambda\lVert w \rVert_0$ では、$\lvert z_j \rvert > \sqrt{2\lambda}$ の成分だけが残って $(3, 0, 0, -2)$ となる（ハード閾値。問題 2.1）。

一般の $X$ では閉じた式はないが、座標ごとにソフト閾値を繰り返す座標降下法や近接勾配法（23-optimization 第5章）で解ける。最小点の条件は、各 $j$ で「$\hat{w}_j \neq 0$ なら $x_{(j)}^{\top}(y - X\hat{w}) = \lambda\operatorname{sign}(\hat{w}_j)$、$\hat{w}_j = 0$ なら $\lvert x_{(j)}^{\top}(y - X\hat{w}) \rvert \leq \lambda$」である（23-optimization 第2章 定理 2.29 の劣勾配による最適性条件と例 2.28 の $\lVert w \rVert_1$ の劣微分から従う。証明は省く）。残差との内積の絶対値 $\lvert x_{(j)}^{\top}(y - X\hat{w}) \rvert$ が $\lambda$ より小さい特徴量の係数は $0$ になるのであり、特に $\hat{w} = 0$ となるのは $\lambda \geq \max_j\lvert x_{(j)}^{\top}y \rvert$ のときに限る（問題 2.4）。図形的には、ラッソの解は「$\lVert w \rVert_1 \leq t$ のもとで二乗誤差を最小にする」解でもあり（第1章の命題 1.21）、座標軸上に頂点をもつ $\ell^1$ 球に二乗誤差の等高線が最初に触れる点は、いくつかの座標が $0$ の頂点や面になりやすい。

2.4 ロジスティック回帰

2 値分類（$y \in \lbrace 0, 1 \rbrace$）で確率 $P(Y = 1 \mid X = x)$ を出したい。例 1.12 では、正規分布の 2 クラスで $\eta(x)$ が「1 次式をロジスティック関数に入れた形」になった。そこで、はじめからこの形を仮定する。ロジスティック関数 $\sigma(t) = 1/(1 + e^{-t})$（特異値 $\sigma_i$ とは無関係）は $\mathbb{R}$ から $(0, 1)$ への単調増加な全単射で、$1 - \sigma(t) = \sigma(-t)$、$\sigma'(t) = \sigma(t)(1 - \sigma(t))$ を満たす。

定義 2.14（ロジスティック回帰, logistic regression）モデル $P(Y = 1 \mid X = x) = \sigma(w^{\top}x)$ をロジスティック回帰という。スコア $t \in \mathbb{R}$ と $y \in \lbrace 0, 1 \rbrace$ に対するロジスティック損失（交差エントロピー損失）

$$\ell(y, t) = -y\log\sigma(t) - (1 - y)\log(1 - \sigma(t)) = \log(1 + e^{t}) - yt$$

の経験リスク $L(w) = \frac{1}{n}\sum_{i=1}^{n}\ell(y_i, w^{\top}x_i)$ を最小にして $w$ を求める。

二つ目の等号は $-\log\sigma(t) = \log(1 + e^{-t}) = \log(1 + e^{t}) - t$、$-\log(1 - \sigma(t)) = \log(1 + e^{t})$ による。$nL(w)$ はベルヌーイ分布のモデルの負の対数尤度なので、$L$ の最小化は最尤推定である（22-statistics 第6章）。

命題 2.15（ロジスティック損失は確率を当てる）$\eta \in (0, 1)$、$P(Y = 1) = \eta$ とすると、$h(t) = E[\ell(Y, t)] = \eta\log(1 + e^{-t}) + (1 - \eta)\log(1 + e^{t})$ は $\sigma(t) = \eta$ となる $t$ をただ一つの最小点にもつ。

証明. $h'(t) = -\eta(1 - \sigma(t)) + (1 - \eta)\sigma(t) = \sigma(t) - \eta$ は狭義単調増加で、$\sigma(t) = \eta$ でだけ $0$ になり、その左で負、右で正である。$\square$

第1章の補題 1.8 と合わせると、ロジスティック損失のリスクをすべての関数の中で最小にするスコア $t(x)$ は、$0 < \eta(x) < 1$ となる各 $x$ で $\sigma(t(x)) = \eta(x)$ を満たす。0-1 損失と違い、ロジスティック損失は確率そのものを正しく出すことを求めるのである（第7章の交差エントロピーにつながる）。ただし、$\eta(x)$ が $\sigma(w^{\top}x)$ の形でない（モデルが正しくない）ときや正則化したときは、学習した $\sigma(\hat{w}^{\top}x)$ が確率として正しい（較正されている）保証はない。

定理 2.16（勾配とヘッセ行列）$p_i = \sigma(w^{\top}x_i)$、$p = (p_1, \dots, p_n)^{\top}$、$D = \operatorname{diag}(p_1(1 - p_1), \dots, p_n(1 - p_n))$ とすると

$$\nabla L(w) = \frac{1}{n}\sum_{i=1}^{n}(p_i - y_i)x_i = \frac{1}{n}X^{\top}(p - y), \qquad \nabla^2L(w) = \frac{1}{n}\sum_{i=1}^{n}p_i(1 - p_i)x_ix_i^{\top} = \frac{1}{n}X^{\top}DX$$

証明. $\frac{\partial}{\partial t}\ell(y, t) = \sigma(t) - y$ と連鎖律（01-calculus 第7章 定理 7.14）より $\nabla_w\ell(y_i, w^{\top}x_i) = (\sigma(w^{\top}x_i) - y_i)x_i$。その第 $k$ 成分の勾配は $\sigma'(w^{\top}x_i)x_{ik}x_i$ なので、ヘッセ行列は $\sigma'(w^{\top}x_i)x_ix_i^{\top}$。$i$ について平均すればよい。$\square$

勾配は「（予測確率 − ラベル）× 入力」の平均で、二乗損失の $\nabla\frac{1}{2n}\lVert Xw - y \rVert^2 = \frac{1}{n}X^{\top}(Xw - y)$ と同じ形をしている。

定理 2.17（ロジスティック損失の凸性）$L$ は $\mathbb{R}^d$ 上の凸関数である。$L$ が狭義凸であるための必要十分条件は $\operatorname{rank}X = d$ である。

証明. $v^{\top}\nabla^2L(w)v = \frac{1}{n}\sum_ip_i(1 - p_i)(x_i^{\top}v)^2 \geq 0$ で、$0 < p_i < 1$ だから等号は $Xv = 0$ のときに限る。よってヘッセ行列はすべての $w$ で半正定値なので $L$ は凸であり、$\operatorname{rank}X = d$ ならすべての $w$ で正定値なので $L$ は狭義凸である（23-optimization 第2章 定理 2.15）。$\operatorname{rank}X < d$ なら $Xv = 0$ となる $v \neq 0$ について $L(w + tv) = L(w)$ がすべての $t$ で成り立つので、狭義凸でない。$\square$

証明が示すとおり、この同値はデータの位置やラベルによらずに成り立つ（$0 < p_i < 1$ がつねに成り立つため。対数尤度の凹性としての同じ主張が 22-statistics 第6章 定理 6.6 にある）。凸なので、勾配法やニュートン法（23-optimization 第5章・第6章）で得た停留点は大域的な最小点である（23-optimization 第2章 定理 2.19）。ニュートン法の更新 $w \leftarrow w - (X^{\top}DX)^{-1}X^{\top}(p - y)$ は 22-statistics 第6章 定理 6.7 の反復重み付き最小二乗法（IRLS）と同じものである。ただし、凸でも、狭義凸でも、最小点があるとは限らない。

命題 2.18（線形分離できるときの発散）$\tilde{y}_i = 2y_i - 1$ とし、すべての $i$ で $\tilde{y}_iw_0^{\top}x_i > 0$ となる $w_0$ がある（訓練データが超平面で完全に分けられる）とする。このとき $\inf_wL(w) = 0$ だが、すべての $w$ で $L(w) > 0$ なので、$L$ は最小点をもたない。$L(w_k) \to 0$ となる列では $\lVert w_k \rVert \to \infty$ である。

証明. $\ell(y_i, t) = \log(1 + e^{-\tilde{y}_it})$ なので、$c \to \infty$ で $L(cw_0) = \frac{1}{n}\sum_i\log(1 + e^{-c\tilde{y}_iw_0^{\top}x_i}) \to 0$ で、各項は正である。$L(w_k) \to 0$ なら各項が $0$ に近づくので $\tilde{y}_iw_k^{\top}x_i \to \infty$ で、$\tilde{y}_iw_k^{\top}x_i \leq \lVert w_k \rVert\lVert x_i \rVert$ より $\lVert w_k \rVert \to \infty$。$\square$

このとき勾配法は係数を際限なく大きくし、予測確率は $0$ か $1$ に張りつく。$\operatorname{rank}X = d$ のとき、最小点が存在するための必要十分条件は、完全な分離も、すべての $i$ で $\tilde{y}_iv^{\top}x_i \geq 0$ となる $v \neq 0$ がある「準完全分離」も起きていないことである（22-statistics 第6章 定理 6.11）。特徴量が多くデータが少ないと線形分離は起こりやすいが、罰則 $\frac{\lambda}{2}\lVert w \rVert^2$ を加えれば最小点はつねにただ一つ存在する（問題 2.5）。

2.5 多クラス分類とソフトマックス

定義 2.19（ソフトマックス回帰）クラスが $\lbrace 1, \dots, K \rbrace$ のとき、$W = (w_1, \dots, w_K) \in \mathbb{R}^{d \times K}$ のスコア $z = W^{\top}x$ から、ソフトマックス関数 $\operatorname{softmax}(z)_k = e^{z_k}/\sum_{j=1}^{K}e^{z_j}$ で $P(Y = k \mid X = x)$ をモデル化する。損失は交差エントロピー $\ell(y, z) = -\log\operatorname{softmax}(z)_y = \log\sum_{j}e^{z_j} - z_y$ である。

命題 2.20 $p = \operatorname{softmax}(z)$ とし、$e_y$ を第 $y$ 成分が $1$ の単位ベクトルとする。

1. 任意の $c \in \mathbb{R}$ で $\operatorname{softmax}(z + c\mathbf{1}) = \operatorname{softmax}(z)$。$K = 2$ では $\operatorname{softmax}(z)_1 = \sigma(z_1 - z_2)$ で、ロジスティック回帰（$w = w_1 - w_2$）に一致する。
2. $\nabla_z\ell(y, z) = p - e_y$、$\nabla_z^2\ell(y, z) = \operatorname{diag}(p) - pp^{\top}$ で、これは半正定値である。したがって経験リスクは $W$ について凸であり、$\nabla_{w_k}\ell(y, W^{\top}x) = (p_k - \mathbf{1}\lbrace y = k \rbrace)x$。

証明. (1) 分母と分子に $e^{c}$ がかかるだけであり、$K = 2$ では $e^{z_1}/(e^{z_1} + e^{z_2}) = 1/(1 + e^{-(z_1 - z_2)})$。(2) $\partial_{z_k}\log\sum_je^{z_j} = p_k$、$\partial_{z_l}p_k = p_k(\mathbf{1}\lbrace k = l \rbrace - p_l)$ から勾配とヘッセ行列を得る。$u^{\top}(\operatorname{diag}(p) - pp^{\top})u = \sum_kp_ku_k^2 - (\sum_kp_ku_k)^2$ は、確率 $p_k$ で値 $u_k$ をとる確率変数の分散なので $0$ 以上である。$z = W^{\top}x$ は $W$ の 1 次式なので、凸関数との合成とその和は凸である。$w_k$ による勾配は、$z_k = w_k^{\top}x$ だけが $w_k$ によることと連鎖律から従う。$\square$

(1) から、すべての $w_k$ に同じベクトルを足しても予測は変わらないので、経験リスクは $W$ について狭義凸にならない（$w_K = 0$ と固定するか罰則を加える）。計算では $e^{z_j}$ のあふれ（$z_j = 1000$ など）を避けるため、$m = \max_jz_j$ を引いて $\log\sum_je^{z_j} = m + \log\sum_je^{z_j - m}$ とする。