IndexPosts

Famous Dimensionality Reduction Methods

Daiki Okayama,•machine-learningdimensionality-reduction

手法のまとめ

手法名特徴
主成分分析 (PCA)変数間の従属性が高ければ、より少数の主成分で元データを表現できる
非負値行列因子分解 (NMF)非負データにしか使えないが、非負ベクトルの和の形で表現できる

なぜ次元削減が必要か？

主成分分析 (PCA)

[Questions]

[Keywords]

多次元データのもつ情報をできるだけ損なわずに低次元空間に情報を縮約する手法。

mm 個の特徴量のデータが nn 点存在するとし、行列 X\boldsymbol{X} と各データ点に対応するベクトル xi=(xi1,xi2,…,xim) (i=1,2,…n)\boldsymbol{x}_i=(x_{i1}, x_{i2}, \ldots{}, x_{im}) \space{} (i=1,2,\ldots{n}) を用いて与えられるとする。

X=(x11x12…x1mx21x22…x2m⋮⋮⋱⋮xn1xn2…xnm)=(x1x2⋮xn)\boldsymbol{X} = \begin{pmatrix} x_{11} & x_{12} & \dots{} & x_{1m} \\ x_{21} & x_{22} & \dots{} & x_{2m} \\ \vdots{} & \vdots{} & \ddots{} & \vdots{} \\ x_{n1} & x_{n2} & \dots{} & x_{nm} \\ \end{pmatrix} = \begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \\ \vdots{} \\ \boldsymbol{x}_n \\ \end{pmatrix}

mm 個の正規直交基底 v1,v2,…,vm∈Rm\boldsymbol{v}_1,\boldsymbol{v}_2,\ldots{},\boldsymbol{v}_m \in \R^m を用いて元データを近似することを考えたい。

具体的には、

X=(x1x2⋮xn)=(t11v1+t12v2+⋯+t1mvmt21v1+t22v2+⋯+t2mvm⋮tn1v1+tn2v2+⋯+tnmvm)≈(t11v1+t12v2+⋯+t1kvkt21v1+t22v2+⋯+t2kvk⋮tn1v1+tn2v2+⋯+tnkvk)\boldsymbol{X} = \begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \\ \vdots{} \\ \boldsymbol{x}_n \\ \end{pmatrix} = \begin{pmatrix} t_{11}\boldsymbol{v}_1 + t_{12}\boldsymbol{v}_2 + \cdots{} + t_{1m}\boldsymbol{v}_m \\ t_{21}\boldsymbol{v}_1 + t_{22}\boldsymbol{v}_2 + \cdots{} + t_{2m}\boldsymbol{v}_m \\ \vdots{} \\ t_{n1}\boldsymbol{v}_1 + t_{n2}\boldsymbol{v}_2 + \cdots{} + t_{nm}\boldsymbol{v}_m \\ \end{pmatrix} \approx{} \begin{pmatrix} t_{11}\boldsymbol{v}_1 + t_{12}\boldsymbol{v}_2 + \cdots{} + t_{1k}\boldsymbol{v}_k \\ t_{21}\boldsymbol{v}_1 + t_{22}\boldsymbol{v}_2 + \cdots{} + t_{2k}\boldsymbol{v}_k \\ \vdots{} \\ t_{n1}\boldsymbol{v}_1 + t_{n2}\boldsymbol{v}_2 + \cdots{} + t_{nk}\boldsymbol{v}_k \\ \end{pmatrix}

のように、mm 個の正規直交基底のうち、k (<m)k \space{} (\lt{} m) 個の正規直交基底を利用して各データ点を近似する。このとき、vj\boldsymbol{v}_j を第 jj 主成分軸、tijt_{ij} をデータ点 xi\boldsymbol{x}_i の第 jj 主成分軸における主成分得点と呼ぶ。(tijt_{ij} は主成分軸の基底 vjv_j が決まれば求められることに注意)

pca

主成分軸の算出

結論から述べると、特徴量の共分散行列 S\boldsymbol{S} に対する固有値問題を解くことで主成分軸は求められる。

