確率単体への射影操作について
まえがき
確率単体への射影操作について、この文献を読みなさい、と教えて貰ったので読んでみます（最初だけ）。
単体と確率単体
数学の単体の一般的な話はWikipediaさんに譲りましょう。確率単体と呼ばれる時、簡単に考えると足して1になるような正の数の集まりの集合と考えたら良いでしょう。例えば
です（1次元目から6次元目まで、それぞれ「iの目が出る確率」を表していると考えます）。確率を考えているので総和を取ると1となります（当たり前ですが）。ここで
using Random
D = 6
p = rand(D)
とすると、6次元ベクトルが得られます。
# 例えば次が得られる:
6-element Vector{Float64}:
0.5604921244995906
0.6736562171779923
0.39129883247384467
0.29948863202500275
0.08842954277581905
0.07699221783500332
しかしランダムで作ったものなので、和は1になっていません（上の例の場合、和は 2.0903575667872527 (Juliaのsumで計算) です）。
これではこの6次元ベクトルは確率単体に属していない（最初サイコロではない）ので、正規化して和を1にしたいと思います。
特に考えずに実装するならば、ここで全体の和で各要素の値を割ればいいと考えます。Juliaでは
pnorm = p ./ sum(p)
とすれば良いです。こうして和が（ほぼ）1のベクトルを作ることができました。
# 例えば次が得られる:
6-element Vector{Float64}:
0.2681321767170349
0.3222684137304601
0.18719229604112478
0.14327148464140413
0.04230354853200051
0.036832080337975616
確率単体への射影操作について
射影という操作は、点
上の例は、乱数で作った実ベクトル p を新しく確率単体の要素 pnorm へ射影した例と捉えることができます。果たして、これはどういう射影になっているのでしょうか？もちろん和が1になっている（正規化した）ため、確率単体への射影自体は行われていそうです。他にはどのような射影が考えられるでしょうか？
ここからがarXivの内容です。我々は次の射影に興味があります。つまりいろいろな射影が考えられる中で、入力から最も距離が近い点への射影を求めます（制約条件の1つ目は確率単体に属すること、2つ目はすべての確率値が負にならないことを意味しています）。
- 入力:
\mathbf{y} \in \mathbb{R}^D - 出力:
\mathbf{x}
arXivの文書によれば、次のアルゴリズムでこの計算が可能になります。
以下はアルゴリズムを実装したJuliaのコードです（最適化とかは何もしていないクソコードなので使ってはいけません）。
function euclidean_projection(y)
# Step 1
u = sort(y, rev=true)
# Step 2
ρ = 1
for j in 1:length(y)
if u[j] + 1 / j * (1 - sum(u[1:j])) > 0
ρ = j
else
break
end
end
# Step 3, 4
λ = 1 / ρ * (1 - sum(u[1:ρ]))
max.(copy(y) .+ λ, 0)
end
これを上の例に適用してみましょう。
pnorm2 = euclidean_projection(p)
要素の和で全要素を割った場合と比較して、かなり見た目が異なる解になっていますね。
# 上の例に適用すると、以下が得られた:
6-element Vector{Float64}:
0.32925817295548304
0.4424222656338847
0.16006488092973709
0.06825468048089517
0.0
0.0
ここで、2つのベクトル pnorm と pnorm2 はどちらも要素の和が（ほぼ）1になるベクトルであり、確率単体に属しています。元の入力である p からそれぞれへのノルムを計算してみましょう。arXivの目的関数がL2ノルムとは特に明記されていないですが、L2ノルムの2乗で計算してみます（LinearAlgebraのnormはデフォルトで2ノルムです、たぶん）。
using LinearAlgebra
d1 = norm(p - pnorm) ^ 2
# 次が得られる:
# 0.2787514468190914
d2 = norm(p - pnorm2) ^ 2
# 次が得られる:
# 0.2276241470295038
以上のことから、雑に計算しがちな手法は、arXivに考える問題の最適解ではなく、別の点に射影されていることが分かりました。
本当にこれでいいの？
arXiv:1309.1541のp.3-4を読んで下さい（投げやり）。
資料
- https://ja.wikipedia.org/wiki/単体_(数学)
- Weiran Wang, Miguel Á. Carreira-Perpiñán, Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application, arXiv:1309.1541.
Discussion