分類とカーネル — ロジスティック回帰とサポートベクトルマシン

2 つの記述子で表した点を 2 つのクラスに分ける境界を,データから引きます.①ではロジスティック回帰を勾配降下法で学習させ,交差エントロピー損失が下がる様子と,線形分離できるデータで正則化をなくすと重みが増え続ける様子を見ます.②ではカーネルと C,γ を変えて,SVM の境界・マージン・サポートベクトルがどう変わるかを見ます.どちらも,画面の数値を本文の式に入れて結果を説明できるかを確かめてください.

事後確率 p(y=1 | x) = σ(a) の濃淡と決定境界(p = 0.5)

ラベルは y ∈ {0, 1} です.図の上でポインターを動かすと,その点の a と p を下の式に入れて表示します.図をクリックすると,選んだクラスの点を足せます.

損失 L(交差エントロピー+正則化項)の推移.縦軸は対数.破線は Newton 法で求めた最小値 L*(存在するとき).

重みの大きさ ‖w‖(b を除く)の推移.線形分離できるデータで λ = 0 にすると増え続けます.

いまの数値を式に入れると

読み出し

このシミュレーターの説明(操作手順・式・条件・問い)

操作手順と観察する点

  1. ①を既定(重なりあり,N = 60,1 次の特徴,λ = 0.01,η = 0.01)のまま「実行」を押します.見る点:最初は w = 0,b = 0 なので全面が p = 0.5(損失 L = 60 ln 2 ≈ 41.6).反復が進むと境界が右下がりの直線に落ち着き,損失は Newton 法の最小値 L* ≈ 19.09 に近づきます(L − L* が読み出しに出ます).
  2. 図の上でポインターを動かすか,「調べる点」の欄に座標を入れます.見る点:「いまの数値を式に入れると」で,a = w1x1 + w2x2 + b と p = 1/(1 + e−a) の数値がつながること.a = 0 の点が境界(p = 0.5)で,境界までの符号付き距離は a/‖w‖ です.
  3. データを「線形分離できる」にし,「正則化なし(λ = 0)」に印を付けて「実行」します.見る点:訓練の正解率が 100 % になった後も,損失は 0 に向かって下がり続け,‖w‖ は増え続けること(境界の位置はほとんど変わらず,濃淡の移り変わりが急になる).読み出しには「最小値は有限の重みでは達成されない」と出ます.λ を 0.01 に戻すと ‖w‖ は有限の値で止まります.
  4. データを「同心円」にして,特徴を「1 次」と「2 次項つき」で比べます.見る点:1 次の特徴では境界が直線なので正解率が 6 割ほどにとどまり,2 次の項 x12,x1x2,x22 を足すと境界が閉じた曲線(楕円)になること.
  5. 学習率 η を「安定の目安」2/Lc より大きくして実行します.見る点:既定のデータでは目安は 2/Lc ≈ 0.097 です.η を 0.32 にすると,損失は 1 反復ごとに約 22.64 と 22.94 を行き来する振動に落ち込み,最小値 19.09 に届きません.目安より小さい η では損失は毎回減ります(目安は十分条件なので,超えても収束することはあります.このデータでは η = 0.25 でも収束します).
  6. ②を既定(三日月,RBF カーネル,C = 1,γ = 1)で見ます.見る点:境界 f = 0(実線)とマージン f = ±1(破線).○ の点(0 < αn < C)はちょうど破線の上にあり,◇ の点(αn = C)は破線の内側か反対側にあること.印のない点(αn = 0)は f(x) の和に入らないので,取り除いても境界は変わりません.
  7. γ と C を大きくします(たとえば γ = 20,C = 100).見る点:境界が個々の点を囲むように細かく曲がり,サポートベクトルの数が増えること(過学習).γ を小さくすると境界は直線に近づきます(ℓ = 1/√(2γ) が長くなる).
  8. カーネルを「線形」,データを「重なりあり」,C を 1000 にし,「反復の上限」を 100 にします.見る点:上限に達したことと,KKT 条件の破れ m − M が許容値より大きいことが表示され,主問題と双対問題の目的関数の差(双対ギャップ)が 0 から離れること.上限を 100000 に戻すと収束します.