ここで、共分散行列 S\boldsymbol{S} は、

S=1n(∑i=1nxi12∑i=1nxi1xi2⋯∑i=1nxi1xim∑i=1nxi2xi1∑i=1nxi22⋯∑i=1nxi2xim⋮⋮⋱⋮∑i=1nximxi1∑i=1nximxi2⋯∑i=1nxim2)=1n(x11x21…xm1x12x22…xm2⋮⋮⋱⋮x1nx2n…xmn)(x11x12…x1mx21x22…x2m⋮⋮⋱⋮xn1xn2…xnm)=1nXTX\begin{aligned} \boldsymbol{S} &= \frac{1}{n} \begin{pmatrix} \sum_{i=1}^{n} x_{i1}^2 & \sum_{i=1}^{n} x_{i1}x_{i2} & \cdots{} & \sum_{i=1}^{n} x_{i1}x_{im}\\ \sum_{i=1}^{n} x_{i2}x_{i1} & \sum_{i=1}^{n} x_{i2}^2 & \cdots{} & \sum_{i=1}^{n} x_{i2}x_{im}\\ \vdots{} & \vdots{} & \ddots{} & \vdots{} \\ \sum_{i=1}^{n} x_{im}x_{i1} & \sum_{i=1}^{n} x_{im}x_{i2} & \cdots{} & \sum_{i=1}^{n} x_{im}^2\\ \end{pmatrix} \\ &= \frac{1}{n} \begin{pmatrix} x_{11} & x_{21} & \dots{} & x_{m1} \\ x_{12} & x_{22} & \dots{} & x_{m2} \\ \vdots{} & \vdots{} & \ddots{} & \vdots{} \\ x_{1n} & x_{2n} & \dots{} & x_{mn} \\ \end{pmatrix} \begin{pmatrix} x_{11} & x_{12} & \dots{} & x_{1m} \\ x_{21} & x_{22} & \dots{} & x_{2m} \\ \vdots{} & \vdots{} & \ddots{} & \vdots{} \\ x_{n1} & x_{n2} & \dots{} & x_{nm} \\ \end{pmatrix} \\ &= \frac{1}{n} \boldsymbol{X}^T\boldsymbol{X} \end{aligned}

とかける。

各データ点を第 jj 主成分軸に射影した点 t1j,…,tnjt_{1j}, \ldots{}, t_{nj} の分散を最大化することを考えたい。

xi\boldsymbol{x}_i と vj\boldsymbol{v}_j の内積がデータ点 xi\boldsymbol{x}_i の主成分軸 vj\boldsymbol{v}_j への射影になる、つまり xi⋅vj=tij\boldsymbol{x}_i\cdot{}\boldsymbol{v}_j = t_{ij} であることを踏まえれば、射影した点 t1j,…,tnjt_{1j}, \ldots{}, t_{nj} の分散は次式のように計算できる。

1n∑i=1ntij2=1n∑i=1n(xi⋅vj)2=1n(x1⋅vjx2⋅vj⋯xn⋅vj)(x1⋅vjx2⋅vj⋯xn⋅vj)T=1n((x1x2⋮xn)vj)T((x1x2⋮xn)vj)=1n(Xvj)T(Xvj)=1nvjTXTXvj=vjTSvj\begin{aligned} \frac{1}{n}{\sum_{i=1}^{n}{t_{ij}^2}} &= \frac{1}{n}{\sum_{i=1}^{n}{(\boldsymbol{x}_i\cdot{}\boldsymbol{v}_j)^2}} \\ &= \frac{1}{n} \begin{pmatrix} \boldsymbol{x}_1 \cdot{} \boldsymbol{v}_j & \boldsymbol{x}_2 \cdot{} \boldsymbol{v}_j & \cdots{} & \boldsymbol{x}_n \cdot{} \boldsymbol{v}_j \end{pmatrix} \begin{pmatrix} \boldsymbol{x}_1 \cdot{} \boldsymbol{v}_j & \boldsymbol{x}_2 \cdot{} \boldsymbol{v}_j & \cdots{} & \boldsymbol{x}_n \cdot{} \boldsymbol{v}_j \end{pmatrix}^T \\ &=\frac{1}{n} \left( \begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \\ \vdots{} \\ \boldsymbol{x}_n \\ \end{pmatrix} \boldsymbol{v}_j \right)^T \left( \begin{pmatrix} \boldsymbol{x}_1 \\ \boldsymbol{x}_2 \\ \vdots{} \\ \boldsymbol{x}_n \\ \end{pmatrix} \boldsymbol{v}_j \right) \\ &= \frac{1}{n} \left(\boldsymbol{X}\boldsymbol{v}_j\right)^T \left(\boldsymbol{X}\boldsymbol{v}_j\right) \\ &= \frac{1}{n} \boldsymbol{v}_j^T\boldsymbol{X}^T\boldsymbol{X}\boldsymbol{v}_j \\ &= \boldsymbol{v}_j^T\boldsymbol{S}\boldsymbol{v}_j \end{aligned}

