NIPS 2010 論文読み会 / [Ding+] t-Logistic Regression #nipsreading

機械学習 NIPS
この記事は NIPS 2010 読み会 用の資料です。

今回読む論文

参照論文

  • [Naudts 2004] Estimators, escort proabilities, and Φ-exponential families in statistical physics.
    • [ABE 2003] Geometry of escort distributions.
  • [Sears 2008] Generalized Maximum Entropy, Convexity, and Machine Learning.
  • [Kuno+ 1993] An outer approximation method for minimizing the product of several convex functions on a convex set.

2. Logistic Regression

  • x_i: samples, y_i ∈ {-1, +1}: labels, φ:feature map
    • \phi({\boldsymbol x},y)=\frac{1}{2}y\phi({\boldsymbol x}) とおく
  • ({\boldsymbol X},{\boldsymbol Y})=\{({\boldsymbol x}_1,y_1),\cdots,({\boldsymbol x}_m,y_m)\} : i.i.d. dataset
  • p(y|{\boldsymbol x};{\boldsymbol \theta})=\exp\{<\phi({\boldsymbol x},y),{\boldsymbol \theta}>-g({\boldsymbol \theta}|{\boldsymbol x})\}
    • θでパラメータ付けされた条件付分布
  • where g({\boldsymbol \theta}|{\boldsymbol x})=\log\{\exp(<\phi({\boldsymbol x},+1),{\boldsymbol \theta}>)+\exp(<\phi({\boldsymbol x},-1),{\boldsymbol \theta}>)\}
    • 対数分配(log-partition)関数
  • p({\boldsymbol \theta}|{\boldsymbol X},{\boldsymbol Y})=p({\boldsymbol \theta})\prod_{i=1}^{m}p(y_i|{\boldsymbol x}_i;{\boldsymbol \theta})/p({\boldsymbol Y}|{\boldsymbol X})
    • 事後分布
  • p(y|{\boldsymbol x};{\boldsymbol \theta})=\frac{\exp(u/2)}{\exp(u/2)+\exp(-u/2)}=\frac{1}{1+\exp(-u)}
    • where マージン u=y<\phi({\boldsymbol x}),{\boldsymbol \theta}>
  • このときθの事前分布に正規分布 \mathcal{N}(0,\frac{1}{\sqrt{\lambda}}{\boldsymbol I}) を設定すると、事後分布の負の対数は
  • -\log p({\boldsymbol \theta}|{\boldsymbol X},{\boldsymbol Y})=\frac{\lambda}{2}|\theta|^2+\sum_{i=1}^m\log\{1+\exp(-y_i<\phi({\boldsymbol x}_i),{\boldsymbol \theta}>)\}+\rm{const}
    • 第１項は正則化項
    • 第２項は損失関数の和
  • 一般的な LR では、この事後分布についてθに関するMAP推定を行う

3. t-Exponential family of Distribution

  • \exp_t(x) =\begin{cases}\exp(x) & \text{if}\;t=1 \\ [1+(1-t)x]_{+}^{1/(1-t)} & \text{otherwise}\end{cases}
    • where (\cdot)_{+}=\max(\cdot,0)
  • パラメータ t (0<t<2) を入れて指数関数を拡張したもの
    • 通常の exp と異なり、\exp_t(a+b)\neq\exp_t(a)\exp_t(b)
    • y=\exp_t(x) とおくと、\frac{dy}{dx}=y^t
  • \begin{equation}\log_t(x)=\begin{cases}\log(x) & \rm{if}\;t=1 \\\frac{x^{1-t}-1}{1-t} & \text{otherwise}\end{cases}\end{equation}
exp_t のグラフ

  • 1<t<2 のとき、exp_t は exp よりゆっくり 0 に向かう
    • heavy tail distribution やベキ分布の表現に使える
    • 今後、1<t<2 、特に t=1.9 を主に想定
t-指数型分部族