キーボードでは Tab でボタンとスライダーへ移り,Enter(または Space)で押し,矢印キーでスライダーを動かせます.タブは ←→ で切り替えられます.図の上での操作(ポインター・クリック)は,「調べる点」の欄と「この位置に点を足す」ボタンでも同じことができます.

計算している式とアルゴリズム

① ロジスティック回帰(ラベル yn ∈ {0, 1}).特徴は 1 次なら φ(x) = (x1, x2)T,2 次項つきなら (x1, x2, x12, x1x2, x22)T です.

a=wTφ(x)+b,y^=p(y=1∣x)=σ(a)=11+e−aL(w,b)=−∑n=1N{ynlny^n+(1−yn)ln(1−y^n)}+λ2‖w‖2∇wL=∑n=1N(y^n−yn)φn+λw,∂L∂b=∑n=1N(y^n−yn)w←w−η∇wL,b←b−η∂L∂b

決定境界は a = 0(p = 0.5)です.1 次の特徴では境界は直線で,点 x から境界までの符号付き距離は a/‖w‖ です.損失の 1 項は σ(a) を経由せずに ln(1 + ea) − ya と書き直し,ln(1 + ea) を桁あふれしない形(a > 0 では a + ln(1 + e−a))で計算しています.b は正則化しません.

学習率の目安:L の勾配は Lc = ¼ λmax(ATA) + λ で Lipschitz 連続です(A は計画行列 Φ に 1 の列を足した行列,λmax は最大固有値).η < 2/Lc なら損失は反復ごとに減ります(十分条件).比較のための最小値 L* は,Hesse 行列 H = ATSA + λ diag(1, …, 1, 0)(S は ŷn(1 − ŷn) を並べた対角行列.最後の成分が b) を Cholesky 分解して Newton 法の方程式を解き(逆行列は作らない),直線探索をつけて求めています.λ = 0 で全点が境界の正しい側にあるときは,最小値は有限の重みでは達成されないと表示します.

② カーネル SVM(ラベル yn ∈ {−1, +1}).双対問題

maxαD(α)=∑n=1Nαn−12∑n=1N∑m=1Nαnαmynymk(xn,xm)制約:0≤αn≤C,∑n=1Nαnyn=0f(x)=∑n:αn>0αnynk(xn,x)+b

を解きます.カーネルは,線形 k = xTx′,多項式 k = (xTx′ + 1)d(d = 2, 3),RBF(Gauss)k = exp(−γ‖x − x′‖2) です.RBF は本文の σf2 exp(−‖x − x′‖2/(2ℓ2)) で σf = 1,γ = 1/(2ℓ2) としたものです.

KKT 条件(最適解であるための必要十分条件)は,各点で次のどれかです.

αn=0⇒ynf(xn)≥10<αn<C⇒ynf(xn)=1αn=C⇒ynf(xn)≤1

1 行目はサポートベクトルではない点,2 行目はマージンの上の点,3 行目はマージンの内側か誤分類の点です.画面の「KKT 条件の残差」は,各点でこの条件の破れ(αn = 0 なら max(0, 1 − ynfn),0 < αn < C なら |ynfn − 1|,αn = C なら max(0, ynfn − 1))の最大値です.b は 0 < αn < C の点で ynf(xn) = 1 となるように決め,それらの平均を取ります(そのような点が無いときは,KKT 条件が許す範囲の中点).