よって、ある主成分軸 jj への射影後の各データ点の分散を最大化するには、vjTSvj\boldsymbol{v}_j^T\boldsymbol{S}\boldsymbol{v}_j を最大化すればよいことが分かる。

特に、正規直交基底として ∣vj∣2=1|\boldsymbol{v}_j|^2 = 1 を仮定していたので、この問題は制約付き最大化問題としてラグランジュの未定乗数法を用いて解くことができる。

要するに、

max.vjTSvjs.t.vjTvj=1\begin{aligned} \text{max.} &\quad{} \boldsymbol{v}_j^T\boldsymbol{S}\boldsymbol{v}_j \\ \text{s.t.} &\quad{} \boldsymbol{v}_j^T\boldsymbol{v}_j = 1 \end{aligned}

の解である jj 主成分軸のベクトル vj\boldsymbol{v}_j は、ラグランジュの未定乗数法によれば、λ∈R\lambda{} \in{} \R を導入によって定義される L(vj,λ)=vjTSvj−λ(vjTvj−1)\mathcal{L}(\boldsymbol{v}_j, \lambda{}) = \boldsymbol{v}_j^T\boldsymbol{S}\boldsymbol{v}_j - \lambda{}(\boldsymbol{v}_j^T\boldsymbol{v}_j - 1) の極値問題を解くことで得られるということである。

L(vj,λ)\mathcal{L}(\boldsymbol{v}_j, \lambda{}) を vj\boldsymbol{v}_j で微分すると、

∂L/∂vj=2Svj−2λvj=2(Svj−λvj)\begin{aligned} \partial{\mathcal{L}}/\partial{\boldsymbol{v}_j} &= 2\boldsymbol{S}\boldsymbol{v}_j - 2\lambda{}\boldsymbol{v}_j \\ &=2(\boldsymbol{S}\boldsymbol{v}_j - \lambda{}\boldsymbol{v}_j) \end{aligned}

であり、∂L/∂vj=0\partial{\mathcal{L}}/\partial{\boldsymbol{v}_j} = 0 として解けば Svj=λvj\boldsymbol{S}\boldsymbol{v}_j = \lambda{}\boldsymbol{v}_j が得られるが、これは共分散行列 S\boldsymbol{S} に対する固有値問題に他ならない。

同様にして、∂L/∂λ=0\partial{\mathcal{L}}/\partial{\lambda{}} = 0 解いて得られる vjTvj=1\boldsymbol{v}_j^T\boldsymbol{v}_j = 1 は、正規直交基底の条件そのものである。

非負値行列因子分解 (NMF)

参考: Lee, Daniel & Seung, Hyunjune. (2001). Algorithms for Non-negative Matrix Factorization. Adv. Neural Inform. Process. Syst.. 13.

[Keywords]

非負行列を２つの非負行列の積で表現する手法。

NMF

なぜ非負にこだわるのかというと、東京大学の資料  によれば、

とのこと。

Y≈HU\boldsymbol{Y} \approx{} \boldsymbol{H}\boldsymbol{U}