指数型分部族のアナロジーから t-指数型分部族を定義

  • p({\boldsymbol x};{\boldsymbol \theta})=\exp_t\{<\phi({\boldsymbol x}),{\boldsymbol \theta}>-g_t({\boldsymbol \theta})\}
    • where g_t({\boldsymbol \theta}) : 対数分配関数(log-partition, 確率分布を正規化する、θによって決まる定数)
    • 一般に g_t(θ) の closed form を exact に求めることは出来ない
Student の t-分布は t-指数型分部族
  • St(x|μ,Σ,v): 平均μ, 共分散Σ, 自由度 v の Student t-分布
  • t, φ, θ, g_t を適切に定めると、St(x|μ,Σ,v) は次のように書き直すことができる
  • St({\boldsymbol x}|{\boldsymbol \mu},{\boldsymbol \Sigma},v)=\exp_t\{<\phi({\boldsymbol x}),{\boldsymbol \theta}>-g_t({\boldsymbol \theta})\}
    • where \phi({\boldsymbol x})=[{\boldsymbol x};{\boldsymbol x}{\boldsymbol x}^T],
    • {\boldsymbol \theta}=[-2\Psi{\boldsymbol K}{\boldsymbol \mu}/(1-t);\Psi{\boldsymbol K}/(1-t)],
    • {\boldsymbol K}=(v{\boldsymbol \Sigma})^{-1},
    • ΨはΣ,v,次元で決まる定数
  • 詳しくは論文の Appendix A 参照
エスコート分布 [Naudts][Abe][Sears]
  • 分布 p(x;θ) に対し、その escort 分布 q_t(x;θ) として q_t({\boldsymbol x},{\boldsymbol \theta})=p({\boldsymbol x},{\boldsymbol \theta})^t/Z({\boldsymbol \theta}) をとる
    • Z(θ) は正規化定数
  • 非指数型(非加法性)など扱いにくい分布に対し、(ある種双対な分布としての?) "escort 分布" を通じて取り扱う方法を提供
    • escort 分布のコンセンサスのとれた定式化はまだなさそう？(論文によって導入が異なる)
    • escort 分布として p^t/Z を考えるのは、Boltzmann-Gibbs エントロピーの拡張としての Tsallis エントロピーを考えることに相当
(参考) Tsallis エントロピー (Tsallis 1988)
  • S_q(p)=\frac{1}{q-1}\left(1-\int f(x)^q dx\right)
    • q→1 のとき Shannon entropy S_1(p)=-\int f(x)\log f(x) dx に一致
    • 温度や圧力など、非示量性(nonextensive, 系全体の量が部分系の量の和に一致しない)な状態量のモデル化に用いられる
  • p(A,B)=p(A)p(B) のとき、S_q(A,B)=S_q(A)+S_q(B)+(1-q)S_q(A)S_q(B)
    • log_t と同じ擬加法性
    • q→1 のときは、通常の加法性を示す
  • Tsallis エントロピーを最大化する分布として Tsallis 分布(q-指数型分布族)が得られる
定理 1 (Appendix B)[Sears][Naudts]

分配関数 g_t(θ) について、以下が成り立つ

  • g_t(θ) は凸関数である。
  • 分布 p(x;θ) が正則条件 \int\nabla_{{\boldsymbol \theta}}p({\boldsymbol x};{\boldsymbol \theta})d{\boldsymbol x}=\nabla_{{\boldsymbol \theta}}\int p({\boldsymbol x};{\boldsymbol \theta})d{\boldsymbol x} を満たすなら、\nabla_{{\boldsymbol \theta}}g_t({\boldsymbol \theta})=\mathbb{E}_{q_t({\boldsymbol x};{\boldsymbol \theta})}[\phi({\boldsymbol x})] が成り立つ。ここで q_t(x;θ) は p(x;θ) のエスコート分布である。
    • 普通の指数型分布族なら、E_qt を E_p に置き換えたものが成立する(PRML 2.226)

