社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
対数線形モデル高速学習のための基底関数
高畠 一哉†
赤穂昭太郎†
† 産業総合技術研究所ヒューマンライフテクノロジー研究部門
〒 305-8568 茨城県つくば市梅園 1–1 産総研中央 2
E-mail: †{k.takabatake,s.akaho}@aist.go.jp
あらまし
離散変数対数線形モデルに対して以下の優れた特徴を持つ基底関数の組とそれを用いた高速学習アルゴリ
ズムを提案する．1) 基底数が大きく分布を表す表現力が高い．基底数を最大限にとれば任意の Gibbs 分布を表現する
ことも可能．2) 対数尤度の勾配ベクトルを基底数の対数に比例する計算量で計算できる．このため基底数が多くとも
計算量爆発を起こさない．3) 学習におけるスコア最小化に特別な反復法を用いる．この反復法は微分不可能な凸関数
にも使え，さらに最小値への収束は簡単な必要十分条件により保証される．
キーワード
対数線形モデル，基底関数，高速アルゴリズム，反復法，L1 正則化
Basis Functions for Fast Learning of Log-linear Models
Kazuya TAKABATAKE† and Shotaro AKAHO†
† Human Technology Institute, AIST
AIST Central 2, Tsukuba, 305-8568, JAPAN
E-mail: †{k.takabatake,s.akaho}@aist.go.jp
Abstract We propose basis functions for log-linear models and a fast learning algorithm that works on these
bases. These bases and the fast learning algorithm have the following preferable properties. 1) The number of
bases is large so that the bases can represent distributions flexibly. If we take the maximum number of bases, they
are able to represent any Gibbs distributions. 2) The gradient vector of the log-likelihood is computed by a fast
algorithm whose computational costs are proportional to the logarithm of the number of bases. Therefore, the large
number of bases does not invite massive computations. 3) For the learning task, a special iterative method is used
for minimizing the score. It even works for non-differentiable convex functions; furthermore, its convergence to the
minimum is guaranteed under a simple necessary and sufficient condition.
Key words log-linear model, basis function, fast algorithm, iterative method, L1 regularization.
見るときは ϕy と記する．
1. は じ め に
lθ : X → R: 指数部と呼ぶ．
本論文で言う所の対数線形モデル (log-linear model) [1] とは
以下の式で表される分布 pθ である．
elθx
pθ (x) =
,
Z
lθx =
∑
θy ϕyx ,
y
このモデルは Gibbs 分布，すなわち全ての x について p(x) > 0
である分布を表しうる．
Z=
∑
lθx
e
(1)
x
x: 確率変数の具現値．値域を X で表す．本論文では
x は n 次元ベクトル x = (x0 , ..., xn−1 )(xi ∈ Xi ) で各
xi は有限離散値をとる，すなわち |Xi | < ∞ の場合を
パラメータ学習，すなわち観測されたデータ D(経験分布 pD )
からパラメータ θ を決めモデル pθ を得ることは以下のスコア
関数の最小化により行われる．
score(θ) = − ⟨ln pθ ⟩pD + r(θ)
扱う．
ここで右辺第 1 項は負の対数尤度であり凸関数（注 1） である．第
y: 基底関数の番号．値域を Y で表す．|Y | < ∞．
2 項は正則化項でありこれも凸関数にとることによりスコア全
θ = {θy }: パラメータ．θy ∈ R．
ϕ : Y × X → R: 基底関数．y を固定して x の関数と
（注 1）
：本論文では下に凸な関数とする．
—1—
体を凸関数として凸最小化問題を解くことになる．この最小化
という優れた特徴を持つ．以下の 2,3 節でこれら 2 つのアイデ
にはもっぱら準ニュートン法などの反復法が使われ，対数尤度
アを示す．また 4 節で本手法を L1 正則化 [2] で用いる利点につ
の勾配ベクトル計算が必要となる．勾配ベクトルの第 y 成分は
いて示す．
以下のように計算される (以下 ∂y = ∂/∂θy と略記する)．
−∂y ⟨ln pθ ⟩pD = − ⟨∂y lθ ⟩pD + ∂y ln Z
1 ∑ lθx
= − ⟨ϕy ⟩pD + ∂y
e
Z
x
1 ∑
= − ⟨ϕy ⟩pD +
ϕyx elθx
Z x
= ⟨ϕy ⟩pθ − ⟨ϕy ⟩pD
負の対数尤度の勾配ベクトルは式 (2) を全ての y について求
めることで求まる．Eθy の計算量が支配的なのでその高速化を
考える．
2. 1 元となる原理
本高速計算の原理は多次元離散フーリエ変換 [3] を考えると
(2)
理解しやすい．例として以下の |X0 | × |X1 | 要素の 2 次元離散
フーリエ変換を考えてみる．
今後頻繁に登場するので
Eθy = ⟨ϕy ⟩pθ ,
2. 勾配ベクトルの高速計算
EDy = ⟨ϕy ⟩pD
と略記することにする．式 (2) では Eθy の計算量が支配的で
∏
|X| = i |Xi | 回の積和演算（注 2） が必要である．EDy の計算に
は |D|(データ数) 回の積和演算を要するが通常は |D| ≪ |X| な
のでこの計算量は無視できる．1 基底分の計算にこれだけ掛か
るので |Y | 個の基底のためには |X||Y | 回の積和演算が必要と
なり，それが反復法の 1 ステップ毎に掛かることになる．
∑
Fy0 y1 =
fx0 x1 αy0 x0 β y1 x1
x0 x1
α : 1 の原始 |X0 | 乗根,
β : 1 の原始 |X1 | 乗根
全ての y0 , y1 についてそれぞれ x0 , x1 の総和をとるという単
純な方法で F を計算すると (|X0 ||X1 |)2 回の積和計算を要する
が，通常は以下のように 1 次元ずつフーリエ変換してゆく方法
がとられる．
全ての可能な指数部 lθ の関数空間の次元は |X| である．こ
Fy0 y1 =
こで 2 つの例を挙げよう．
(
∑ ∑
x1
)
fx0 x1 α
y0 x0
β y1 x1
x0
例 1) x が 20 次元 2 値ベクトル．
1) 括弧内の総和を全ての x1 , y0 についてとる (積和
例 2) x = (x0 , x1 ) で xi はそれぞれアナログ量を 10bit
回数 |X0 |2 |X1 |)．x0 は消え括弧内は y0 , x1 の関数と
で量子化したもの．
なる．
このどちらの場合も |X| = 220 となる．このような場合現実的
には計算量の都合上 |Y | ≪ |X|，すなわち広大な関数空間に比
2) 外側の総和を全ての y0 , y1 についてとる (積和回
数 |X0 ||X1 |2 )．x1 は消え Fy0 y1 が得られる．
べごく少ない基底を張ることしかでず分布を表現する能力が貧
変換全体にかかる積和回数は |X0 ||X1 |(|X0 | + |X1 |) に減る．こ
弱となる．本論文は基底関数の形をうまくとればこの問題を回
の原理を勾配ベクトルの高速計算に用いる．
避できることを示す．
2. 2 勾配ベクトルの高速計算
本論文は 2 つの独立なアイデアからなる．1 つは基底関数を
i = 0, ..., n − 1 に対して基底番号も y = (y0 , ..., yn−1 )(yi ∈
うまくとることにより負の対数尤度の勾配ベクトルの計算量が
Yi ) とベクトルで表し，ϕiyi（注 3） : Xi → R なる関数を用意しこ
O(|X| log |Y |) とできることを示す．
れを「ローカル基底」と呼ぶ．基底はローカル基底の積
もう 1 つはこれも基底関数をうまくとることにより，近似を
ϕy =
一切用いない反復法ができることを示す．現在よく用いられて
基本的に C 1 (微分連続) クラスの関数の最小化にしか使
えない．
•
様々な近似 (テイラー展開近似，擬似ヘシアン逆行列) を
とする．すると
Eθy =
C ∞ クラスの凸関数でも収束しない場合がある．収束を
∑
pθ (x)ϕyx
x
用いている．
•
ϕiyi
i
いる準ニュートン法では
•
∏
=
∑
(
...
(
∑
xn−1
)
pθ (x)ϕ0y0 x0
)
... ϕn−1
yn−1 xn−1
x0
保証するための必要十分条件が分からない．
という難点があるが提案手法は
•
微分可能性を必要としない．
•
一切の近似を用いない．
•
反復法の進展にともなうスコアの単調減少が保証される．
•
簡単な必要十分条件により収束が保証できる．
であるので内側の括弧から順に評価してゆく．すなわち
G0x = pθ (x)
G1y0 x1 ...xn−1 =
∑
G0x ϕ0y0 x0
x0
（注 3）
：i はべき乗ではなく単なる上添え字．以降上添え字を多用するので注意
（注 2）
：本論文では演算 d = a ∗ b + c を 1 積和演算と数える．
されたい．
—2—
変換には通常 |Yi ||Xi | 回の積和演算が必要である．
..
.
Gn
y
∑
=
2. 3. 1 |Xi | = |Yi | = 2ki のとき
n−1
Gn−1
y0 ...yn−2 xn−1 ϕyn−1 xn−1
Φ(i) をフーリエ変換行列やアダマール行列にとれば高速変換
xn−1
アルゴリズムにより積和演算を ki |Yi | 回に減らせる．ローカル
として最終的に Eθy =
Gn
y
i+1
が求まる．ここで各 G
i
i+1
全ての下添え字について行うので G から G
の評価は
変換を全ての y0 ...yi−1 xi+1 ...xn−1 について行うことにより Gi
を求めるのに
から Gi+1 が求まるので Gi から Gi+1 を求めるのに掛かる積
掛かる積和回数は
和回数は
|Y0 |...|Yi ||Xi |...|Xn−1 |
ki |Y0 |...|Yi−1 ||Yi ||Xi+1 |...|Xn−1 | = ki 2ki n
となる．簡単のため |Xi | = a, |Yi | = b とすると G0 から Gn す
となる．簡単のため |Xi | = |Yi | = 2k とすると pθ から全ての
なわち pθ から全ての y について Eθy を求めるのに掛かる積和
y について Eθy を求めるのに掛かる積和回数は
回数は
n−1
∑
bi+1 an−i
i=0
nan+1 = na|X|
=
ab(an −bn ) = ab(|X|−|Y |)
a−b
a−b
kn2kn = kn|X| = |X| log2 |Y |
a=b
a=
| b
(3)
2. 3. 2 |Xi | = a =
| |Yi | = b = 2k のとき
多くの高速変換行列は正方行列であり自由にサイズもとれな
となる．
い．このような場合はローカル変換行列を
pθ を求めるにはまず指数部 lθ を求める．
lθx =
∑
Φ(i) = F (i) S (i)
θy ϕ0y0 x0 ...ϕn−1
yn−1 xn−1
y
=
となる．θ から lθ にかかる積和回数もこれと同じとなる．
∑
(
(
...
yn−1
∑
)
θy ϕ0y0 x0
)
...
F (i) : 2ki × 2ki 高速変換行列．
ϕn−1
yn−1 xn−1
S (i) : 2ki × |Xi | 疎行列．
(4)
y0
なので先ほどと同様の計算により Gi から Gi+1 を求めるのに
としてやれば
(i+1)
(i)
g...
= F (i) S (i) g...
掛かる積和回数は
(i)
となる．この式の右辺を (F (i) S (i) )g...
と見れば，F (i) の各行
|X0 |...|Xi ||Yi |...|Yn−1 |
となり |Xi | = a, |Yi | = b とした場合 θ から lθ を求めるのに掛
かる積和回数は式 (3) と同じになる．cexp を 1 回の指数計算に
必要な積和回数とすると lθ から pθ を求めるには (cexp + 2)|X|
回の積和計算を必要とする．
以 上 の 結 果 を ま と め る と θ か ら 全 て の y に つ い て Eθy
を求める計算量は n のみを変数としてみると最悪でも
で表される |Yi | 次元の基底を S (i) で |Xi | 次元に射影したもの
(i)
がローカル基底になっていると解釈できる．また F (i) (S (i) g...
)
(i)
と見れば g...
を |Yi | 次元に射影してからローカル変換を行って
(i)
いると解釈できる．S (i) g...
の計算に掛かる積和回数は S (i) の
非 0 要素数 (si |Yi | とおく) であるのでローカル変換にかかる積
和回数は (si + ki )|Yi | となり，Gi から Gi+1 を求めるのにかか
る積和回数は
O(nan ) = O(|X| log |Y |) となる．
(si + ki )|Y0 |...|Yi ||Xi+1 |...|Xn−1 |
2. 3 ローカル変換の高速化
式 (3) を見ると，例 1 にあげたような |Yi | = b が小さいとき
となる．簡単のため si = s, ki = k, |Yi | = 2k < |Xi | = a の
には十分な高速化効果があるが，例 2 のような |Yi | = b が大き
とき pθ から全ての y について Eθy を求めるのに掛かる積和回
い場合には効果が薄い．このような場合は以下に示すように高
数は
速フーリエ変換や高速アダマール変換 [4] などの高速変換を用
n−1
∑
いて計算量をさらに小さくすることができる．
Gi から Gi+1 を求める漸化式において yi , xi 以外の全ての変
数を固定し
(|Xi | × 1 ベクトル)
(i)
g...
= (Gi...xi ... )
(i+1)
g...
= (Gi+1
...yi ... )
Φ(i) = (ϕiyi xi )
(|Yi | × 1 ベクトル)
(|Yi | × |Xi | 行列)
(s + k)2k(i+1) an−i−1 =
(s + k)2k (an − 2kn )
a − 2k
=
(s + k)2k (|X| − |Y |)
a − 2k
i=0
となる．なお θ から lθ を求める際のローカル変換行列は |Yi |×|Yi |
行列となることから |Yi | = 2ki ととることで高速変換行列をそ
のまま用いることができる．
3. 近似を用いない反復法
と定義すると
(i+1)
(i)
g...
= Φ(i) g...
となる．これを「ローカル変換」と呼ぶことにする．ローカル
Eθy を θy 以外のパラメータを固定して θy だけの 1 変数関数
としてみたものを uy (θy ) とおく．この導関数は
—3—
u′y (θy ) = −∂y Eθy = ∂y
∑
=
(
=
ϕyx pθ (x) =
x
ϕyx
ϕyx elθx
elθx ∂y Z
−
Z
Z2
ϕ2yx pθ
∂y Z ∑
−
ϕyx pθ
Z x
x
∑
∑
x
∑
)
ϕyx ∂y
x
elθx
Z
v ′ = u − ED
wy
(c, −ED )
θy = 0
−wy
′
vy
(0) > wy
′
|vy
(0)| <
= wy
′
vy
(0) < −wy
図 1 θymin の位置は交点
⟨ ⟩
2
= ϕ2y p − Eθy
この scorey (θy ) は θy =
| 0 で微分可能，θy = 0 では左微係数と
θ
右微係数を持つ．最小点，最小値を
であるので常微分方程式
⟨ ⟩
u′y = ϕ2y p − u2y
θymin = arg min score(θy )
θy
θ
scoreymin = min score(θy )
が導かれる．ここですべての x において
θy
ϕyx = ±1
すなわち
ϕ2y
(5)
とおく．scorey (θy ) の微係数が 0 であるか，左微係数が 0 以下
で右微係数が 0 以上であるところが最小点 θymin なので図 1 に
≡ 1 となる基底を使うと
示すように v ′ と階段関数 ±wy との交点が θymin を示す．式に
書くと
u′y = 1 − u2y
である．この常微分方程式の一般解は
θymin
uy = tanh(θy − c)
で与えられる．境界条件としてある θ0 において u0y = uy (θy0 )
scoreymin
vy′ (0) > wy
tanh−1 (wy + EDy ) + c
= 0
|vy′ (0)| <
= wy
−1
′
tanh (−wy + EDy ) + c vy (0) < −wy
∑
= vy (θymin ) + wy |θymin | +
wy′ |θy′ |
y ′ =y
|
が既知とすると
c = θy0 − tanh−1 u0y = θy0 −
1 1 + u0y
ln
2 1 − u0y
以上のように各 θy 方向にある最小値が分かることからそれら
の内で最小となる y について θy を θymin に更新してゆく以下
となる．負の対数尤度も 1 変数関数とみて
のような反復法が考えられる．
vy (θy ) = − ⟨ln pθ ⟩pD
1) θ = 0 とする．
とおくと
2) 何らかの収束条件を満たせば停止する．
vy′ (θy ) = uy (θy ) − EDy
∫ θy
vy (θy ) = vy0 +
uy (η) − EDy dη
3) y ′ = arg miny vymin とする．最小値が複数あると
きはそのどれでもよい．
(vy0 = vy (θy0 ))
4) θy′ を = θy′ min に更新する．最小値が複数あると
0
θy
きはそのどれでもよい．
θ
y
= vy0 + [ln 2 cosh(η − c) − EDy η]η=θ
0
5) 2 に戻る．
y
= vy0 + ln 2 cosh(θy − c) − EDy (θy − θy0 )
この反復法ではスコアが単調減少していくことは自明である．
1
− ln(1 − u0y )(1 + u0y ) + ln 2
2
3. 1 反復法の収束
以上に述べた反復法は一般の凸関数 f (θ) に対して常に収束
と近似なしに解析的に求まる．
するわけではない．以下に反例を示す．
ここで以下の重み付き L1 正則化項の場合のスコアの最小化
を考えてみることにする．
score(θ) = − ⟨ln pθ ⟩pD +
∑
wy |θy |,
wy >
=0
(6)
y
ここでも θy 以外のパラメータを固定して score を θy だけの関
数と見てみる．
scorey (θy ) = vy (θy ) + wy |θy | +
∑
y ′ =y
|
f (θ) = |θ0 − θ1 | + ϵ(θ02 + θ12 ),
0<ϵ<
1
2
この関数の点 θ = (θ0 , θ1 ) = (1, 1) における f の降下方向を図
2 に示す．反復法のあるステップ t で θt = (1, 1) と仮定すると
θt+1 も (1, 1) となる．すなわち (1, 1) は停留点となり反復法は
最小点 (0, 0) に収束しない．この原因は (1, 1) 点からどの軸方
向を見ても上り坂であるのに (0, 0) に向かう方向には下ってい
wy′ |θy′ |
ることにある．
以下の定義をする
Ay (θ0 ) = {θ|θy = θy0 }: 点 θ0 における第 y 軸と呼ぶ．
—4—
f に対して初期値 θ0 ∈ B とし 3. 節の反復法を行い得られる点
x1
列を {θt } とする．このとき任意の初期値に対して
lim f (θt ) = min f (θ)
t→∞
θ∈B
となるための必要十分条件は f の全ての軸最小点がまた極小点
x0
となることである．
図2
収束しない例
証明)
軸最小: θ0 = min ∪y Ay のとき θ0 は軸最小であると
呼ぶ．
必要条件) 軸最小点が停留点となることから必要条件は自明で
ある．
十分条件) 凸関数は連続関数 [5] なので補題より {θt } の集積点
反例の点 (1, 1) は軸最小であるにもかかわらず極小でない点で
a は軸最小である．ここで軸最小点が極小点であれば f の凸性
ある．では逆に軸最小点が必ず極小であるならばこの反復法は
から a は最小点すなわち
最小値に収束するであろうか? 以下の補題と定理によりそれは
f (a) = min f (θ)
保証される．
θ∈B
補題) f : B → R を有界閉領域 B ⊂ Rn で連続な関数とする．
である．a に収束する {θt } の部分列 {θti } をとれば
f に対して初期値 θ0 ∈ B とし 3. 節の反復法を行い得られる点
列を {θt } とする．このとき {θt } の集積点は全て軸最小である．
lim f (θti ) = f (a) = min f (θ)
i→∞
となるが元の数列 {θt } は単調減少列でその部分列の f 値が最
小値に収束することから
証明) a を集積点とするとき {θt } の部分列で
lim f (θt ) = min f (θ)
lim θti = a
t→∞
i→∞
θ∈B
となる．
となるものがとれる．f の連続性から
lim f (θti ) = f (a)
(証明終わり
(7)
i→∞
である．背理法の仮定として a が軸最小でないとすると，ある
第 y 軸上で
θ∈Ay
L1 正則化は最初に与えられた基底の組 {ϕy }(y ∈ Y ) のうち
f (θmin ) < f (a)
となっている．部分列 {θti } の各点の第 y 成分だけを θmin の
第 y 成分で置き換えた点列 {λ } を考えると
ti
i→∞
どれが不要であったかを教えてくれるが，逆にどのような基底
を追加すれば良いのかについては何も教えてくれない．最初に
与えた基底が不足していれば望ましい分布を表現できずに満足
lim f (λti ) = f (θmin )
i→∞
できる性能のモデルが得られないことになる．であれば最初に
全ての関数を表現しうるだけの基底を与えておけばよかろう．
であるので十分大きな j に対して
式 (1) において基底数を |Y | = |X| ととりあらゆる指数部
tj
lθ を表現できるようにしたモデルをフルスパン対数線形モデ
f (λ ) < f (θmin )
とできる．ところがこのとき λtj ∈ Ay (θtj ) であるので
tj +1
L1 正則化項を加えたものであるときは軸最小点は極小点とな
4. L1 正則化とフルスパンモデル
なる点に対して
lim λti = θmin ,
f が C 1 (微分連続) クラスまたは C 1 クラスの関数に重みつき
ることから定理より反復法は最小値に収束する．
θmin = arg min f (a)
f (θ
θ∈B
ル (full-span log-linear model) と呼ぶことにする．フルスパ
ンモデルを用い L1 正則化により最終的に生き残る (すなわち
θy =
| 0 となる)y の集合を Ys と表すことにする．|Ys | ≪ |X| で
tj
)<
= f (λ ) < f (θmin )
あるときは一見すると不要な基底のため無駄な計算が行われて
であるが {θt } は単調減少列なので i > j なる全ての i について
いるように思うかもしれない．しかし元々|Ys | 個の基底を使い
1. 節で述べた素朴な方法により学習する際の計算量 O(|X||Ys |)
ti
f (θ ) <
= f (θmin ) < f (a)
と 2. 節で述べた計算法にフルスパンモデルを学習する計算量
O(|X| log |X|) を比べるとよほど |Ys | が小さいときを除きフル
となりこれは式 (7) に反し矛盾が生じる．
(証明終わり
定理) f : B → R を有界閉凸領域 B ⊂ Rn での凸関数とする．
スパンモデルの方が有利であることになる．
4. 1 不要な基底の制限
フルスパンモデルで望まない基底の係数 θy を強制的に 0 す
—5—
ることができる．式 (6) の wy は基底を忌避する度合いを制御
する重みである．wy が大きいほど基底 ϕy を使うことに対する
れる．
– ニュートン法とは違い簡単な必要十分条件により収束が
ペナルティが大きくなり θy = 0 と抑制されやすくなる．ここ
保証される．
で ϕyx = ±1, | tanh(∗)| <
= 1 であることから図 1 を見ても分か
>
るように wy = 2 ととれば必ず θymin = 0 となり基底 ϕy は決
といった理論的に好ましい特徴を持つ．
して使われないにことになる．
ルスパンモデルと呼ぶものを構成できる (現実的な時間で計算
例としてボルツマンマシン [6] を最尤推定で学習させること
を考えてみよう．ϕy は x の関数であるが，このとき従属変数
に含まれる xi の個数を ϕy の次数と呼び Ord(ϕy ) と表すこと
にしよう．ボルツマンマシンは 2 体ポテンシャルを使うモデル，
すなわち Ord(ϕy ) <
= 2 である基底のみを用いる対数線形モデ
ルなので，その最尤推定による学習は
2 Ord(ϕy ) > 2
wy =
0 Ord(ϕ ) < 2
y =
とすることにより実現できる．これまで基底が多すぎて計算量
上困難であった m 体ポテンシャルモデルも
2
wy =
0
Ord(ϕy ) > m
Ord(ϕy ) <
=m
とすることで実現できる．
4. 2 計算量のさらなる節約
前節に述べた基底の使用制限により使用されない基底につい
ては 3. 節で示した反復法中での手順 3 で vymin の評価が不要
•
提案手法を使い任意の Gibbs 分布を表すことのできるフ
できる)．
•
フルスパンモデルを L1 正則化に用いることで基底の取
りこぼしのない学習モデルが得られる．
•
設計者の意図によりフルスパンモデルで基底の使用を制
限することができる．
謝辞 本研究は JSPS 科研費 25120011 の助成を受けたもの
です．
文
献
[1] D. Koller and N. Friedman, Probabilistic Graphical Models,
MIT Press, 2009.
[2] J. Friedman, T. Hastie, and R. Tibshirani, “Regularization
paths for generalized linear models via coordinate descent,”
Journal of statistical software, vol.33, no.1, p.1, 2010.
[3] P. Henrici, Applied and computational complex analysis,
discrete Fourier analysis, Cauchy integrals, construction of
conformal maps, univalent functions, vol.3, John Wiley &
Sons, 1993.
[4] M. Harwit, Hadamard transform optics, Elsevier, 2012.
[5] R.T. Rockafellar, Convex analysis, no.28, Princeton university press, 1997.
[6] D.E. Rumelhart, J.L. McClelland, P.R. Group, et al., Parallel distributed processing, vol.1, MIT press, 1995.
となり計算量を抑えることができる．
またこの反復法では 1 ステップで 1 つの θy のみが更新され
ることを利用すれば (4) での計算をより効率化できる．今 θt と
θt+1 は第 y 成分だけが違うとして lθt を既知とすると
lθt+1 = lθt + (θyt+1 − θyt )ϕy
であり全ての x について lθt+1 x を計算するのに要する積和回
数は |X| 回となりこれは 2. 節で示した lθ 計算に比べて速い．
4. 3 効果的なモデル
本論文で述べた勾配ベクトルの高速計算法と反復法が最も有
効に働く推薦設定例は以下のようなものである．
•
フルスパンモデルを用いる．
•
|Yi | = |Xi | = 2ki としローカル変換行列をアダマール行
列とする．これによりローカル変換が高速に行われ，かつ式 (5)
が満たされるので 3. 節に示した反復法が使える．
5. ま と め
•
対数線形モデルの勾配ベクトル計算が高速にできるよう
な基底関数を提案した．確率変数の値域の大きさを |X|，基底
の個数を |Y | とするとき従来法の計算量は O(|X||Y |) に対し本
手法による計算量は O(|X| log |Y |) である．
•
(準) ニュートン法のような近似 (テイラー展開近似，擬
似ヘシアン逆行列) に頼った反復法とは違った近似を全く用い
ない反復法を提案した．この手法は
– 反復のステップ毎にスコアが単調減少することが保証さ
—6—
© Copyright 2024 ExpyDoc
