(出題：2014-5-19) - Home Page of Math CM Nagoya Univ.

統計解析特論：第２回レポート課題略解 (出題：2014-5-19)
1. 次の関数 k1 , k2 が正定値カーネルかどうか調べよ．
(1) k1 (x, x′ ) =
1
, x, x′ ∈ R, |x|, |x′ | < 1,
′
2
1 − (xx )
(2) k2 (x, x′ ) = 1 + tanh(xx′ + 1), x, x′ ∈ R.
略解：(1) k0 (x, x′ ) = x′ x は正定値カーネル．したがって (x′ x)k , k ∈ N も正定値カー
∑∞
ネル．k1 (x, x′ ) = k=0 (xx′ )2k (各点収束) より k1 (x, x′ ) は正定値カーネル．
(2) 正定値カーネルでない．x1 , x2 を適当に定めれば，2 × 2 グラム行列が正定値に
ならない例を構成できる．
3. データ Yi , i = 1, . . . , n は
Yi = ϕ(xi )T θ + εi , i = 1, . . . , n,
ε1 , . . . , εn ∼i.i.d. N (0, σ 2 )
で定まる分布にしたがうとする．ここで，入力 x1 , . . . , xn は定数であり，ϕ(x), θ は
d 次元列ベクトルとする．n × d 行列 Φ を
Φ = (ϕ(x1 ), . . . , ϕ(xn ))T
とし，Φ のランクは d とする．パラメータ θ の最小２乗推定量を θb とするとき，点 x
での出力値を Yb (x) = ϕ(x)T θb で予測する．Yb (x) の分散を求めよ．
略解： Y = (y1 , . . . , yn )T ∈ Rn とすると θb = (ΦT Φ)−1 ΦT Y より Yb (x) = ϕ(x)T (ΦT Φ)−1 ΦT Y
となる．Y ∼ N (Φθ, σ 2 In ) より Var[Yb (x)] = ϕ(x)T (ΦT Φ)−1 ΦT (σ 2 In )Φ(ΦT Φ)−1 ϕ(x) =
σ 2 ϕ(x)T (ΦT Φ)−1 ϕ(x)．
4. 行列 Φ を問題で定めた n × d 行列とし，ランクは d とする．n × n 行列 Π を Π =
Φ(ΦT Φ)−1 ΦT とおく．
1. Π の固有値を求めよ．
2. Z ∼ Nn (0, In ) とする．このとき ΠZ と (In − Π)Z は独立であることを示せ．
略解： (1) ΠT = Π, Π2 = Π を満たす．固有値を λ，固有ベクトルを x とすると
Πx = λx，さらに Π を掛けると Π2 x = λΠx = λ2 x，これと Πx = λx が等しいので
λ2 x = λx．また x ̸= 0 より λ2 = λ となる．よって固有値は 0 または 1．
(2) 射影行列 Π の階数が d なので適当な直交変換 Q ∈ Rn×n を施すことで
QΠZ = (Z1 , . . . , Zd , 0, . . . , 0)T ,
Q(In − Π)Z = (0, . . . , 0, Zd+1 , . . . , Zn )T
となる．したがって
ΠZ = QT (Z1 , . . . , Zd , 0, . . . , 0)T ,
(In − Π)Z = QT (0, . . . , 0, Zd+1 , . . . , Zn )T
を得る．Z1 , . . . , Zn は独立なので，ΠZ と (In − Π)Z は独立であることが分かる．
5. k0 : X × X → R を正定値カーネルとする．以下の問に答えよ．
1. ある x0 ∈ X に対して k0 (x0 , x0 ) = 0 となるとき，任意の x ∈ X に対して
k0 (x, x0 ) = 0 となることを示せ．
2. 任意の x ∈ X に対して k0 (x, x) > 0 を仮定する．k(x, x′ ) を
k(x, x′ ) = √
k0 (x, x′ )
k0 (x, x)k0 (x′ , x′ )
と定義する．k(x, x′ ) は正定値カーネルであることを証明せよ．
また |k(x, x′ )| ≤ 1 が成り立つことを示せ．
√
√
略解： (1) |k0 (x, x0 )| = |⟨k0 (·, x), k0 (·, x0 )⟩| ≤ ∥k0 (·, x)∥∥k0 (·, x0 )∥ = k0 (x, x) k0 (x0 , x0 ) =
0 より k0 (x, x0 ) = 0．
(2) k0 (x, x′ ) が正定値カーネルなら任意の関数 g(x) に対して k0 (x, x′ )g(x)g(x′ ) も正
定値カーネル (講義で解説済み)．したがって k(x, x′ ) は正定値カーネル．
6. カーネル関数 k(x, x′ ) を用いたカーネル回帰
min ∥Y − Kβ − b1∥2 + λβ T Kβ
β∈Rn ,b∈R
b bb として，回帰関数を fb(x) = ∑n k(x, xi )βbi + bb で推定
を考える．上の最適解を β,
i=1
する (記号の定義は講義で示したとおり)．最適解 βb が一意でないときでも fb(x) は
一意に定まることを示せ．
補足：問題文に明記していませんでしたが λ > 0 です．
略解：
カーネル関数 k から定まる RKHS を H とすると，表現定理と正則化項の性質から
min
g∈H,b∈R
n
∑
(yi − g(xi ) − b)2 + λ∥g∥2H
i=1
の最適解 gb + b
b と fb は一致する．すなわち gb は span{k(·, x1 ), . . . , k(·, xn )} に含まれ
る (含まれない g は，λ > 0 より最適解になり得ない)．b
b を求めて 2 乗誤差に代入す
ると
)2
n (
n
∑
1∑
yi − g(xi ) −
(yj − g(xj )) + λ∥g∥2H
min
g∈H
n j=1
i=1
となる．上の目的関数は H 上で強凸関数 (λ > 0 を用いる) なので，最適解が存在す
るなら一意に定まる．解の存在は，問題文にある定式化から分かる．よって最適解
は H + R 上で一意に定まる．
統計解析特論：第３回レポート課題略解 (出題：2014-7-14)
問題２：ベイズルールでは，入力 x に対して Pr(Y = 1|x) ≥ Pr(Y = −1|x) なら，Y = 1 を予
測ラベルとし，Pr(Y = 1|x) < Pr(Y = −1|x) なら，Y = −1 を予測ラベルとする．これは
Pr(Y = 1, x) = p(x|Y = 1)Pr(Y = 1) と Pr(Y = −1, x) = p(x|Y = −1)Pr(Y = −1) の大小関係
と同じである．関数 f (x) を
f (x) = log
p(x|Y = 1)Pr(Y = 1)
p(x|Y = −1)Pr(Y = −1)
とすると，予測ラベルは f (x) の符号に対応する．f (x) は x について高々２次であることが分
かる．
問題３：ヒンジ損失 ℓ(z) は |ℓ(z) − ℓ(z ′ )| ≤ |z − z ′ | を満たすので，ℓ(z) のリプシッツ定数は L = 1
以下である．したがって，
[
[
]
]
m
m
∑
∑
1
1
b e(G) ≤ L · Eσ
b S (F)
R
sup
σi yi f (xi ) = Eσ
sup
σi f (xi ) = R
S
m f i=1
m f i=1
問題４：記号の定義：e(h) = E[1[h(X) ̸= Y ]], eb(h) =
1
m
∑m
i=1 [1[h(Xi )
̸= Yi ]].
任意の h ∈ H に対して e(hH ) ≤ e(h) なので e(hH ) ≤ e(b
h) となり，したがって両辺の期待値を
b
b
考えると e(hH ) ≤ E[e(h)] となる．一方，eb(h) ≤ eb(hH ) の期待値をとると
]
[
m
m
∑
1 ∑
1
b
1[hH (Xi ) ̸= Yi ] =
E [1[hH (Xi ) ̸= Yi ]]
E[b
e(h)] ≤ E[b
e(hH )] = E
m i=1
m i=1
1 ∑
e(hH ) = e(hH ).
=
m i=1
m
問題５：以下の等式が成り立つ．
)
( (
n
n
∑
ebλ,c )
c
1∑
1
+ λ∥feλ,c ∥2H
ℓc (yi geλ,c ) + λ∥feλ,c ∥2H =
ℓ yi feλ,c (x) +
n i=1
n i=1
c
c
)
( n ( (
)
ebλ,c )
1∑
1e
=c
+ cλ∥feλ,c /c∥2H .
ℓ yi fλ,c (x) +
n i=1
c
c
上式が最小値を達成していることに注意する．したがって
geλ,c = cgcλ という関係がある．
1 e
f
c λ,c
= fcλ ,
1e
b
c λ,c
= bcλ ，つまり
補足：最適解が一意でないときは，任意の最適解に対して上のような対等がある，ということ．
問題６：全部で n 回蹴るとする，k 回目の PK を考える．
• 先攻が蹴るとき：k − 1 回までに先攻が a 回成功，後攻が b 回成功しているとする．
– 外したら負け ⇔ a + (n − k) < b
– 入れれば勝ち ⇔ a + 1 > b + (n − k + 1)
• 後攻が蹴るとき：k 回までに先攻が a 回成功，k − 1 回までに後攻が b 回成功していると
する．
– 外したら後攻の負け ⇔ b + (n − k) < a
– 入れれば後攻の勝ち ⇔ b + 1 > a + (n − k)
105 回の数値シミュレーションの結果：
Pr(先攻の勝ち) = 0.46331,
Pr(先攻の負け) = 0.42635,
Pr(引き分け) = 0.11034.
R-code の例
prob_to_lose <- 0.44
prob_to_win
<- 0.93
prob_normal
<- 0.70
## n: n kicks
gen_pk <- function(n=5, prob_to_lose=0.44, prob_to_win=0.93, prob_normal=0.70){
A_success <- 0; B_success <- 0;
status <- "even"
for (k in 1:n){
## k-round: A
if(A_success+n-k < B_success){
## A to lose
if(runif(1) < prob_to_lose){
A_success <- A_success + 1
}else{
status <- "A_lose"
break
}
}else if(A_success > B_success+n-k){ ## A to win
if(runif(1) < prob_to_win){
status <- "A_win"
break
}
}else if(runif(1) < prob_normal){## otherwise
A_success <- A_success + 1
}
## k-round: B
if(B_success+n-k < A_success){
## B to lose (a to win)
if(runif(1) < prob_to_lose){
B_success <- B_success + 1
}else{
status <- "A_win"
break
}
}else if(B_success+1 > A_success+n-k){ ## B to win (A to lose)
if(runif(1) < prob_to_win){
status <- "A_lose"
break
}
}else if(runif(1) < prob_normal){## otherwise
B_success <- B_success + 1
}
}
return(status)
}
## pk monte carlo
iterate <- 100000
res <- c()
for (ii in 1:iterate)
res <- c(res,gen_pk(5,prob_to_lose, prob_to_win, prob_normal))
print(c(mean(res=="A_win"),mean(res=="A_lose"),mean(res=="even")))

Download Report