SMO(sequential minimal optimization)は,等式制約 Σαnyn = 0 を保つために 2 つの α を組にして選び,その 2 変数の問題を解析的に解いて箱 [0, C] に切り詰める,を繰り返します.組は「KKT 条件を最も破る点」と,それと組んだとき目的関数が最も改善する点です(LIBSVM と同じ選び方).Ft = Σs αsysk(xs, xt) − yt として,m(α) = max (−Ft)(ytαt を増やせる点),M(α) = min (−Ft)(減らせる点)とすると,KKT 条件は m ≤ M と同値です.m − M ≤ ε = 10−3 で止めます.

マージン幅=2‖w‖,
‖w‖2=∑n,mαnαmynymk(xn,xm)
P=12‖w‖2+C∑nmax(0,1−ynfn)≥D(α)

主問題の目的関数 P(ヒンジ損失の形)と双対の目的関数 D の差(双対ギャップ)は,最適解で 0 になります.

データと乱数の条件

  • 点はすべて教育用の合成データです.2 つの記述子 x1,x2(標準化した値,無次元)で表した試料を 2 クラスに分ける例(たとえば「ガラス化する/しない」)を想定していますが,実在の物質のデータではありません.点 n のクラスは偶奇で交互に決めます(n = 0, 2, 4, … が y = 0(②では −1),n = 1, 3, … が y = 1(②では +1)).ε は互いに独立な標準 Gauss 乱数です.
    • 線形分離できる:x = s(1, 1) + 0.7ε,s = +1(y = 1),−1(y = 0).s(x1 + x2)/√2 < 0.3 の点は引き直します(直線 x1 + x2 = 0 で,余裕をもって分けられることが保証されます).
    • 重なりあり:x = s(0.8, 0.8) + 1.0ε.
    • 同心円:x = r(cos θ, sin θ),θ ~ U(0, 2π),r = ry + 0.25ε,r0 = 1.0(内側),r1 = 2.2(外側).
    • 三日月:t ~ U(0, π),y = 0 では u = (cos t, sin t),y = 1 では u = (1 − cos t, 0.5 − sin t),x = 1.8{u − (0.5, 0.25)} + 0.22ε.
    • XOR:x = 1.2(a, c) + 0.55ε.a = ±1 を等確率で選び,y = 1 なら c = a,y = 0 なら c = −a.
  • 範囲 [−3.4, 3.4] の外に出た点は引き直します.図の範囲は両軸とも [−3.5, 3.5] です.
  • 乱数は seed つきの生成器(mulberry32)です.既定の seed は ①,② とも 20261112.同じ seed でやり直すと同じ点が出ます.データの型・データ数・seed を変えると,クリックで足した点は消えて作り直します.
  • 既定値:① 重なりあり,N = 60,1 次の特徴,λ = 0.01,η = 0.01,w = 0,b = 0 から開始.② 三日月,N = 60,RBF,C = 1,γ = 1,反復の上限 100000.
  • 計算量の上限:点は 300 個まで(生成は 10〜200 個),勾配降下法は 50000 反復まで,SMO は 100000 反復(2 変数の更新)まで.

簡略化している点

  • 入力は最初から標準化した値として作っています.実際のデータでは,ロジスティック回帰でも SVM でも記述子の標準化が必要です(特に RBF カーネルは距離を使うので単位に敏感です).
  • ロジスティック回帰はミニバッチを使わない勾配降下法(全データで勾配を計算)です.2 次項つきの特徴は標準化していないので,1 次より安定な学習率が小さくなります.
  • 訓練データの正解率だけを表示しています.C,γ,λ の選択に必要な検証データ・交差検証は扱っていません.
  • SVM の SMO は LIBSVM の作業集合の選び方と同じですが,shrinking(動かない変数を一時的に外す工夫)やキャッシュはありません.
  • SVM のスコアを確率に変換する方法(Platt のスケーリング)は入れていません.