ただし、Y∈R+N,K,H∈R+K,M,U∈R+M,N\boldsymbol{Y}\in\R_{+}^{N,K}, \boldsymbol{H}\in\R_{+}^{K,M}, \boldsymbol{U}\in\R_{+}^{M,N}であり、H\boldsymbol{H} を基底行列、U\boldsymbol{U} を係数行列という。

minD(H,U)=∑i=1N∑j=1K(yi,j−∑k=1Mhi,kuk,j)2s.t.hi,k≥0i=1,…,N,k=1,…,Muk,j≥0k=1,…,M,j=1,…,K\begin{aligned} \text{min} & \quad{} D(\boldsymbol{H},\boldsymbol{U}) = \sum_{i=1}^{N}\sum_{j=1}^{K}\left(y_{i,j} - \sum_{k=1}^{M}h_{i,k}u_{k,j}\right)^2\\ \text{s.t.} & \quad{} h_{i,k} \ge 0 \qquad{} i=1,\ldots{},N,k=1,\ldots{},M \\ & \quad{} u_{k,j} \ge 0 \qquad{} k=1,\ldots{},M,j=1,\ldots{},K \\ \end{aligned}

目的関数を展開すると、

D(H,U)=∑i=1N∑j=1K(yi,j−∑k=1Mhi,kuk,j)2=∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+(∑k=1Mhi,kuk,j)2)\begin{aligned} D(\boldsymbol{H},\boldsymbol{U}) = & \sum_{i=1}^{N}\sum_{j=1}^{K}\left(y_{i,j} - \sum_{k=1}^{M}h_{i,k}u_{k,j}\right)^2 \\ =& \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \left(\sum_{k=1}^{M}h_{i,k}u_{k,j}\right)^2 \right) \end{aligned}

（補足）D(H,U)D(\boldsymbol{H},\boldsymbol{U}) の展開をさらに進めると、

∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+(∑k=1Mhi,kuk,j)2)=∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+∑k=1Mhi,k2uk,j2+2∑k≠lhi,kuk,jhi,lul,j)\begin{aligned} & \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \left(\sum_{k=1}^{M}h_{i,k}u_{k,j}\right)^2 \right) \\ =& \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \sum_{k=1}^{M}h_{i,k}^2u_{k,j}^2 + 2\sum_{k\neq{}l}h_{i,k}u_{k,j}h_{i,l}u_{l,j} \right) \\ \end{aligned}

のように、hi,kvk,jh_{i,k}v_{k,j} に関する項が増え、解析的に解を求めることが困難になる。

ここで、∑k=1Mλi,j,k=1\sum_{k=1}^{M}\lambda{}_{i,j,k}=1 の下で λi,j,k>0\lambda{}_{i,j,k} > 0 を導入すると、イェンセンの不等式から、

∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+(∑k=1Mhi,kuk,j)2)=∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+(∑k=1Mλi,j,khi,kuk,jλi,j,k)2)≤∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+∑k=1Mλi,j,k(hi,kuk,jλi,j,k)2)=∑i=1N∑j=1K(yi,j2−2yi,j∑k=1Mhi,kuk,j+∑k=1Mhi,k2uk,j2λi,j,k)\begin{aligned} & \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \left(\sum_{k=1}^{M}h_{i,k}u_{k,j}\right)^2 \right) \\ =& \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \left(\sum_{k=1}^{M} \lambda{}_{i,j,k} \frac{h_{i,k}u_{k,j}}{\lambda{}_{i,j,k}}\right)^2 \right) \\ \le& \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \sum_{k=1}^{M}\lambda{}_{i,j,k}\left(\frac{h_{i,k}u_{k,j}}{\lambda{}_{i,j,k}}\right)^2 \right) \\ =& \sum_{i=1}^{N}\sum_{j=1}^{K} \left( y_{i,j}^2 - 2y_{i,j}\sum_{k=1}^{M}h_{i,k}u_{k,j} + \sum_{k=1}^{M}\frac{h_{i,k}^2u_{k,j}^2}{\lambda{}_{i,j,k}} \right)\\ \end{aligned}