4. Binary Classification with the t-exponential family

t-ロジスティック回帰を定式化する。

  • p(y|{\boldsymbol x};{\boldsymbol \theta})=\exp_t\{<\phi({\boldsymbol x},y),{\boldsymbol \theta}>-g_t({\boldsymbol \theta}|{\boldsymbol x})\}
    • 条件付き分布を t-指数関数によってモデル化
    • ここでは 1<t<2 を考える
  • g_t はこれを正規化するので、\exp_t\{<\phi({\boldsymbol x},+1),{\boldsymbol \theta}>-g_t({\boldsymbol \theta}|{\boldsymbol x})\}+\exp_t\{<\phi({\boldsymbol x},-1),{\boldsymbol \theta}>-g_t({\boldsymbol \theta}|{\boldsymbol x})\}=1 を満たす
    • closed form は求められない！　→　実験では、いくつかの点について数値解を求め、その間はスプライン補完によって計算
Student's t-prior

θの事前分布にt-分布を入れる

  • t を -\frac{v+1}{2}=\frac{1}{1-t} を満たすように選ぶ
    • 自由度 v=\frac{3-t}{t-1}
    • このとき v>1 ⇔ 1<t<2
  • Student t-分布は t-指数型分布族
    • したがって St(x|\mu,\sigma,v)=\exp_t\{-\frac{\tilde{\lambda}}{2}(x-\mu)^2-\tilde{g}_t\} と書き直せる
    • \tilde{\lambda},\;\tilde{g}_t は適切に定義(詳細は論文参照)
  • これを使って、等方性の事前分布を次のように設定する
  • p({\boldsymbol \theta})=\prod_{j=1}^d p(\theta_j)=\prod_{j=1}^d St\left(\theta_j|0,\frac{2}{\tilde{\lambda}},\frac{3-t}{t-1}\right)
likelihood
  • LR と同様に log-likelihood を考えても、凸損失関数は得られない
  • Student t-事前分布に対する -log p(θ)、つまり正則化項も凸ではない
    • ↓↓↓
  • log_t は単調増加関数ゆえ、log_t-likelihood を最小化すればよい
  • \hat{J}({\boldsymbol \theta})=-\log_t p({\boldsymbol \theta})\prod_{i=1}^{m}p(y_i|{\boldsymbol x}_i;{\boldsymbol \theta})/p({\boldsymbol Y}|{\boldsymbol X})
  • \hspace{4ex}=C\prod_{j=1}^d r_j({\boldsymbol \theta})\prod_{i=1}^m l_i({\boldsymbol \theta})+\frac{1}{1-t} (C>0)
    • ただし r_j({\boldsymbol \theta})=1+(1-t)\left(-\frac{\tilde{\lambda}}{2}\theta_j^2-\tilde{g}_t\right)
    • l_i({\boldsymbol \theta})=1+(1-t)\left(<\frac{y_i}{2}\phi({\boldsymbol x}_i),{\boldsymbol \theta}>-g_t({\boldsymbol \theta}|x_i)\right)
  • r_j, l_j ともに凸ゆえ、凸関数の積を最小化する問題に帰着できることがわかる
t-Logistic Regression の損失関数
  • t=1.9 での損失関数は normal LR のものよりペナルティが小さい
    • 頑健性

5. Convex Multiplicative Programming

  • P({\boldsymbol \theta})=\prod_{n=1}^N z_n({\boldsymbol \theta}),\;\;\rm{where}\;{\boldsymbol \theta}\in\mathbb{R}^d,\;z_n:\rm{convex}
  • P(θ) の最小化には、以下の定理を用いる[Kuno+ Theorem 2.1]