結果が不安定になる条件

  • 学習率 η が 2/Lc より大きいと,損失が振動・増加し,重みが発散することがあります.‖w‖ が 106 を超えるか NaN・無限大が出たら計算を止めて理由を表示します.
  • 線形分離できるデータで λ = 0 にすると,損失の最小値は有限の重みでは達成されず,‖w‖ は反復とともに(ゆっくり,ほぼ対数的に)増え続けます.データが 1 クラスだけのときは b が発散します.
  • SVM は 2 クラスが 1 点ずつ以上ないと解けません(その旨を表示します).同じ位置に反対のクラスの点が重なると,ハードマージンに近い大きな C では解が αn = C に張り付きます.
  • 線形カーネルで重なりのあるデータに大きな C(100 以上)を使うと,SMO の収束がとても遅くなり,反復の上限に達することがあります.上限に達したら「反復の上限に達しました」と KKT 条件の残差を表示します(解は最適ではありません).
  • 双対ギャップ P − D には C × (ヒンジ損失の和) が入るので,C が大きいと,m − M が許容値以下でもギャップは大きめに残ります(停止の判定は m − M で行います).
  • 多項式カーネルでは xTx′ + 1 の 3 乗が大きな値(数百)になり,C が小さいと全点が αn = C になりやすくなります.

本文の対応節

操作後に答える短い問い

  1. ①の最初(w = 0,b = 0)の損失はいくつですか.データ数 N とどういう関係ですか.
    答えの例

    どの点でも a = 0,ŷ = 0.5 なので,1 点あたりの損失は −ln 0.5 = ln 2 ≈ 0.693 です.N = 60 なら L = 60 ln 2 ≈ 41.59(正則化項は 0).画面の t = 0 の値と一致します.

  2. 線形分離できるデータで λ = 0 のとき,正解率が 100 % になっても ‖w‖ が増え続けるのはなぜですか.λ > 0 にすると止まるのはなぜですか.
    答えの例

    全点が正しい側にあると,(w, b) を同じ向きのまま c 倍(c > 1)すると,どの点でも |an| が大きくなり,ŷn が正解のラベルに近づくので損失が必ず減ります.したがって損失は 0 に近づくだけで,最小値を与える有限の重みがありません.勾配降下法は損失を減らす向きに進み続けるので ‖w‖ が増え続けます(seed 20261112,η = 0.01 では 1000 反復で約 5.99,10000 反復で約 8.98).λ > 0 では (λ/2)‖w‖2 が ‖w‖ の 2 乗で増えるので,交差エントロピーの減少と釣り合う有限の点に最小値ができます(λ = 0.01 で ‖w‖ ≈ 6.75).

  3. ②で ○ の点(0 < αn < C)にポインターを合わせると,f(x) はおよそいくつですか.◇ の点(αn = C)ではどうですか.
    答えの例

    ○ の点はマージンの上にあるので ynf(xn) = 1,つまり y = +1 なら f ≈ +1,y = −1 なら f ≈ −1 です(停止の許容値のぶんだけずれます).◇ の点は ynf(xn) ≤ 1 で,マージンの内側(0 < yf < 1)か,境界の反対側(yf < 0,誤分類)にあります.どちらも f は確率ではないので,「f = 0.8 だから 80 %」とは読めません.

  4. ②の既定(三日月,RBF,C = 1)から γ を 1 → 20 にすると,サポートベクトルの数とマージン幅はどう変わりますか.それはなぜですか.
    答えの例

    既定(seed 20261112,N = 60)では,サポートベクトル 22 個(○ 18,◇ 4),マージン幅 0.581.γ = 20 では 59 個(○ 57,◇ 2),0.323 です(60 点のほぼ全部).γ が大きい(ℓ = 1/√(2γ) が短い)と,カーネルは近くの点どうしでしか値を持たず,f は各点のまわりの小さな山の重ね合わせになります.境界が個々の点に沿って曲がり,多くの点が境界の近くに残るのでサポートベクトルが増えます(訓練データに合わせすぎる=過学習).

機械学習 — 確率から GPT まで(目次)へ戻る | 本文:第9章 9.3 節,第10章 10.5 節,第11章 11.5 節 | 数式はブラウザ標準の MathML で組んでいます(外部ライブラリ不使用).