と目的関数の上限となる関数が得られ、これを λ={λi,j,k}N×K×M\boldsymbol{\lambda{}} = \{\lambda{}_{i,j,k}\}_{N\times{}K\times{}M} を用いて G(H,U,λ)G(\boldsymbol{H}, \boldsymbol{U}, \boldsymbol{\lambda{}}) とおく。等号は、hi,1u1,jλi,j,1=hi,2u2,jλi,j,2=⋯=hi,MuM,jλi,j,M\frac{h_{i,1}u_{1,j}}{\lambda{}_{i,j,1}} = \frac{h_{i,2}u_{2,j}}{\lambda{}_{i,j,2}} = \cdots{} = \frac{h_{i,M}u_{M,j}}{\lambda{}_{i,j,M}} のとき成り立つ。

これにより、補助関数法に従えば、

λ←arg min⁡λG(H,U,λ)H←arg min⁡HG(H,U,λ)U←arg min⁡UG(H,U,λ)\begin{aligned} \boldsymbol{\lambda{}} &\leftarrow{} \underset{\boldsymbol{\boldsymbol{\lambda{}}}}{\argmin{}}G(\boldsymbol{H}, \boldsymbol{U}, \boldsymbol{\lambda{}}) \\ \boldsymbol{H} &\leftarrow{} \underset{\boldsymbol{H}}{\argmin{}}G(\boldsymbol{H}, \boldsymbol{U}, \boldsymbol{\lambda{}}) \\ \boldsymbol{U} &\leftarrow{} \underset{\boldsymbol{U}}{\argmin{}}G(\boldsymbol{H}, \boldsymbol{U}, \boldsymbol{\lambda{}}) \end{aligned}

を繰り返し行うことで、目的関数 D(H,U)D(\boldsymbol{H},\boldsymbol{U}) の値を最小化できるということである。

まず、イェンセンの不等式の等号成立条件 hi,1u1,jλi,j,1=hi,2u2,jλi,j,2=⋯=hi,MuM,jλi,j,M\frac{h_{i,1}u_{1,j}}{\lambda{}_{i,j,1}} = \frac{h_{i,2}u_{2,j}}{\lambda{}_{i,j,2}} = \cdots{} = \frac{h_{i,M}u_{M,j}}{\lambda{}_{i,j,M}} から、

λi,j,1=hi,1u1,jhi,1u1,jλi,j,1λi,j,2=hi,2u2,jhi,1u1,jλi,j,1⋮λi,j,M=hi,MuM,jhi,1u1,jλi,j,1\begin{aligned} \lambda{}_{i,j,1} &= \frac{h_{i,1}u_{1,j}}{h_{i,1}u_{1,j}}\lambda{}_{i,j,1} \\ \lambda{}_{i,j,2} &= \frac{h_{i,2}u_{2,j}}{h_{i,1}u_{1,j}}\lambda{}_{i,j,1} \\ \vdots{} \\ \lambda{}_{i,j,M} &= \frac{h_{i,M}u_{M,j}}{h_{i,1}u_{1,j}}\lambda{}_{i,j,1} \\ \end{aligned}

が得られ、∑k=1Mλi,j,k=1\sum_{k=1}^{M}\lambda{}_{i,j,k}=1 に代入すると、

hi,1u1,jhi,1u1,jλi,j,1+hi,2u2,jhi,1u1,jλi,j,1+⋯+hi,MuM,jhi,1u1,jλi,j,1=1\frac{h_{i,1}u_{1,j}}{h_{i,1}u_{1,j}}\lambda{}_{i,j,1}+ \frac{h_{i,2}u_{2,j}}{h_{i,1}u_{1,j}}\lambda{}_{i,j,1} + \cdots{}+ \frac{h_{i,M}u_{M,j}}{h_{i,1}u_{1,j}}\lambda{}_{i,j,1} = 1

から、

λi,j,1=hi,1u1,j∑k=1Mhi,kvk,j\lambda{}_{i,j,1} = \frac{h_{i,1}u_{1,j}}{\sum_{k=1}^{M}{h_{i,k}v_{k,j}}}

が得られる。λi,j,2,…,λi,j,M\lambda{}_{i,j,2},\ldots{},\lambda{}_{i,j,M} らについても同様に計算すると、