MP({\boldsymbol \theta},{\boldsymbol \xi})=\sum_{n=1}^N \xi_n z_n({\boldsymbol \theta}) を \xi_n>0,\;\prod_{n=1}^N \xi\geq 1 という制約下で最小化したときの最適解 ({\boldsymbol \theta}^*,{\boldsymbol \xi}^*) で、{\boldsymbol \theta}^* が P(θ) の最適解であるようなものが存在する。

  • [Kuno+] では exact algorithm が紹介されているが、次元>4 あたりから厳しい(指数オーダー)
    • →ξとθについて交互に最小化していく
  • 以下のξstep とθステップを繰り返すことで、勾配が0になる点に収束する(Appendix C)
ξstep
  • θを固定。\bar{z}_n=z_n({\boldsymbol \theta}) と書くと、
  • \xi_n>0,\; \prod_n \xi_n \geq 1 という制約条件の下で \sum_n \xi_n\bar{z}_n を最小化すればよい
  • {\boldsymbol \xi}=(\gamma/\bar{z}_1, \cdots,\gamma/\bar{z}_N),\;\; \rm{where} \gamma=\prod_n \bar{z}_n^{\frac{1}{N}} を得る。
    • z_n が大きくなれば、 influence たる ξ_n は小さくなる。つまり大きい損失を持つサンプルは影響が少ない(robust)
θstep
  • ξを固定して、- \sum \xi_n z_n({\boldsymbol \theta}) をθについて最小化。
    • 凸関数の正係数線形結合ゆえ、これも凸関数。つまり制約無しの凸関数最適化問題なので、適当な手法で解ける
    • 本論文の実験では L-BFGS を用いているが、それには z_n (つまり r_j と l_i)の勾配が必要。
  • \nabla_{{\boldsymbol \theta}}r_j({\boldsymbol \theta})=(t-1)\tilde{\lambda}\theta_j\cdot{\boldsymbol e}_j
    • ただし e_j は j 番目の要素のみ 1、それ以外は 0 のベクトル
  • \nabla_{{\boldsymbol \theta}}l_i({\boldsymbol \theta})=(1-t)\left(\frac{y_i}{2}\phi({\boldsymbol x}_i)-\mathbb{E}_{q_t(y_i|{\boldsymbol x}_i;{\boldsymbol \theta})}[\frac{y_i}{2}\phi({\boldsymbol x}_i)]\right)
    • 途中 ∇g_t が現れるが、定理 1 により E_q に置き換わる
    • -\frac{y_i}{2}\phi({\boldsymbol x}_i) の bias が現れている

6. 実験

  • 6つのデータセット(Long-Servedio, Mease-Wyner, Mushroom, USPS-N, Adult, Web)
    • 次元:21〜300、サンプル数:2000〜60000
    • ランダムに選んだ 30% を validation set に
  • t-Logistic Regression(t=1.3, 1.6, 1.9) で 10-fold CV
    • 大きいほど頑健であることを期待
  • baselines:
    • normal Logistic Regression
    • probit loss in BrownBoost/RobustBoost
    • linear SVM
  • label noise なし(青)、10% の label noise(赤)
  • ノイズなしでは LR, SVM, t=1.3 あたりが良い感じ
  • ノイズありでは、左下(USPS-N)の probit が若干勝っている以外は、全て t=1.9 がエラー最少
    • データ件数が多ければ、linear SVM でもそんなに悪くない……？
  • ノイズが増えると安定しない？
    • label noise が 30% もあるってどんな状況？
  • 計算量のオーダーは LR くらい？
  • probit はええ。
  • RampSVM (Collobert+ 2006) も使いたかったが、うまく動かせなかったらしい。

まとめ

  • t-指数型分部族 への拡張により t-ロジスティック回帰を考える
    • 一定の robust 性を確保
    • 分配関数の計算回りはもうちょっとすっきりした方法が欲しいかも
  • 「t-conditional random field とかもおもしろそう」(7. Discussion and Outlook)
    • 確かにおもしろそうかも
    • でも maxent + t-指数族ってどうなんだろう？＜ 二値 LR は MaxEnt と同値だよ！(by tsubosaka)
    • maxent + Tsallis エントロピー で t-指数族 が出てくるんだから……