λi,j,k=hi,kuk,j∑k′=1Mhi,k′vk′,j\lambda{}_{i,j,k} = \frac{h_{i,k}u_{k,j}}{\sum_{k'=1}^{M}{h_{i,k'}v_{k',j}}}

として関数 G(H,U,λ)G(\boldsymbol{H}, \boldsymbol{U}, \boldsymbol{\lambda{}}) の最小の値を与える λ\boldsymbol{\lambda{}} が計算できた。

次に、G(H,U,λ)G(\boldsymbol{H}, \boldsymbol{U}, \boldsymbol{\lambda{}}) は、次式のように行列 H\boldsymbol{H} の各要素 hi,kh_{i,k} ごとに分離できる。各 hi,kh_{i,k} について整理すると、

G(H,U,λ)=∑i=1N∑j=1Kyi,j2+∑i=1N∑k=1M((∑j=1K−2yi,jvk,j)hi,k+(∑j=1Kuk,j2λi,j,k)hi,k2)G(\boldsymbol{H},\boldsymbol{U},\boldsymbol{\lambda{}}) = \sum_{i=1}^{N}\sum_{j=1}^{K}y_{i,j}^2 + \sum_{i=1}^{N}\sum_{k=1}^{M}\left( \left( \sum_{j=1}^{K}-2y_{i,j}v_{k,j} \right) h_{i,k} + \left( \sum_{j=1}^{K} \frac{u_{k,j}^2}{\lambda{}_{i,j,k}} \right) h_{i,k}^2 \right)

のように、hi,kh_{i,k} ごとに独立な二次関数の和の形で表現できるので、それぞれの hi,kh_{i,k} を個別に最小化することで式全体を最小化できる。式の値を最小化する各 h^i,k\hat{h}_{i,k} は、

h^i,k=∑j=1Kyi,jvk,j∑j=1Kuk,j2λi,j,k\hat{h}_{i,k} = \frac{\sum_{j=1}^{K} y_{i,j}v_{k,j}}{\sum_{j=1}^{K} \frac{u_{k,j}^2}{\lambda{}_{i,j,k}}}

であり、同様にして行列 U\boldsymbol{U} の各要素 uk,ju_{k,j} に対しても G(H,U,λ)G(\boldsymbol{H},\boldsymbol{U},\boldsymbol{\lambda{}}) を最小化する u^k,j\hat{u}_{k,j} も、

u^k,j=∑i=1Nyi,jhi,k∑i=1Nhi,k2λi,j,k\hat{u}_{k,j} = \frac{\sum_{i=1}^{N} y_{i,j}h_{i,k}}{\sum_{i=1}^{N} \frac{h_{i,k}^2}{\lambda{}_{i,j,k}}}

のように求まる。

各行列要素の値の更新を繰り返すことで、目的関数 D(H,U)D(\boldsymbol{H},\boldsymbol{U}) の値を単調減少させることができる。

イェンセンの不等式 (Jensen’s inequality)

任意の凸関数 gg、II 個の実数 x1,…,xIx_1,\ldots{},x_I、∑i=1Iλi=1\sum_{i=1}^{I}{\lambda{}_i}=1 を満たす II 個の正値の重み係数 λ1,…,λI\lambda{}_1,\ldots{},\lambda{}_I のもとで、

g(∑i=1Iλixi)≤∑i=1Iλig(xi)g\left(\sum_{i=1}^{I}{\lambda{}_i x_{i}}\right) \le \sum_{i=1}^{I}{\lambda_{i}g(x_i)}

が成り立つ。等号は x1=x2=⋯=xIx_1=x_2=\cdots{}=x_I のとき成立する。

(証明) I=2I=2 のとき、不等式は凸関数の性質そのものである。I=kI=k のとき、不等式が成り立つと仮定して、I=k+1I=k+1 のとき、

g(∑i=1k+1λixi)≤∑i=1k+1λig(xi)g\left(\sum_{i=1}^{k+1}{\lambda{}_i x_{i}}\right) \le \sum_{i=1}^{k+1}{\lambda_{i}g(x_i)}

となることを示したい。

問題の仮定より、∑i=1k+1λi=1\sum_{i=1}^{k+1}{\lambda{}_i}=1 である。ここで、∑i=1kλi1−λk+1=1\sum_{i=1}^{k}{\frac{\lambda{}_i}{1-\lambda_{k+1}}}=1 であることと、帰納法の仮定から、

g(∑i=1kλi1−λk+1xi)≤∑i=1kλi1−λk+1g(xi)(1)g\left(\sum_{i=1}^{k}{\frac{\lambda{}_i}{1-\lambda_{k+1}} x_{i}}\right) \le \sum_{i=1}^{k}{\frac{\lambda_{i}}{1-\lambda_{k+1}}g(x_i)} \tag{1}

が得られる。

さらに、(1−λk+1)+λk+1=1(1-\lambda_{k+1})+\lambda_{k+1}=1 と凸関数の性質から、

g((1−λk+1)(∑i=1kλi1−λk+1xi)+λk+1xk+1)≤(1−λk+1)g(∑i=1kλi1−λk+1xi)+λk+1g(xk+1)\begin{aligned} g\left((1-\lambda_{k+1}) \left(\sum_{i=1}^{k}{\frac{\lambda{}_i}{1-\lambda_{k+1}}}x_i \right) + \lambda_{k+1}x_{k+1} \right) &\le (1-\lambda_{k+1})g\left(\sum_{i=1}^{k}{\frac{\lambda{}_i}{1-\lambda_{k+1}}}x_i\right) + \lambda_{k+1}g(x_{k+1}) \\ \end{aligned}

であり、右辺は (1)(1) より、

(1−λk+1)g(∑i=1kλi1−λk+1xi)+λk+1g(xk+1)≤(1−λk+1)∑i=1kλi1−λk+1g(xi)+λk+1g(xk+1)=∑i=1k+1λig(xi)\begin{aligned} (1-\lambda_{k+1})g\left(\sum_{i=1}^{k}{\frac{\lambda{}_i}{1-\lambda_{k+1}}}x_i\right) + \lambda_{k+1}g(x_{k+1}) &\le (1-\lambda{}_{k+1})\sum_{i=1}^{k}{\frac{\lambda_{i}}{1-\lambda_{k+1}}g(x_i)} + \lambda{}_{k+1}g(x_{k+1}) \\ &= \sum_{i=1}^{k+1}{\lambda{}_ig(x_i)} \end{aligned}

によって題意の不等式が示された。

補助関数法

目的関数が非線形であるといった理由等で解の探索が困難な場合、目的関数の上限となる補助関数を反復的に降下させることで目的関数を間接的に降下させることができる。

θ={θi}1≤i≤I\theta{}=\{\theta{}_i\}_{1\le{i}\le{I}} を変量とする目的関数 D(θ)D(\theta{}) に対し、

D(θ)=min⁡θˉG(θ,θˉ)D(\theta{}) = \underset{{\bar{\theta{}}}}{\min{}}G(\theta{}, \bar{\theta{}})

が成り立つとき、G(θ,θˉ)G(\theta{}, \bar{\theta{}}) を D(θ)D(\theta{}) を補助関数、θˉ\bar{\theta{}} を補助変数という。

補助関数 G(θ,θˉ)G(\theta{},\bar{\theta{}}) を、θˉ\bar{\theta{}} に関して最小化するステップと、θ1,…,θI\theta_{1},\ldots{},\theta_{I} に関して最小化するステップ

θˉ←arg min⁡θˉG(θ,θˉ)θi←arg min⁡θiG(θ,θˉ)\begin{aligned} \bar{\theta} &\leftarrow{} \underset{\bar{\theta{}}}{\argmin{}}{G(\theta{}, \bar{\theta{}})} \\ \theta{}_i &\leftarrow{} \underset{\theta{}_i}{\argmin{}}{G(\theta{},\bar{\theta{}})} \end{aligned}

を繰り返すと、目的関数 D(θ)D(\theta{}) の値は単調減少する。

MIT License 2025 © Daiki Okayama.RSS