Պ‫ݚ‬අγϯϙδ΢Ϝ
ʮ౷‫ػͱֶܭ‬ցֶशͷ਺ཧͱల։ʯ
Պֶ‫ڀݚ‬අɾ‫ج‬൫‫ڀݚ‬ʢAʣ ʮେ‫ن‬໛ෳࡶσʔλͷཧ࿦ͱํ๏࿦ͷ૯߹త‫ڀݚ‬ʯ‫ڀݚ‬୅දऀɿ੨ౢ ੣ (ஜ೾େֶ)ɽ՝୊൪߸ɿ15H01678
೔࣌ɿ 2019 ೥ 9 ݄ 18 ೔ (ਫ)ʙ19 ೔ (໦)৔ॴɿ ౦‫ۀ޻ژ‬େֶ ੢̔߸‫ؗ̚‬౩̍̌֊ େձٞࣨ։࠵੹೚ऀɿ ۚ৿ ‫ܟ‬จ (౦‫ۀ޻ژ‬େֶ)ϓϩάϥϜɿ
9/18 (ਫ)

9:55 - 10:00

Φʔϓχϯά੨ౢ ੣ (ஜ೾େ)ද‫ֶݱ‬श (࠲௕ɿ઒ౡ)10:00 ∼ 10:35
࿨ా ༟Ұ࿠ (໊େ)
Robust Label Prediction via Label Propagation and Geodesic k-Nearest Neighbor in
Online Semi-Supervised Learning
10:35 ∼ 11:10
ߴ‫( ߉ ڮ‬౦޻େ)૬ؔͷ͋Δಛ௃ྔʹର͢Δ൒ղੳత Stability Selection ๏ಛผߨԋ̍ (࠲௕ɿ઒ౡ)11:20 ∼ 12:05
஛಺ Ұ࿠ (໊޻େ/ཧ‫ ݚ‬AIP)
Selective Inference ʹΑΔ‫ֶ͠ͳࢣڭ‬श݁Ռͷ౷‫ܭ‬త৴པੑධՁ
12:05ʙ13:30 ϥϯνɾϒϨΠΫ౷‫ܭ‬తֶश (࠲௕ɿ‫۽‬୩)

13:30 ∼ 14:05
Ҵ௡ ༎ (ཧ‫ ݚ‬AIP)
ೖྗ͕ίετʹԠͨ͡ϥϯμϜੑΛ࣋ͭ৔߹ͷϨϕϧηοτਪఆͷͨΊͷೳಈֶश
14:05 ∼ 14:40
ߴས ߞ࡞ (ཧ‫ ݚ‬AIP)
Predictive properties of forecast combination, ensemble methods, and Bayesian synthesisΧʔωϧ๏ (࠲௕ɿ‫۽‬୩)

14:50 ∼ 15:25
຀૲ Ն࣮ (ઍ༿େ)࠶ੜ֩ώϧϕϧτۭؒʹ͓͚ΔࣹӨͷϞʔϝϯτʹΑΔೋඪຊ‫ݕ‬ఆ
15:25 ∼ 16:00
দҪ ޹ଠ (ཧ‫ ݚ‬AIP)
Power Series Kernels ʹ‫ͮ͘ج‬ϊϯύϥϝτϦοΫֶशͷͨΊͷม਺બ୒๏
ߴ࣍‫ݩ‬౷‫ ܭ‬I (࠲௕ɿۚ৿)16:15 ∼ 16:50
Atina Husnaqilati (౦๺େ)
Component Retention in PCA Applied to Microarray Datasets
16:50 ∼ 17:25
Լ໺ ण೭ (Digital Garage, Inc.)௒ཱํମʹ಺઀͢Δ௒ପԁ‫ʹٿ‬ΑΔઢ‫ܗ‬ճ‫ؼ‬ͷղऍಛผߨԋ̎ (࠲௕ɿۚ৿)17:35 ∼ 18:20‫ޙ‬౻ ৼҰ࿠ (౷਺‫)ݚ‬Ϛελʔํఔ͔ࣜΒ‫ʹີݫ‬ಘΒΕΔ‫ظ‬଴஋ม਺ͷ৘ใ‫ز‬Կֶɼ઀৮‫ز‬Կֶ͓Αͼͦͷपล

9/19 (໦)σʔλղੳ (࠲௕ɿদҪ)

10:00 ʙ 10:35
ۚ৿ ‫ܟ‬จ (౦޻େ/ཧ‫ ݚ‬AIP)
Similarity Measures and Statistical Models in Recommendation Problems
10:35 ∼ 11:10
৽ଜ लҰ (੒᪟େ)ߴ࣍‫ݩ‬Ҩ఻ࢠղੳͷढ͍͔Βͷղ์ 3 -‫ػ‬ցֶशͳͲͷ޻ֶ‫ڀݚ‬ͷ໰୊఺ಛผߨԋ̏ (࠲௕ɿদҪ)

11:20 ∼ 12:05
ࠤʑ໦ തত (͸ͩͯ͜ະདྷେ)֬཰ີ౓ؔ਺ͷϞʔυ୳ࡧͱͦͷԠ༻

12:05ʙ13:30 ϥϯνɾϒϨΠΫߴ࣍‫ݩ‬౷‫ ܭ‬II (࠲௕ɿߴས)13:30 ∼ 14:05
தࢁ ༏‫( ޗ‬ஜ೾େ)
Asymptotic properties of kernel PCA with Gaussian kernel for high-dimensional data
14:05 ∼ 14:40
ക௡ ༎ଠ (໊޻େ)௒ߴ࣍‫ݩ‬εύʔεՃ๏Ϟσϧʹ͓͚Δม਺બ୒
14:40 ∼ 15:15
઒ౡ ޹ߦ (౦޻େ)ΨϯϚɾμΠόʔδΣϯε࠷খԽʹ‫ͮ͘ج‬ϩόετ͔ͭεύʔεͳճ‫ؼ‬

15:15 ∼ 15:20

Ϋϩʔδϯά

Robust Label Prediction via Label Propagation and Geodesic
k-Nearest Neighbor in Online Semi-Supervised Learning
Yuichiro WADA1 , Siqiang SU2 , Wataru KUMAGAI3 , and Takafumi KANAMORI3,4
1 Nagoya University, Furocho, Chikusaku, Nagoya 464-8601 Japan

2 The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

3 RIKEN AIP, Nihonbashi 1-chome Mitsui Building, 15th floor,1-4-1 Nihonbashi, Chuo-ku,

Tokyo 103-0027 Japan

4 Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552 Japan

1

Introduction

We consider the case in which a few manually labeled data points are provided before the arrival of continuously
streamed unlabeled data points. The goal is to predict the label of the newly arrived data point correctly andquickly under severe memory constraints. To handle above problems, online Semi-Supervised Learning (SSL)
methods have been proposed [1, 2, 3]. These methods adopt a similar strategy: At each time, firstly the data
adjacency graph is recompressed after incorporating a newly arrived data point, and secondly the label of new
data point is predicted by using the graph and an offline semi-supervised algorithm. On one hand, the several
graph compressing algorithms [1, 2, 3] are employed in the first step. On the other hand, the method employedin the second step is often fixed: Label Propagation (LP) [4]. However, LP is not robust against outliers but also
computationally not efficient. The computational compleixity of LP is known as O(n3 ) where n is the number ofdata points. These drawbacks make the online methods underperform.
In this paper, we propose an offline SSL algorithm named Robust Label Prediction (RLP). RLP is not only
more robust against outliers but also more computationally efficient than LP. This proposed method is intended toassist online graph-based SSL algorithms. The efficacy of RLP in creating new online algorithms is demonstrated
in numerical experiments.
l and U = {x }l+u
In the following, the labeled dataset and the unlabeled dataset are denoted by L = {(xi, yi )}i=1
i i=l+1prespectively, where xi 2 R is the feature vector, and yi 2 {1, ..., S} is its label. The total sample size l + u isl , and Ub means the predicted
denoted by n as well. The set Lx means the set of feature vectors in L, i.e., Lx = {xi }i=1l+ub = {(xi, ŷi )}U, i.e., U, where ŷi is the predicted label of xi .
i=l+1

2

Proposed Method

We propose an offline SSL algorithm named RLP. This algorithm consists of three steps. On the basis of theneighbor graph, RLP first selects some unlabeled samples that represent the global structure of the data manifolds.
The selected points are called hub points. The second step assigns labels to hub points by using a special type of
LP. The third step predicts the labels on the remaining unlabeled samples by using Geodesic k-Nearest Neighbor(GkNN) [5]. The detailed procedure of RLP is as follows.
1. Construct the graph G = (Lx [ U, E), where E is defined by k1 NN manner with the Euclidean metric.

2. Build the hub dataset H such that |H| = h, where the elements of H are top h highest degree nodes on G.
Thereafter, define non-hub dataset H̄ by U \ H.
3. Define the geodesic metric dG by computing the graph shortest path distance on graph G.

4. For predicting labels of H, conduct a special type of LP on Lx [ H. In this LP, a different number ofbneighbors k 2 and the predefined geodesic metric dG are employed. The predicted set is denoted by H.
1

Table 1: The averaged prediction accuracy with the standard deviation on unlabeled data in eight real-world data
streams (Yale to USPS). In each dataset, l denotes the number of labeled data obtained before the arrival of eachstream. The size of stream is denoted by T.
(l, T)
Online QRLP Online QLP
Yale(75,85)0.528(0.046) 0.471(0.048)
ORL(80,220)0.722(0.029) 0.656(0.058)
UMNIST(60,240)0.637(0.028) 0.544(0.059)
COIL(80,120)0.660(0.034) 0.592(0.062)
Vowel(100,1300) 0.969(0.004) 0.966(0.002)
MNIST(100,1900) 0.679(0.021) 0.663(0.019)
optdigits(10,4990)
0.971(0.002) 0.961(0.031)
USPS(100,1900) 0.700(0.020) 0.612(0.050)
b Then, by using L, predict the labels of H̄ by conducting GkNN
5. Update the labeled dataset by L
L [ H.
b̄bb
on G with k = k v . Finally, output U = H [ H.

For the theoretical computational complexity of RLP, by summing up each step of above procedure, we can get
O h3 + pn2 + (k 1 + log n)n where  = max{k 2, k v }: see [5]. Since the number of hub data points h is thehyperparameter, by introducing the upper bound to h, we can make RLP faster than LP, i.e., the complexity of RLP
is O(n2 ).

3Numerical Experiment

In this experiment, we evaluate how helpful employing RLP is in online algorithms. The evaluation is based on
the replacement of LP in the previous online SSL algorithm named online Qunatized LP (QLP) [1]. The replaced
method is named online Quantized RLP (QRLP). In both online QLP and online QRLP, Doubling Algorithm [6] isemployed for the graph compressing algorithm. For this evaluation, we applied both methods on eight real-world
datasets. The result is shown in Table 1. Note that the hyperparameters in both methods were already tuned
appropriately before handling the datasets. As we can see in this table, online QRLP outperforms online QLP in
all datasets. Since, except label prediction part, both online methods are the same, we can conclude RLP tend to
be more helpful in creating an online algorithm.

References[1] M. Valko, B. Kveton, L. Huang, and D. Ting, “Online semi-supervised learning on quantized graphs,” inProceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI’10, (Arlington,
Virginia, United States), pp. 606–614, AUAI Press, 2010.
[2] Y. Tao, R. Triebel, and D. Cremers, “Semi-supervised online learning for efficient classification of objects
in 3d data streams,” in Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on,
pp. 2904–2910, IEEE, 2015.
[3] T. Wagner, S. Guha, S. P. Kasiviswanathan, and N. Mishra, “Semi-supervised learning on data streams via
temporal label propagation,” in International Conference on Machine Learning, pp. 5082–5091, 2018.
[4] X. Zhu and Z. Ghahramani, “Learning from labeled and unlabeled data with label propagation,” 2002.
[5] A. Moscovich, A. Jaffe, and B. Nadler, “Minimax-optimal semi-supervised regression on unknown manifolds,”
arXiv preprint arXiv:1611.02221, 2016.
[6] M. Charikar, C. Chekuri, T. Feder, and R. Motwani, “Incremental clustering and dynamic information retrieval,”
SIAM Journal on Computing, vol. 33, no. 6, pp. 1417–1440, 2004.

2૬ؔͷ͋Δಛ௃ྔʹର͢Δ൒ղੳత Stability Selection ๏ߴ‫א ߉ ڮ‬ౡ ঵հɹ౦‫ۀ޻ژ‬େֶɹ৘ใཧ޻ֶӃɹ਺ཧɾ‫ࢉܭ‬Պֶ‫ܥ‬{takahashi, kaba}@sp.dis.titech.ac.jp1

εύʔεઢ‫ܗ‬ճ‫ʹؼ‬ର͢Δ stability selectionʢSSʣ๏ઢ‫ܗ‬ճ‫͚͓ʹؼ‬Δม਺બ୒ͷ໰୊Λߟ͑ΔɻM ‫ݸ‬ͷಠཱͳσʔλ఺ (aµ , yµ ), µ = 1, 2, ..., M ͔ΒͳΔσʔληοτ D ͕͋Δͱ͢Δɻͨͩ͠ɺaµ ∈ RN ͱ yµ ∈ R ͸ͦΕͧΕಛ௃ྔͱԠ౴ม਺Ͱɺyµ = a⊤µ x0 + wµ ,wµ ∼i.i.d. N (0, σ 2 ) ͷؔ܎ʹ͋ΔɻS(x) = supp(x0 ) ͱ͢Δͱɺม਺બ୒ͷ໨త͸ D ͔Β S(x0 ) Λܾఆ͢Δ͜
ͱͰ͋Δɻ͜ͷΑ͏ͳ໰୊͸ɺߴ࣍‫ݩ‬౷‫ͰͲͳֶܭ‬සग़͢Δɻ͔͠͠ɺૉ๿ʹ Lasso Ͱ x0 ͷਪఆ஋ x̂ Λ‫ٻ‬ΊɺS(x̂) Λ S(x0 ) ͷਪఆ஋ͱͯ͠΋ɺಛ௃ྔʹ૬͕ؔ͋Δ৔߹ʹ͸ަࠩ‫ʹূݕ‬Αͬͯબ͹Εͨ࠷దͳਖ਼ଇԽύϥϝʔλΛ༻͍ͯ΋ S(x̂) ̸= S(x0 ) Ͱ͋ΔɻSS ๏ [MB10] ͸ɺLasso ͷม਺બ୒ੑೳΛ޲্ͤ͞ΔͨΊʹఏҊ͞Εͨํ๏Ͱ͋ΔɻSS ๏ͷ‫ج‬ຊతͳΞΠσΟ!
Ξ͸ɺਖ਼ଇԽύϥϝʔλ λ ʹ͍ͭͯద౰ʹઃ‫ͨ͠ܭ‬෼෍ p(λ) = (λi ) Λߟ͑ɺD, λ ͷ྆ํ͕֬཰ม਺Ͱ͋Δ
ͱͯ͠ɺLasso ਪఆྔ x̂ ʹ͍ͭͯ Πi ≡ Prob[x̂i (D, λ) ̸= 0], i = 1, 2, ..., N Λ‫͠ࢉܭ‬ɺΠi ͕େ͖ͳม਺ΛબͿ͜ͱʹ͋Δɻͨͩ͠ɺਅͷ D ͷ෼෍͸ෆ໌Ͱ͋ΔͷͰɺϒʔτετϥοϓ๏Ͱۙࣅ‫͢ࢉܭ‬Δ:#1 "Πi = # b | x̂i (D, c(b) , λ(b) ), b = 1, 2, ..., B , i = 1, 2, .., N,
(1)
B
$ M
&
N
%
1 % (b)(b)
2x̂(D, c(b) , λ(b) ) = arg mincµ (yµ − a⊤x)+
λi |xi | ,(2)µ
x∈RN 2
µ=1
i=1
(b)
c(b)
µ ∼i.i.d. Poisson(cµ ; 1/2),

(b)

λi

∼i.i.d. (δ(λ − 2λ0 ) + δ(λ − λ0 ))/2.

(3)

͜͜ͰɺB ͸ϒʔτετϥοϓσʔληοτͷ਺Ͱ͋Δɻ[MB10] Β͸ɺ͜ͷ Π Λ༻͍ͨม਺બ୒ʹΑͬͯɺ
Lasso Ͱͷม਺બ୒ΑΓ΋ِཅੑ֬཰Λ௿‫͖Ͱݮ‬Δ͜ͱΛࣔͨ͠ɻ͔͠͠ɺΠi ͷ‫ʹࢉܭ‬͸ (2) ࣜͷ࠷దԽ໰୊
Λ B ≫ 1 ճ‫܁‬Γฦ͠ղ͘ඞཁ͕͋ΔɻΠi Λਖ਼֬ʹධՁ͢ΔͨΊʹ͸ B Λେ͖͘ͱΔඞཁ͕͋ΓɺSS ๏ͷ࣮ߦʹ͸શମͱͯ͠େ͖ͳ‫͔͔͕ؒ࣌ࢉܭ‬Δ͜ͱ͕໰୊Ͱ͋Δɻ

2൒ղੳత stability selection ๏ศརͷͨΊɺSS ๏ͷ౷‫ֶྗܭ‬తͳఆࣜԽΛ੔ཧ͢ΔɻBoltzmann ෼෍ p(β) (x|D, c, λ) ΛҎԼͷΑ͏ʹఆٛ͢Δ:p(β) (x | D, c, λ) =

M
N
'
⊤
2 '
1
−β
2 cµ (yµ −aµ x)ee−βλi |xi | ,Z (β) (D, c, λ) µ=1
i=1

(4)

β > 0 ͸‫ٯ‬Թ౓ͱ‫ݺ‬͹ΕΔύϥϝʔλɺZ ͸෼഑ؔ਺ͱ‫ݺ‬͹ΕΔ‫֨ن‬Խఆ਺Ͱ͋Δɻβ → ∞ Ͱ Boltzmann ෼෍((2͸ minx [ µ cµ (yµ − a⊤µ x) /2 +i λi |xi |] Λຬͨ͢ x ্ʹूத͢ΔͷͰɺಛఆͷ c, λ ʹର͢Δ Lasso ਪఆྔ͸)*x̂i (D, c, λ) = lim E xi ; p(β) (x | D, c, λ) ,(5)β→∞ͱॻ͚ΔɻEx [...; p(x)] ͸ p ʹै͏֬཰ม਺ x ʹ͍ͭͯͷ‫ظ‬଴஋Ͱ͋Δɻ࠷ऴ໨ඪ͸ɺࢦࣔؔ਺ 1l(...) ʹର͠ɺ
) + )
*
,*
Πi = Ec,λ [1l(x̂i (c, λ) ̸= 0)] = lim Ec,λ 1l E xi ; p(β) (x | D, c, λ) ̸= 0 ,(6)β→∞Λ‫͢ࢉܭ‬Δ͜ͱͰ͋Δɻ֬཰Ϟσϧͷ‫ظ‬଴஋ͷ‫ͯ͠ͱݶۃ‬ද͢͜ͱͰɺ֬཰తਪ࿦ͷۙࣅٕ๏Λ༻͍қ͘ͳΔɻ
൒ղੳతϦαϯϓϦϯά๏ [MO03] ͸ϨϓϦΧ๏ [MPV87] ͱۙࣅਪ࿦๏Λ૊Έ߹ΘͤΔ͜ͱͰɺSS ๏ͷΑ͏ͳΓαϯϓϦϯά๏ʹ͓͚Δɺਪఆͷ‫܁‬Γฦ͠Λߦ͏͜ͱʹ൐͏‫ྔࢉܭ‬Λ࡟‫͢ݮ‬Δํ๏Ͱ͋Δɻ(6) ͸ BoltzmannՊ‫ݚ‬අγϯϙδ΢Ϝʮ౷‫ػͱֶܭ‬ցֶशͷ਺ཧͱల։ʯใࠂॻ

෼෍ͷϚʔδφϧ෼෍ͷϞʔϝϯτ͕ c, λ ʹͲ͏ґଘ͢Δ͔Λௐ΂Ε͹Α͍͕ɺҰൠʹ r ∈ N ࣍Ϟʔϝϯτͷc, λ ʹର͢Δ‫ظ‬଴஋͸ɺϨϓϦΧ๏ [MPV87] Λ༻͍Δͱ
)+ )
*,r *
)
*
(1)
Ec,λ E xi ; p(β) (x | D, c, λ)= lim Ex(1) xi ; p̃(β) ({x(γ) }nγ=1 ) ,
(7)
n→0
i
$ n -M
.&
N
' ' β
'
(γ)
.
(β)
(γ) n
− 2 cµ (yµ −a⊤x(γ) )2−βλi |xi |µp̃ ({x }γ=1 ) = Ec,λ
e
e
,
(8)
γ=1

µ=1

i=1

.
ͱॻ͚Δɻͨͩ͠ɺ= ͸ʮ‫֨ن‬Խఆ਺·Ͱ‫ؚ‬ΊͯҰகʯΛද͢‫͋Ͱ߸ه‬Δɻ·ͨɺ(7) ͷ n → 0 ͷ‫ݶۃ‬͸ɺ੔਺ͷ n ʹରͯ͠‫ظ‬଴஋ΛධՁ͠ɺn ∈ R ʹ݁ՌΛ֎ૠͯ͠‫ݶۃ‬ΛͱΔ͜ͱΛද͢ɻ͜͜Ͱɺ(8) ͸গͳ͘ͱ΋n = 1, 2, ... ʹରͯ͠͸ɺ(x(1) , ..., x(n) ) ͷஔ‫͍ͯͭʹ׵‬ෆมͰ͋ΔϨϓϦΧରশੑͱ‫ݺ‬͹ΕΔੑ࣭Λ͍࣋ͬͯΔɻ͜ͷͱ͖ɺde Finetti ͷද‫ݱ‬ఆཧ [HS55] ͔Β (8) ͸
$ n
&
/ '
n
'
(β)
(γ) n
(β)
(γ)
(β)
(β)
(γ)
p̃ ({x }γ=1 ) =p (x | ξ)p (ξ)dξ = Eξp (x | ξ) ,
(9)
γ=1

γ=1

ͱॻ͖දͤΔ͸ͣͰ͋Δɻ͜͜Ͱɺξ ͸ c, λ ͷޮՌΛ൓өͨ֬͠཰ม਺Ͱ͋Δɻ͜ͷද‫ݱ‬Λ༻͍ͯಘͨදࣜʹ͍ͭͯ n → 0 ͷ‫ݶۃ‬ΛͱΔͱɺr ࣍Ϟʔϝϯτ (7) ͸ඇৗʹ୯७ʹද͞ΕΔ͜ͱ͕Θ͔Δ:
/ " )
*#r
lim
Ex xi ; p(β) (x | ξ)p(β) (ξ)dξ.
(10)
β→∞

(β)

(β)

͕ͨͬͯ͠ɺp (x | ξ), p (ξ) ͷ β → ∞ Ͱͷۙࣅ෼෍Λ‫ٻ‬ΊΔ͜ͱ͕Ͱ͖Ε͹ɺ‫܁‬Γฦ͠ͷਪఆΛ͢Δ͜ͱ
ͳ͘ɺ೚ҙͷ r ࣍ϞʔϝϯτΛ‫͖Ͱࢉܭ‬ΔɻͦΕʹͱͲ·Βͣɺp(β) (x | ξ), p(β) (ξ) ͷؔ਺‫͔ܗ‬Βɺx̂ ͕ c, λ ʹͲͷΑ͏ʹґଘ͍ͯ͠Δͷ͔Λ࢕͏͜ͱ΋Ͱ͖ΔɻϨϓϦΧ๏Λ༻͍ͯ໰୊Λॻ͖௚͠ɺઌʹϦαϯϓϦϯά
ʹؔ͢Δฏ‫ۉ‬Λͱ͔ͬͯΒۙࣅਪ࿦Λߦ͏ͷ͕ʮ൒ղੳతϦαϯϓϦϯά๏ʯͰ͋Δɻ
্ड़ͷϨϓϦΧ๏Λ༻͍ͨ‫ޙ‬ɺۙࣅਪ࿦Λߦ͏্Ͱ͸ɺ• c, λ Ͱฏ‫ۉ‬Λͱͬͨ෼෍ͷۙࣅ෼෍Λޮ཰తʹ‫ٻ‬ΊΒΕΔ͔• ม਺બ୒ͷ໰୊Λߟ͍͑ͯΔͷͰɺͳΔ΂͘‫ظ‬଴஋Ұகۙࣅ๏ͳͲͷߴਫ਼౓ͳۙࣅ๏Λ༻͍͍͕ͨɺ
ͦͷۙࣅ෼෍Λޮ཰తʹ‫ٻ‬ΊΒΕΔͷ͔͕໰୊ʹͳΔɻલऀ͸ɺ݁‫࡞ૢࣅۙہ‬தʹ c, λ ͷฏ‫͕࡞ૢۉ‬େ͖ͳෛՙΛੜΈग़͞ͳ͍͔ͱ͍͏఺ʹ͍ͭͯͷ‫ݒ‬೦ɺ‫ऀޙ‬͸ۙࣅਪ࿦ٕ๏ࣗମͷ໰୊Ͱ͋Δɻ࣮ࡍɺ[MO03] ͸ߴਫ਼౓ͳۙࣅ෼෍ΛಘΔͨΊͷ൓෮ΞϧΰϦζϜΛఏҊ͠ɺͻͱͨͼ‫ݻ‬ఆ఺͕ಘΒΕΕ͹ߴਫ਼౓ͳ݁ՌΛग़͢͜ͱΛ͕ࣔͨ͠ɺͦͷ൓෮μΠφϛΫε͸‫ۃ‬Ίͯෆ҆ఆͰ͠͹͠͹ൃࢄ͢Δ΋ͷͰ͋ͬͨɻຊ‫Ͱڀݚ‬͸ɺ৘ใཧ࿦ͷϕΫτϧۙࣅϝοηʔδύογϯά๏[RSF17] Λ༻͍ͯɺલड़ͷ‫ݒ‬೦྆ํΛղܾ͢Δۙࣅਪ࿦๏ΛఏҊͨ͠ɻߨԋͰ͸ɺ‫ڀݚ‬ͷϞνϕʔγϣϯɺؔ࿈‫ڀݚ‬ɺۙࣅਪ࿦๏ͷ࿮૊Έɺ͓Αͼٙࣅʗ࣮σʔλΛ༻͍࣮ͨ‫ʹݧ‬ΑΔఏҊख๏ͷੑೳධՁ݁ՌΛ঺հ͢ΔɻΑΓৄࡉͳઆ໌ʹ͍ͭͯͷจ‫ͯ͠ͱݙ‬͸ɺຊߨԋͷ༧ߘɺ͓Αͼ [TK19] Λࢀর͞Ε͍ͨɻࢀߟจ‫ݙ‬[HS55]

Edwin Hewitt and Leonard J Savage, Symmetric measures on cartesian products, Transactions of the American Mathematical Society 80 (1955), no. 2, 470–501.

[MB10]

Nicolai Meinshausen and Peter Bühlmann, Stability selection, Journal of the Royal Statistical Society:
Series B (Statistical Methodology) 72 (2010), no. 4, 417–473.

[MO03]

Dörthe Malzahn and Manfred Opper, A statistical mechanics approach to approximate analytical bootstrap
averages, Advances in Neural Information Processing Systems 15 (S. Becker, S. Thrun, and K. Obermayer,eds.), MIT Press, 2003, pp. 343–350.

[MPV87] Marc Mézard, Giorgio Parisi, and Miguel Virasoro, Spin glass theory and beyond: An introduction to thereplica method and its applications, vol. 9, World Scientific Publishing Company, 1987.
[RSF17] Sundeep Rangan, Philip Schniter, and Alyson K Fletcher, Vector approximate message passing, 2017 IEEE
International Symposium on Information Theory (ISIT), IEEE, 2017, pp. 1588–1592.
[TK19]

Takashi Takahashi and Yoshiyuki Kabashima, Replicated vector approximate message passing for resampling problem, arXiv preprint arXiv:1905.09545 (2019).
2

Selective Inference ʹΑΔ‫ֶ͠ͳࢣڭ‬श݁Ռͷ౷‫ܭ‬త৴པੑධՁҪ্ ໜ৐ 1୩࡚ ޫ༎ 1ക௡ ༎ଠ 11

1Ҵ௡ ༎ 2໊‫ݹ‬԰޻‫ۀ‬େֶ

2௶ా ঙਅ 3ཧԽֶ‫ॴڀݚ‬‫ڮ‬ຊ య໌ 33

ຊ୩ ल‫ ݎ‬1̋஛಺ Ұ࿠ 1,2໊‫ݹ‬԰େֶ͸͡Ίʹσʔλ‫ۦ‬ಈ‫ܕ‬ՊֶͰ͸σʔλʹ‫͍ͯͮج‬Ծઆͷબ୒͕ߦΘΕΔͨΊɼԾઆબ୒όΠΞεͷิਖ਼͕ඞཁͰ͋ΔɽԾ
આબ୒όΠΞεͷิਖ਼Λߦ͏ํ๏ͱͯ͠ɼselective inference ͱ‫ݺ‬͹ΕΔΞϓϩʔν͕஫໨ΛूΊ͍ͯΔ [1, 2, 3].

Selective inference ͸ओʹಛ௃બ୒Λߦͬͨ‫ޙ‬ͷઢ‫ܗ‬Ϟσϧͷ౷‫ܭ‬తਪଌʹ༻͍ΒΕ͖͕ͯͨɼຊ‫Ͱڀݚ‬͸ selective
inference Λ‫ֶ͠ͳࢣڭ‬शͷ݁Ռͷ౷‫ܭ‬తਪଌʹར༻͢ΔɽຊߨԋͰ͸ɼK ฏ‫ۉ‬๏ʹ‫ͮ͘ج‬ΫϥελϦϯάͱάϥϑΧοτʹ‫ͮ͘ج‬ը૾ηάϝϯςʔγϣϯͷ݁ՌΛ selective inference ͷ࿮૊ͰධՁ͢Δํ๏Λ঺հ͢Δ [4, 5]ɽ

2

K ฏ‫ۉ‬๏ʹΑΔΫϥελϦϯάͷ৴པੑධՁ

ຊઅͰ͸ɼK ฏ‫ۉ‬๏ʹΑͬͯΫϥελΛಉఆͨ͠‫ʹޙ‬ɼΫϥελؒͰ֤ಛ௃͕ҟͳΔ͔Ͳ͏͔Λ౷‫ܭ‬తԾઆ‫ݕ‬ఆͷ࿮૊Ͱ൑ఆ͢Δํ๏Λ঺հ͢Δɽ‫؍‬ଌσʔλͱͯ͠ɼd ࣍‫ݩ‬ͷಛ௃Λ࣋ͭ n ‫ݸ‬ͷࣄྫ͕ߦྻ X ∈ Rn×d ͱͯ͠༩͑ΒΕ͍ͯΔͱ͢ΔɽK ฏ‫ۉ‬๏͸֤ΫϥελͷΫϥελத৺ͱΫϥελߏ੒ཁૉͷߋ৽Λ‫܁‬Γฦ͢ΞϧΰϦζ
ϜͰ͋Γɼn ‫ݸ‬ͷࣄྫ͕ K ‫ݸ‬ͷΫϥελʹ෼ׂ͞ΕΔɽΫϥελϦϯάͷεςοϓΛ t = 1, . . . , T ͱද͠ʢT ͸

K ฏ‫ۉ‬๏͕ऩଋ͢Δ·Ͱʹ͔͔ͬͨεςοϓ਺ʣɼ֤εςοϓ t ∈ [T ] ʹ͓͚ΔΫϥελ k ∈ [K] ͷΫϥελத৺ͱΫϥελߏ੒ཁૉΛͦΕͧΕɼmtk ∈ Rd ɼCkt ⊆ [n] ͱද͢ɽ2 ͭͷҟͳΔΫϥελ a ͱ bʢ1 ≤ a ≤ b ≤ K ʣʹ͓͍ͯɼ֤ಛ௃͕Ϋϥελ a ͱ b ͰҟͳΔ͔Ͳ͏͔Λߟ͑Δɽ‫؍‬ଌσʔλ X ͷ֤ཁૉΛฒ΂ͨ n × d ࣍‫ݩ‬ͷϕΫτϧ͕ n × d ࣍‫ݩ‬ਖ਼‫ن‬෼෍ʹै͍ͬͯΔ΋ͷͱ͠ɼͦͷฏ‫ۉ‬ϕΫτϧ͸ະ஌ɼ෼ࢄ‫ڞ‬෼ࢄߦྻ͸‫ط‬஌ͱ͢ΔɽΫϥελ a ͱ b ʹଐ͢Δࣄྫͷಛ௃ j ͷਅͷฏ‫ۉ‬ΛͦΕͧΕɼµa,j ɼµb,j ͱ͠ɼ౷‫ܭ‬తԾઆ‫ݕ‬ఆ

H0 : µa,j = µb,j v.s. H1 : µa,j ̸= µb,j(1)

Λߟ͑Δɽ‫ݕ‬ఆ౷‫ ͯ͠ͱྔܭ‬τ = mTa,j − mTb,j Λ༻͍ɼԾઆ͕σʔλʹ‫͍ͯͮج‬બ୒͞Εͨ͜ͱΛ౿·͑ͯ΋ |τ |͕े෼ʹେ͖͍͔Ͳ͏͔Λ൑ఆ͢Δɽࣜ (1) Ͱ༩͑ΒΕΔԾઆ‫ݕ‬ఆ໰୊͸ɼΫϥελϦϯάΞϧΰϦζϜʹΑͬͯબ୒͞Εͨ΋ͷͰ͋ΔͨΊɼԾઆબ୒όΠΞε͕ੜͯ͡͠·͏ɽԾઆબ୒όΠΞεΛิਖ਼͢ΔͨΊɼselective inference ͷ࿮૊Ͱ͸ɼΫϥελͷબ୒ʹؔ͢ΔΠϕϯτʹ৚݅෇͚ΒΕͨ৚݅෇͖ਪ࿦Λߦ͏ɽΫϥελϦϯά݁ՌΛಘΔͨΊͷΠϕϯτͱͯ͠ɼ֤
εςοϓͷΫϥελߏ੒ཁૉ E := {(Cat , Cbt )}t∈[T ] Λߟ͑Δɽσʔλ X ʹ T εςοϓͷ K ฏ‫ۉ‬๏Λద༻ͯ͜͠

ΕΒͷΫϥελϦϯάͷΠϕϯτ͕ಘΒΕΔࣄ৅Λ E ← C(X) ͱද‫͢ه‬Δɽ͜͜ͰɼRn×d ͷ෦෼ྖҬͱͯ͠ɼX := {X ′ ∈ Rn×d | E ← C(X ′ )} Λߟ͑Δɽ͢ͳΘͪɼ͜ͷ෦෼ྖҬʹ͓͚Δ೚ҙͷ‫؍‬ଌσʔλ X ′ ∈ X ʹରͯ͠ Tεςοϓͷ K ฏ‫ۉ‬๏Λద༻͢ΔͱɼͦͷΠϕϯτ͕‫؍‬ଌσʔλͷ৔߹ͱಉ͘͡ E ͱͳΔ͜ͱΛҙຯ͍ͯ͠Δɽ·ͨɼ྆ଆ‫ݕ‬ఆʹؔ͢Δ‫ࢉܭ‬ͷ౎߹্ɼτ ͷූ߸ʹؔ͢ΔΠϕϯτ΋ಋೖ͠ɼΫϥελϦϯάΠϕϯτͱ τ ͷූ߸͕‫؍‬ଌσʔλʹ͓͚Δ΋ͷͱಉҰʹͳΔΑ͏ͳσʔλۭؒͷ෦෼ྖҬΛ X + ⊆ Rn×d ͱ͢Δɽৄࡉ͸ׂѪ͢Δ͕ɼselective(a,b)

inference ͷ࿮૊Λར༻͢Δ͜ͱͰɼࣜ (1) Ͱ༩͑ΒΕΔԾઆ‫ݕ‬ఆ໰୊ʹର͢Δ selective p-value pjΛ‫͢ࢉܭ‬Δ

(a,b)
(a,b)
͜ͱ͕Ͱ͖ΔɽSelective p-value pj͸ɼX ∈ X + ͷ৚݅ͷ΋ͱ PH0 (pj≤ α | X ∈ X + ) = α ∀α ∈ (0, 1). Λຬͨͨ͢ΊɼԾઆબ୒ͷӨ‫ڹ‬Λഉআͨ͠͏͑Ͱɼ௨ৗͷ p ஋ͱಉ༷ʹ౷‫ܭ‬త৴པੑͷࢦඪͱͯ͠༻͍Δ͜ͱ͕Ͱ͖Δɽͳ͓ɼৄࡉ͸ׂѪ͢Δ্͕‫ه‬ͷΫϥελϦϯάΠϕϯτ X ∈ X + ͕ X ʹؔ͢Δೋ࣍ෆ౳ࣜͱͯ͠ఆࣜԽ
Ͱ͖Δ͜ͱΛར༻ͯ͠ɼselective p-value ͷ‫ߦ͕ࢉܭ‬ΘΕ͍ͯΔɽ

3άϥϑΧοτʹΑΔը૾ηάϝϯςʔγϣϯ݁Ռͷ৴པੑධՁ

ຊઆͰ͸ɼάϥϑΧοτʹΑͬͯը૾ΛΦϒδΣΫτྖҬͱόοΫάϥ΢ϯυྖҬʹ෼ׂ͢ΔηάϝϯςʔγϣϯΛߦͬͨࡍʹɼ2 ͭͷྖҬͷ͕ࠩ౷‫ܭ‬తʹ༗ҙͰ͋Δ͔Λ‫͢ূݕ‬Δ͜ͱʹΑͬͯηάϝϯςʔγϣϯ݁Ռͷ৴པੑධՁΛߦ͏ํ๏Λ঺հ͢Δɽ‫؍‬ଌը૾ͱͯ͠ɼn ‫ݸ‬ͷϐΫηϧ͔Β੒Δը૾͕ n ࣍‫ݩ‬ϕΫτϧ x ∈ Rn ͱͯ͠༩͑ΒΕ͍ͯΔͱ͢Δɽ֤ϐΫηϧΛϊʔυͱ͠ɼྡ઀͢ΔϐΫηϧؒʹΤοδΛ࣋ͭάϥϑΛߟ͑ɼ֤ΤοδʹϐΫηϧ஋͕ࣅ͍ͯΔ΄Ͳߴ͍஋Λ࣋ͭΑ͏ͳॏΈΛׂΓ౰ͯΔɽάϥϑΧοτʹΑΔηάϝϯςʔγϣϯͰ͸ɼॏΈ෇͖άϥϑΛ෼ׂ͢Δ͜ͱͰը૾ΛΦϒδΣΫτྖҬͱόοΫάϥ΢ϯυྖҬ΁෼ׂ͢Δৄࡉ͸ׂѪ͢Δ͕ɼ
άϥϑΧοτʹΑΔηάϝϯςʔγϣϯ͸ॏΈ෇͖༗޲άϥϑͷ࠷େϑϩʔ໰୊ͱͯ͠ఆࣜԽ͞Εɼޮ཰తʹղ͘͜ͱ͕Ͱ͖ΔɽάϥϑΧοτʹΑͬͯ෼ׂ͞ΕͨΦϒδΣΫτྖҬͱόοΫάϥ΢ϯυྖҬͷϐΫηϧ ID ͷू߹ΛͦΕͧΕ O ∈ [n]ɼB ∈ [n] ͱ͢Δɽ֤ըૉΛฒ΂ͨ n ࣍‫ݩ‬ϕΫτϧ x ͕ n ࣍‫ݩ‬ਖ਼‫ن‬෼෍ʹै͍ͬͯΔ΋ͷͱ͠ɼͦͷฏ‫ۉ‬ϕΫτϧ͸ະ஌ɼ෼ࢄ‫ڞ‬෼ࢄߦྻ͸‫ط‬஌ͱ͢Δɽ

ΦϒδΣΫτྖҬͱόοΫάϥ΢ϯυྖҬͷ͕ࠩे෼ʹେ͖͍͔Ͳ͏͔Λ౷‫ܭ‬తʹఆྔԽ͢ΔͨΊɼ྆ऀͷըૉ஋ͷਅͷฏ‫ۉ‬ΛͦΕͧΕɼµO ɼµB ͱ͠ɼԾઆ‫ݕ‬ఆ໰୊

H0 : µO = µB v.s. H1 : µO ̸= µB(2)

Λߟ͑Δɽ‫ݕ‬ఆ౷‫ ͯ͠ͱྔܭ‬τ = mO − mB Λ༻͍ɼԾઆ͕σʔλʹ‫͍ͯͮج‬બ୒͞Εͨ͜ͱΛ౿·͑ͯ΋ |τ | ͕!
!
े෼ʹେ͖͍͔Ͳ͏͔Λ൑ఆ͢Δɽͨͩ͠ɼmO = |O|−1 i∈O xi ɼmB = |B|−1 i∈B xi Ͱ͋Δɽ

ࣜ (2) Ͱ༩͑ΒΕΔԾઆ‫ݕ‬ఆ໰୊͸ɼάϥϑΧοτηάϝϯςʔγϣϯΞϧΰϦζϜʹΑͬͯબ୒͞Εͨ΋ͷͰ͋ΔͨΊɼԾઆબ୒όΠΞε͕ੜͯ͡͠·͏ɽԾઆબ୒όΠΞεΛิਖ਼͢ΔͨΊɼselective inference ͷ࿮૊Ͱ͸ɼηάϝϯςʔγϣϯʹؔ͢ΔΠϕϯτʹ৚݅෇͚ΒΕͨ৚݅෇͖ਪ࿦Λߦ͏ɽάϥϑΧοτΞϧΰϦζϜʹΑͬͯηάϝϯςʔγϣϯ݁ՌΛಘΔͨΊͷΠϕϯτΛ E ͱ͠ɼը૾σʔλ x ʹάϥϑΧοτΛద༻ͯ͠Πϕϯτ E ͕ಘΒΕͨࣄ৅Λ E ← S(x) ͱද‫͢ه‬Δɽ͜͜ͰɼRn ͷ෦෼ྖҬͱͯ͠ɼX := {x′ ∈ Rn | E ← S(x′ )} Λߟ͑Δɽ
͢ͳΘͪɼ͜ͷ෦෼ྖҬʹ͓͚Δ೚ҙͷ‫؍‬ଌσʔλ x′ ∈ X ʹରͯ͠άϥϑΧοτΛద༻͢ΔͱɼͦͷΠϕϯτ͕‫؍‬ଌσʔλͷ৔߹ͱಉ͘͡ E ͱͳΔ͜ͱΛҙຯ͍ͯ͠Δɽৄࡉ͸ׂѪ͢Δ͕ɼselective inference ͷ࿮૊Λར༻͢
Δ͜ͱͰɼࣜ (2) Ͱ༩͑ΒΕΔԾઆ‫ݕ‬ఆ໰୊ʹର͢Δ selective p-value p(O,B) Λ‫͢ࢉܭ‬Δ͜ͱ͕Ͱ͖ΔɽSelective

p-value p(O,B) ͸ɼx ∈ X ͷ৚݅ͷ΋ͱ PH0 (p(O,B) ≤ α | x ∈ X ) = α ∀α ∈ (0, 1) Λຬͨͨ͢ΊɼԾઆબ୒ͷӨ‫ڹ‬Λഉআͨ͠͏͑Ͱɼ௨ৗͷ p ஋ͱಉ༷ʹ౷‫ܭ‬త৴པੑͷࢦඪͱͯ͠༻͍Δ͜ͱ͕Ͱ͖Δɽͳ͓ɼৄࡉ͸ׂѪ͢Δ্͕‫ه‬ͷάϥϑΧοτͷΠϕϯτ x ∈ X ͕ɼҰ෦ͷඇઢ‫਺ؔܗ‬ͷೋ࣍εϓϥΠϯۙࣅΛಋೖ͢Ε͹ɼx ʹؔ͢
Δೋ࣍ෆ౳ࣜͱͯ͠ఆࣜԽͰ͖Δ͜ͱΛར༻ͯ͠ɼselective p-value ͷ‫ߦ͕ࢉܭ‬ΘΕ͍ͯΔɽ

4

͓ΘΓʹ

ຊߨԋͰ͸ɼselective inference ͷ‫ج‬ຊతͳߟ͑ํͱɼͦΕͧΕͷ໰୊ʹ͓͚Δ selective p-value ͷ۩ମత‫ࢉܭ‬๏Λઆ໌͢ΔɽΫϥελϦϯά݁Ռͷਪ࿦ͷ໰୊Ͱ͸γϯάϧηϧղੳͷ෼ੳʹద༻ͨ͠ྫΛɼηάϝϯςʔγϣϯ݁Ռͷਪ࿦ͷ໰୊Ͱ͸පཧը૾ͷ෼ੳʹద༻ͨ݁͠ՌΛ঺հ͢Δɽࢀߟจ‫ݙ‬[1] Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor. Exact post-selection inference, withapplication to the lasso. The Annals of Statistics, 44(3):907–927, 2016.
[2] William Fithian, Dennis Sun, and Jonathan Taylor. Optimal inference after model selection. arXiv preprint
arXiv:1410.2597, 2014.
[3] Jonathan Taylor and Robert J Tibshirani. Statistical learning and selective inference. Proceedings of the
National Academy of Sciences, 112(25):7629–7634, 2015.
[4] Inoue S., Umezu Y., Tsubota S., Suzuki K., duVerle DA., Kadomatsu K., Tsuda K., and Takeuchi I.
Valid statistical method for cluster-specific diﬀerentially-expressed genes in single-cell rna-sequencing by
post-clustering inference. in preparation, 2019.
[5] Tanizaki K., Inatsu Y., Hashimoto N., Hontani H., and Takeuchi I. Computing valid p-values for image
segmentation by selective inference. arXiv:1906.00629, 2019.

ೖྗ͕ίετʹԠͨ͡ϥϯμϜੑΛ࣋ͭ৔߹ͷϨϕϧηοτਪఆͷͨΊͷೳಈֶशҴ௡ ༎ 11ཧԽֶ‫৽ֵॴڀݚ‬஌ೳ౷߹‫ڀݚ‬ηϯλʔ32

஛಺ Ұ࿠ 1,2,3

໊‫ݹ‬԰޻‫ۀ‬େֶ ৘ใ޻ֶઐ߈ɾ৘ใՊֶϑϩϯςΟΞ‫ڀݚ‬Ӄ෺࣭ɾࡐྉ‫ ߏػڀݚ‬৘ใ౷߹‫ܕ‬෺࣭ɾࡐྉ‫఺ڌڀݚ‬1. ֓ཁධՁίετ͕ߴ͍ black-box ؔ਺͕, ͋Δᮢ஋Λ্ճΔྖҬͱԼճΔྖҬΛಉఆ͢Δ໰୊ΛϨϕϧηοτਪఆ (LSE) ໰୊ͱ͍͏. LSE ͸‫ڥ؀‬ϞχλϦϯά΍‫ڐ‬༰Մೳͳύϥϝʔλۭؒͷαϒηοτͷಉఆ౳ͷλεΫʹ༻͍ΒΕ͓ͯΓ ([1]), ࣮Ԡ༻ʹ͓͍ͯॏཁͳλεΫͱͳ͍ͬͯΔ. ·ͨ, ࣮Ԡ༻ʹ͓͍ͯ͸, ೖྗ͕ίετʹԠͨ͡ϥϯμϜੑΛ࣋ͭͱ૝ఆͰ͖Δ(e.g., λϯύΫ࣭ͷΞϛϊࢎ഑ྻͷվม࣮‫ )ݧ‬৔߹͕͋Δ. ຊ‫Ͱڀݚ‬͸, Ψ΢εաఔ (GP) ͱͦΕʹ‫ͮ͘ج‬৴༻۠ؒΛ༻͍, ߋʹ, [2] ʹΑͬͯఏҊ͞Εͨ‫ظ‬଴෼ྨ૿Ճྔʹ‫͍֫ͨͮج‬ಘؔ਺Λ֦ு͢Δ͜ͱͰ, ೖྗ͕ίετʹԠͨ͡ϥϯμϜੑΛ࣋ͭ৔߹ͷ LSE ͷͨΊͷೳಈֶश๏ΛఏҊ͢Δ.

2. ઃఆ
ؔ਺ f : D → R Λ, D ⊂ Rd Ͱఆٛ͞ΕͨධՁίετ͕ߴ͍ black-box ؔ਺ͱ͢Δ. ֤ೖྗ x ∈ D ʹର͠, ؔ਺ f (x) ͷ஋͸ f (x) + ε ͱͯ͠‫؍‬ଌ͞ΕΔͱ͢Δ. ͨͩ͠, ε ͸ਖ਼‫ن‬෼෍ N (0, σ 2 ) ʹै͏, ಠཱͳϊΠζͰ͋Δ. ͜ͷͱ͖, D ͷ༗‫ݶ‬෦෼ू߹ Ω ্Ͱͷ, f ʹର͢Δ Level set estimation (LSE) Λߟ͑Δ:

Definition 2.1. ᮢ஋Λ h ͱ͢Δ. ͜ͷͱ͖, f ʹର͢Δ্Ґू߹ H ͓ΑͼԼҐू߹ L Λ
H = {x ∈ Ω | f (x) > h}, L = {x ∈ Ω | f (x) ≤ h}

(2.1)

ͰఆΊΔ.
ߋʹ, ຊߘͰ͸, ೖྗʹର͠ίετʹґଘͨ͠ෆ࣮֬ੑ͕൐͏ঢ়‫گ‬Λߟ͑Δ. ίετ c1 , . . . , ck ͸, 0 < c1 < c2 < · · · < ckΛຬͨ͢ͱ͢Δ. ֤ίετ ci , i ∈ {1, . . . , k} ≡ [k] ͱೖྗ x ∈ Ω ʹର͠, x Λೖྗͨ͠ࡍʹ࣮ࡍʹೖྗ͞ΕΔ஋ s(x, ci ) ͸(c )֬཰ม਺ S(x, ci ) ͔ΒͷϥϯμϜඪຊͱ͢Δ. ͨͩ͠, s(x, ci ) ∈ D ͔ͭ S(x, ci ) ͸‫ط‬஌ͷີ౓ؔ਺ g(s|θx i ) Λ࣋ͭͱ͢Δ. ͜ͷઃఆͷԼ, ૯ίετΛͰ͖Δ͚ͩখ্ͭͭ͘͞͠Ґू߹ H ͓ΑͼԼҐू߹ L Λಉఆ͢Δ͜ͱΛ໨ඪͱ͢Δ.

3. Ϩϕϧηοτਪఆ
·ͣ, ະ஌ؔ਺ f ʹର͢ΔϞσϦϯάͱͯ͠, Ψ΢εաఔ (GP) Λ༻͍Δ. ؔ਺ f ʹର͢Δࣄલ෼෍ʹ GP, GP(0, k(s, s′ ))ΛԾఆ͢Δ. ͜͜Ͱ, k(s, s′ ) : D × D → R ͸ਖ਼ఆ஋ΧʔωϧͰ͋Δ. ͢ͳΘͪ, ೖྗͱ‫؍‬ଌͷ૊ {(sj (xj , cij ), yj }tj=1 ͕༩͑ΒΕͨͱ͖, f ͷࣄ‫ޙ‬෼෍͸࠶ͼ GP ͱͳΓ, f (x) ͷࣄ‫ޙ‬ฏ‫ ۉ‬µt (x), ࣄ‫ޙ‬෼ࢄ σt2 (x) ͓Αͼ‫ڞ‬෼ࢄ kt (x, x′ ) ͸ͦΕͧΕҎԼͰ༩͑ΒΕΔ:µt (x) = kt (x)⊤ Ct−1 yt , σt2 (x) = kt (x, x), kt (x, x′ ) = k(x, x′ ) − kt (x)⊤ Ct−1 kt (x′ ).
͜͜Ͱ, kt (x) = (k(s1 (x1 , ci1 ), x), . . . , k(st (xt , cit ), x))⊤ , Ct = (Kt + σ 2 It ), yt = (y1 , . . . , yt )⊤ ͓Αͼ It ͸ t ࣍୯ҐߦྻͰ͋Δ.
࣍ʹ, ֤఺ x ∈ Ω ʹର͠, ୈ t ࢼߦ࣌ʹ͓͚Δ f (x) ʹର͢Δ৴༻۠ؒΛ Qt (x) = [lt (x), ut (x)] ͰఆΊΔ. ͨͩ͠,lt (x) = µt (x) − β 1/2 σt (x), ut (x) = µt (x) + β 1/2 σt (x) Ͱ͋Γ, β 1/2 ≥ 0 Ͱ͋Δ. ͜ͷͱ͖, ਫ਼౓ύϥϝʔλ ϵ > 0 Λ༻͍
ͯ, H ͓Αͼ L ΛҎԼͷ Ht ͓Αͼ Lt Λ༻͍ͯਪఆ͢Δ:

Ht = {x ∈ Ω | lt (x) > h − ϵ}, Lt = {x ∈ Ω | ut (x) < h + ϵ}.
ߋʹ, ະ෼ྨू߹Λ Ut = Ω \ (Ht ∪ Lt ) ͱఆ͓ٛͯ͘͠.

1

(3.1)

4. ఏҊ๏ೖྗ͕ίετʹԠͨ͡ϥϯμϜੑΛ࣋ͭ৔߹ͷ LSE ͷͨΊͷೳಈֶश๏ΛఏҊ͢Δ. ͦͷͨΊʹ, ࣍ʹධՁ͢΂͖ೖྗ఺͓Αͼ, ͦͷೖྗ఺ͷ‫؍‬ଌʹඅ΍͢ίετΛܾఆ͢ΔͨΊͷ֫ಘؔ਺Λ༩͑Δ. ຊ‫Ͱڀݚ‬͸, [2] ͱࣅͨߟ͑ํΛ࠾༻͢Δ. [2]ͷߟ͑ํ͸, ৽ͨͳ఺͕ՃΘͬͨͱ͖ͷ෼ྨ਺ͱ‫ࡏݱ‬ͷ෼ྨ਺ͷ͕ࠩ, ‫ظ‬଴஋తʹ࠷΋େ͖͘ͳΔ఺Λ࣍ͷධՁ఺ͱ͢Δͱ͍
͏ߟ͑ํͰ͋Δ. Ұํ, ຊ‫ڀݚ‬ͷઃఆ͸, ೖྗ͕ίετʹґଘͨ͠ෆ࣮֬ੑΛ࣋ͭͨΊ, ൴Βͷ֫ಘؔ਺Λ௚઀ར༻͸Ͱ͖ͳ
͍. ͦ͜Ͱ, ‫ظ‬଴෼ྨ૿Ճྔͷೖྗͷ෼෍ʹؔ͢Δ‫ظ‬଴஋ΛίετͰׂͬͨ΋ͷΛߟ͑Δ. ͢ͳΘͪ, ୯Ґίετ͋ͨΓͷ, ೖྗͷෆ࣮֬ੑΛߟྀͨ͠, ‫ظ‬଴஋తͳ෼ྨ૿ՃྔΛߟ͑Δ. ߋʹ, ϵ-greedy ͷߟ͑ํͱ૊Έ߹ΘͤΔ͜ͱͰ, ΞϧΰϦζϜ͕֬཰ 1 Ͱऩଋ͢Δ͜ͱΛอূͰ͖Δ.
͸͡Ίʹ, ୯Ґίετ͋ͨΓͷೖྗͷෆ࣮֬ੑΛߟྀͨ͠‫ظ‬଴஋తͳ෼ྨ૿ՃྔΛఆٛ͢Δ. ఺ s∗ Λ͋Βͨͳೖྗ఺ͱ͠,∗y = f (s∗ ) + ε ͕ಘΒΕͨͱ͢Δ. ૊ (s∗ , y ∗ ) ͕௥Ճ͞Εͨͱ͖ͷ, H ͓Αͼ L ͷਪఆू߹Λ Ht (s∗ , y ∗ ), Lt (s∗ , y ∗ ) ͱॻ͘. ͜ͷͱ͖, ೖྗ఺ x ∈ Ω ͷ‫؍‬ଌʹίετ ci Λ͔͚ͨͱ͖ͷ, ୯Ґίετ͋ͨΓͷೖྗͷෆ࣮֬ੑΛߟྀͨ͠, ‫ظ‬଴஋తͳ෼ྨ૿Ճྔ at (x, ci ) ͸ҎԼͰ༩͑ΒΕΔ:

at (x, ci ) = c−1i!

Ey∗ [|Ht (s∗ , y ∗ ) ∪ Lt (s∗ , y ∗ )| − |Ht ∪ Lt |]g(s∗ |θx(ci ) )ds∗ .

(4.1)

ͳ͓, ࣜ (4.1) தͷ‫ظ‬଴஋͸ղੳ‫ܗ‬Λ͕࣋ͭ, ͜͜Ͱ͸লུ͢Δ.
࣍ʹ, ϵ-greedy ઓུʹ‫͍ͨͮج‬, ૊ (x, ci ) Λ֬཰తʹબͿํ๏ʹ͍ͭͯઆ໌͢Δ. ू߹ C Λ C = {(x, ci ) | x ∈ Ω, i ∈ [k]}ͱ͓ͯ͘͠. ֬཰ม਺ Ct Λ C ͷ‫ʹݩ‬஋ΛऔΔ཭ࢄ֬཰ม਺ͱ͠, ͦͷ֬཰ؔ਺͸ҎԼͰ༩͑ΒΕΔͱ͢Δ:

pCt (x, ci ) = P(Ct = (x, ci )).

(4.2)

͜ͷͱ͖, ίετຖʹҰ༷ͳ֬཰Λ࣋ͭҎԼͷ֬཰ؔ਺Λߟ͑Δ:

Definition 4.1. ֤ i ∈ [k] ʹର͠, κi Λ 0 < κi < 1 Λຬͨ͠, ͔ͭΛҎԼͰఆΊΔ:"ki=1 |Ω|κi = 1 Λຬͨ͢ͱ͢Δ. ͜ͷͱ͖, pCt (x, ci )pCt (x, ci ) = κi .

(4.3)࠷‫ʹޙ‬, ࣜ (4.1) ͱ (4.3) Λ༻͍ͨఏҊΞϧΰϦζϜʹ͍ͭͯड़΂Δ. ຊߘͰఏҊ͢ΔΞϧΰϦζϜ͸, ֤ࢼߦ࣌ʹ͓͍ͯ,֬཰ 1 − pt , 0 ≤ pt ≤ 1 Ͱ (4.1) Λ࠷େͱ͢Δ૊ (x, ci ) Λબͼ, ֬཰ pt Ͱ (4.3) ʹ‫͖ͮج‬૊ (x, ci ) ΛબͿ΋ͷͰ͋Δ.
ຊ‫͚͓ʹڀݚ‬Δ, ͍͔ͭ͘ͷཧ࿦݁Ռ͓Αͼ਺஋࣮‫ݧ‬ͷ݁Ռʹ͍ͭͯ͸౰೔ใࠂ͢Δ.

ँࣙຊ‫ڀݚ‬ͷҰ෦͸ɼՊֶ‫ڀݚ‬අʢ17H00758, 16H06538ʣ, JST CREST (JPMJCR1302,JPMJCR1502), ཧԽֶ‫৽ֵॴڀݚ‬஌ೳ౷߹‫ڀݚ‬ηϯλʔ, JST Πϊϕʔγϣϯϋϒߏஙࢧԉࣄ‫ۀ‬ɾ৘ใ౷߹‫ܕ‬෺࣭ɾࡐྉ։ൃΠχγΞςΟϒͷิॿΛड͚ͯߦΘΕͨɽࢀߟจ‫ݙ‬[1] Alkis Gotovos, Nathalie Casati, Gregory Hitz, and Andreas Krause. Active learning for level set estimation. In
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 1344–1350, 2013.
[2] Andrea Zanette, Junzi Zhang, and Mykel J Kochenderfer. Robust super-level set estimation using gaussian processes. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 276–291.
Springer, 2018.

2

Predictive properties of forecast combination,ensemble methods, and Bayesian synthesis
Kosaku Takanashi⇤ & Kenichiro McAlinn†

Forecast combination has recently received a surge in interest across multiple fields due toan increase in usage of more complex models, added with the increasing availability of density
forecasts. In statistics, especially in the Bayesian literature, Bayesian model averaging (BMA) has
been a staple, with theoretical justification under certain conditions and recent developments to
topical problems in statistics. In machine learning, ensemble methods, including boosting, bagging,and stacking, have been used extensively to mitigate overfitting, which machine learning algorithms
tend to do and benefit from in certain contexts. In econometrics, the field is stimulated by theincreased availability of formal forecasting models that yield full density forecasts and the need to
improve information flows to policy and decision makers.
We contribute to the growing literature of forecast combination, model averaging, and ensemble
learning by developing a novel strategy based on continuous time stochastic processes to evaluate
and assess the theoretical predictive properties of classes of combination strategies. Our development is motivated by the recently introduced Bayesian predictive synthesis (BPS) (McAlinn andWest 2017; McAlinn et al. 2017), which is a general Bayesian framework for forecast combinationthat encompasses other methods as special cases. The motivation is driven by the fact that a certainclass of BPS, proposed in the papers, substantially improve forecasts over standard and advanced
benchmarks in the literature. We show that this class of synthesis defines a broader class of what
we call non-linear synthesis. We further show that this class has properties that we identify as thesource of improved predictive performance; namely an extra term in the stochastic process thatacts as a shrinkage term on the error process. Finally, we prove that this class of BPS outperforms
any and all linear combination of forecasts, including popular methods such as Bayesian model
averaging, equal weight averaging, etc. We note that our development of using continuous timestochastic processes to evaluate predictive performances opens up several avenues of research that
goes beyond the analysis conducted in this paper and has further potential to be applied to othercontexts.
⇤†

RIKEN AIP, Tokyo, Japan. Email: kosaku.takanashi@riken.jp
Booth School of Business, University of Chicago, Chicago, IL 60637. Email: kenichiro.mcalinn@chicagobooth.edu

References
McAlinn, K., Aastveit, K. A., Nakajima, J., West, M., 2017. Multivariate bayesian predictive synthesis
in macroeconomic forecasting. arXiv preprint arXiv:1711.01667.
McAlinn, K., West, M., 2017. Dynamic bayesian predictive synthesis in time series forecasting.
Journal of Econometrics Forthcoming.

1࠶ੜ֩ώϧϕϧτۭؒʹ͓͚ΔࣹӨͷϞʔϝϯτʹΑΔ
ೋඪຊ‫ݕ‬ఆઍ༿େɾ༥߹ཧ޻ֶ෎ɹ຀૲ Ն࣮

1 ͸͡Ίʹ
i.i.d.

i.i.d.

P ɼQ Λώϧϕϧτۭؒ H ্ͷ֬཰෼෍ͱ͢Δͱ͖ɼೋඪຊ X1 , . . . , Xn ∼ P ɼY1 , . . . , Ym ∼Q ʹ‫ݕͮ͘ج‬ఆ‫ؼ‬ແԾઆ H0 : P = Q vs. ରཱԾઆ H1 : P ̸= QΛߟ͑ΔɽϢʔΫϦουۭؒͰͷೋඪຊ‫ݕ‬ఆ͸͢Ͱʹ༷ʑͳ‫ݕ‬ఆํ๏͕ٞ࿦͞Ε͍ͯΔ͕ɼώϧϕϧτۭؒʹ஋ΛͱΔ֬཰ม਺ʹର͢Δೋඪຊ‫ݕ‬ఆΛߟ͑Δ͜ͱͰɼߴ࣍‫ݩ‬σʔλʹର͢Δೋඪຊ‫ݕ‬ఆͷٞ࿦Λ༩͑Δɽߴ࣍‫ݩ‬σʔλʹର͢ΔΞϓϩʔνͱͯ͠ɼΧʔωϧ๏ͱ͍͏ํ๏͕͋ΔɽΧʔωϧ๏Λ༻͍ͨೋඪຊ‫ݕ‬ఆͱͯ͠ɼMaximum Mean Discrepancy(MMD) ʹ‫ͮ͘ج‬ೋඪຊ‫ݕ‬ఆ͕

[1] ʹΑΓ͢Ͱʹٞ࿦͞Ε͍ͯΔ͕ɼ͜ͷ MMD ͱಉ༷ͷߟ͑ํʹΑΓɼ2 ࣍ͷΧʔωϧͷ MMD
ʹΑΔೋඪຊ‫ݕ‬ఆΛߟ͑Δɽ

2 ࠶ੜ֩ώϧϕϧτۭؒͰͷϞʔϝϯτͷఆٛ֬཰ม਺ X ∼ P ɼY ∼ Q Λਖ਼ఆ஋Χʔωϧ k ʹΑͬͯɼ͜ͷ k ʹରԠ͢Δ࠶ੜ֩ώϧϕϧτۭؒ H(k) ্ʹɼͦΕͧΕ k(·, X)ɼk(·, Y ) ʹΑΓม‫׵‬Λߦ͏ɽ͜ͷͱ͖ɼ͜ͷ k(·, X)ɼk(·.Y ) ͷฏ‫·ۉ‬ΘΓͷ 2 ࣍Ϟʔϝϯτ Σk (P )ɼΣk (Q) ͸ɼͦΕͧΕώϧϕϧτۭؒ H(k)⊗2 = H(k) ⊗ H(k)Ͱͷ‫ظ‬଴஋ Σk (P ) = EX∼P [(k(·, X) − µ(P ))⊗2 ]ɼΣk (Q) = EY ∼Q [(k(·, Y ) − µ(Q))⊗2 ] ʹΑͬͯఆΊΒΕ͍ͯΔɽ͜͜Ͱɼµ(P )ɼµ(Q) ͸ k(·, X) ͷ 1 ࣍Ϟʔϝϯτ µ(P ) = EX∼P [k(·, X)]ɼµ(Q) = EY ∼Q [k(·, Y )] Ͱ͋Γɼ⊗ ͸ςϯιϧੵΛද͓ͯ͠Γɼ೚ҙͷ f ∈ H(k) ʹର͠ɼf ⊗2 =f ⊗ f = ⟨f, ·⟩H(k) f Ͱ͋Δɽ

3 ‫ݕ‬ఆ౷‫ྔܭ‬ͷߏங͜ͷ k(·, X) ͱ k(·, Y ) ͷ f ∈ H(k) ΁ͷࣹӨͷϞʔϝϯτࠩ

sup||f ||H(k) =1| ⟨f, µ(P ) − µ(Q)⟩H(k) | = ||µ(P ) − µ(Q)||H(k)ʹΑΓɼ2 ͭͷ෼෍ͷҧ͍ΛଌΔͷ͕ɼMaximum Mean Discrepancy (MMD) ͱ‫ݺ‬͹ΕΔ΋ͷͰ
͋Δɽಉ༷ͷߟ͑ํʹΑΓɼ(k(·, X) − µ(P ))⊗2 ͱ (k(·, Y ) − µ(Q))⊗2 ͷ A ∈ H(k)⊗2 ΁ͷࣹӨͷϞʔϝϯτࠩ

sup||A||H(k)⊗2 =1| ⟨A, Σk (P ) − Σk (Q)⟩H(k)⊗2 | = ||Σk (P ) − Σk (Q)||H(k)⊗2ʹΑΓ 2 ͭͷ෼෍ͷҧ͍ΛଌΔɽ͜Ε͸ɼMMD ͷΑ͏ͳ͋Δछͷ෼෍ͷҧ͍Λଌ͍ͬͯΔɽ͜ͷҧ͍ ∥Σk (P ) − Σk (Q)∥2H(k)⊗2 ͸

""
""2
""!
""
!
T!2 = ""Σ
(P
)
−
Σ
(Q)
""
k
k

H(k)⊗2ʹΑͬͯਪఆ͢Δ͜ͱ͕Ͱ͖Δɽͨͩ͠ɼ

n
n
1#
1#
⊗2
!
Σk (P ) =(k(·, Xi ) − µ!(P )) , µ!(P ) =
k(·, Xi ),
n i=1
n i=1

Ͱ͋Δɽ

m
m
#
1 #
! k (Q) = 1Σ(k(·, Yi ) − µ!(Q))⊗2 , µ!(Q) =
k(·, Yi )
m i=1
m i=1

ຊൃදͰ͸ɼ͜ͷ‫ݕ‬ఆ౷‫ ྔܭ‬T!2 ͷ઴ۙ‫ڍ‬ಈʹ͍ͭͯใࠂΛߦͬͨɽಛʹɼ‫ؼ‬ແԾઆ H0 : P = Qͷ΋ͱͰɼୀԽ V ౷‫ྔܭ‬ͷ݁Ռʹ‫ؼ‬ணͤ͞Δ͜ͱͰɼT!2 ͷ઴ۙ෼෍͕ɼಠཱͳࣗ༝౓̍ͷ χ2 ෼෍ͷॏΈ෇͖͖ͭແ‫ݶ‬࿨ͷ‫Ͱܗ‬ಘΒΕΔ͜ͱ ([2] ࢀর)ɼͦͷॏΈΛσʔλʹ‫͍ͯͮج‬ਪఆ͢Δํ๏ʹ͍ͭͯใࠂΛߦͬͨɽ·ͨɼରཱԾઆ H1 : P ̸= Q ͷ΋ͱͰͷ T!2 ͷ઴ۙ෼෍͕ฏ‫ ۉ‬0 ͷਖ਼‫ن‬෼෍ʹͳ͍ͬͯΔ͜ͱʹ͍ͭͯใࠂΛߦͬͨɽࢀߟจ‫ݙ‬[1] Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B. and Smola, A. (2007). A
kernel method for the two sample problem. Advances in Neural Information Procesing
Systems, 19 of MIT Press, Cambridge.
[2] Serfling, R. J. (1980). Approximation theorems of mathematical statistics. Wiley, NewYork.

Power Series Kernels ʹ‫ͮ͘ج‬ϊϯύϥϝτϦοΫֶशͷͨΊͷม਺બ୒๏
দҪ޹ଠ 1 , ‫۽‬୩࿱ 1 , ۚ৿‫ݚ‬ଠ 2 , ‫ݟۋ‬ຬ‫ ݦ‬3 , ۚ৿‫ܟ‬จ 4,11

ཧԽֶ‫৽ֵ ॴڀݚ‬஌ೳ౷߹‫ڀݚ‬ηϯλʔ, 2 ໊‫ݹ‬԰޻‫ۀ‬େֶ, 3 ໊‫ݹ‬԰େֶ, 4 ౦‫ۀ޻ژ‬େֶ1ಋೖ‫ػ‬ցֶशͷ༷ʑͳ໰୊ʹ͓͍ͯ, ม਺બ୒͸, ֶशͨ͠ϞσϧͷύϑΥʔϚϯεͷ޲্, ॏཁͳಛ௃ͷબ୒, ղऍੑͳͲͷ‫͔఺؍‬ΒඇৗʹॏཁͳλεΫͰ͋Δ [4]. ઢ‫ܗ‬ϞσϧΛ‫ؚ‬ΉύϥϝτϦοΫֶशͷ࿮૊ΈͰ͸, ଟ͘ͷม਺બ୒ͷͨΊͷํ๏͕ఏҊ͞Ε͍ͯΔҰํͰ, ϊϯύϥϝ
τϦοΫֶशʹ͓͚Δม਺બ୒๏ͷ‫ڀݚ‬͸, ͦͷॏཁੑʹൺֱͯ͠‫ݶ‬ఆతͰ͋Δ [1, 3]. ຊ‫ڀݚ‬Ͱ͸, Χʔωϧ๏ʹΑΔϊϯύϥϝτϦοΫֶश (ΧʔωϧϦοδճ‫ؼ‬, Χʔωϧີ౓, ີ౓ൺਪఆͳͲΛ‫ؚ‬Ή) ʹ͓͚Δม਺બ୒๏ΛఏҊ͢Δ. ۩ମతʹ͸, power series kernel ͱ͍͏ΫϥεͷΧʔωϧΛ༻͍ͯϞσϦϯά͠, non-negative garrote ‫ܕ‬ͷേଇʹΑͬͯม਺બ୒Λߦ͏. ཧ࿦తʹ͸, ఏҊ๏͸ΏΔ͍৚݅ͷԼͰม਺બ୒ͷҰகੑΛ࣋ͭ͜ͱ͕ࣔ͞ΕΔ. ͜ͷੑ࣭͸, ΦϦδφϧͷ (ઢ‫ܗ‬Ϟσϧʹର͢Δ) non-negative garrote ͷม਺બ୒ͷҰகੑͷ, Χʔωϧ๏ʹ‫ͮ͘ج‬ਪఆྔ (ඇઢ‫ܗ‬Ϟσϧ) ΁ͷ֦ுͱҐஔ͚ͮΒΕΔ. ͳ͓, ‫ݧ࣮ػࢉܭ‬ͷ݁Ռ͸౰೔ใࠂ
͢Δ.

2

໰୊ઃఆ

X Λ d ࣍‫ݩ‬αϯϓϧۭؒ, k : X × X → R ΛΧʔωϧؔ਺ͱ͢Δ. k ʹରԠ͢Δ࠶ੜ֩ώϧϕ!
ϧτۭؒΛ H ͱॻ͖, ͦͷ্ͷ಺ੵΛ ⟨f, g⟩, ϊϧϜΛ ∥f ∥ = ⟨f, f ⟩ ͱॻ͘ (f, g ∈ H).
ଟ͘ͷֶशΞϧΰϦζϜͰ͸, λʔήοτͱ͢Δؔ਺ͷਪఆ͸ਖ਼ଇԽ෇͖‫ݧܦ‬ଛࣦ࠷খԽ໰
୊ͱͯ͠ఆࣜԽͰ͖Δ :min L̂(f ) + λR(f )
f ∈H

(1)

ຊ‫Ͱڀݚ‬͸, ಛʹଛࣦͱͯ͠ 2 ࣍‫ ࣜܗ‬L̂(f ) = 12 ⟨f, Ĉf ⟩ − ⟨ĝ, f ⟩, 2 ৐ਖ਼ଇԽ߲ R(f ) = 12 ∥f ∥2 Λߟ
͑Δ. ΧʔωϧϦοδճ‫ؼ‬, Χʔωϧີ౓ൺਪఆ, Χʔωϧີ౓ਪఆ, density-ridge ਪఆͳͲͷϊϯύϥϝτϦοΫֶश͸͜ͷΫϥεʹଐ͢Δ [5]. Χʔωϧ๏ʹΑΔλʔήοτؔ਺ͷਪఆྔ͸ fˆ ͸௨ৗશͯͷม਺ x = (x1 , ..., xd ) ʹґଘ͢Δ͕, ͜͜Ͱ͸ਅͷλʔήοτؔ਺ f ∗ ͸ s < d‫ݸ‬ͷม਺ͷΈʹґଘ͍ͯ͠Δͱ͠, ͜ΕΒ f ∗ ʹ‫د‬༩͢Δม਺Λಛఆ͢Δ͜ͱΛ໨తͱ͢Δ.

3

Adaptive scaling ͱ power series kernel ʹΑΔม਺બ୒

3.1

Kernel ๏ʹ͓͚Δ Adaptive Scalingม਺બ୒Λ࣮‫͢ݱ‬ΔͨΊʹ, Breiman ͷ non-negative garrote (NNG) ʹΑΔ adaptive scalingΛ RKHS Ϟσϧʹద༻͢Δ [2]. f ∈ H ͱ, ξ ∈ Rd ʹରͯ͠, fξ (x) := f (ξ ◦ x) ͱఆΊΔ (◦ ͸੒෼ຖͷੵ). fξ ͷਪఆྔ fˆξ̂ Λಋग़͢ΔͨΊͷΞϦΰϦζϜΛ Algorithm 1 ʹࣔ͢.

Algorithm 1 Two-stage kernel-based estimator with NNG.
Input: Training samples, and regularization parameters, λ and η.
Step 1: Find the kernel-based estimator fˆ by solving (1).
Step 2: Let us define fˆξ (z) = fˆ(ξ ◦ z). Find the optimal garrote parameter ξ̂ by solving" f"ξ ) + η∥ξ∥1 ,min L(
ξs.t. ξ ∈ [0, 1]d .

Output: The estimator fˆξ̂ (x).

3.2Power Series Kernel ͱͦͷෆมੑ# = ∪ξ∈[0,1]d Hξ , Hξ = {fξ (x) | f ∈ H} ͳΔଟॏఏҊ๏ʹ͓͚Δ౷‫ܭ‬Ϟσϧ͸, Ұൠʹ͸ H#=HΧʔωϧϞσϧͱͳΔ. ΋͠, ೚ҙͷ ξ ʹରͯ͠ Hξ ͕ෆมੑ (Hξ ⊂ H) Λ࣋ͭͳΒ͹, H
͕੒ཱ͠, ଟॏΧʔωϧͷ‫ࢉܭ‬Λճආ͢Δ͜ͱ͕Ͱ͖Δ. Power series kernel$ w α xα y αk(x, y) :=, xα = xα1 1 · · · xαd d , α! = α1 ! · · · αd !
2
(α!)
d
α∈N0

͸্ड़ͷෆมੑΛ࣋ͭΧʔωϧͷΫϥεͰ͋Γ, ଟ߲ࣜΧʔωϧ΍ࢦ਺Χʔωϧ͸͜ͷΫϥεʹ‫·ؚ‬ΕΔ. ҰํͰ, Ψ΢εΧʔωϧ͸͜ͷΫϥεʹ͸‫·ؚ‬Εͣ, ҰൠʹෆมੑΛຬͨ͞ͳ͍.

4ม਺બ୒ͷҰகੑλʔήοτؔ਺ f ∗ ͸ s < d ‫ݸ‬ͷม਺ͷΈʹґଘ͢ΔͷͰ, ࠷దͳ NNG ύϥϝʔλ͸ ξ ∗ =(ξ1∗ , ξ0∗ ) = (1, 0) ∈ Rs × Rd−s ͱॻ͚Δ͜ͱʹ஫໨͢Δ.

Theorem 1 ([5], Assumption 1∼3, Theorem 1). ͍͔ͭ͘ͷԾఆͷԼͰ, ఏҊ๏ʹΑΔਪఆྔξ̂ ͸ҎԼͷੑ࣭Λ࣋ͭ.
1. ξ̂1 ͸ ξ1∗ ʹ֬཰ऩଋ͢Δ.
2. αϯϓϧαΠζ͕े෼େ͖͍ͱ͖, ξ̂0 = ξ0∗ ͕ߴ͍֬཰Ͱ੒Γཱͭ.

ࢀߟจ‫ݙ‬[1] Genevera I Allen. Automatic feature selection via weighted kernels and regularization.
Journal of Computational and Graphical Statistics, 22(2):284–299, 2013.
[2] Leo Breiman. Better subset regression using the nonnegative garrote. Technometrics,
37(4):373–384, 1995.
[3] Zaili Fang, Inyoung Kim, and Patrick Schaumont. Flexible variable selection for recovering
sparsity in nonadditive nonparametric models. Biometrics, 72(4):1155–1163, 2016.
[4] Isabelle Guyon and André Elisseeﬀ. An introduction to variable and feature selection.
Journal of machine learning research, 3(Mar):1157–1182, 2003.
[5] Kota Matsui, Wataru Kumagai, Kenta Kanamori, Mitsuaki Nishikimi, and Takafumi
Kanamori. Variable selection for nonparametric learning with power series kernels. Neuralcomputation, 31(8):1718–1750, 2019.

Component Retention in PCA Applied to Microarray
Datasets
Atina Husnaqilati1 , Yohji Akama2
1 The Mathematical Institute, Tohoku University, Japan, husqila@gmail.com

2 The Mathematical Institute, Tohoku University, Japan, yoji.akama.e8@tohoku.ac.jp

Principal component analysis (PCA) is a multivariate statistical technique introduced by Karl Pearson [5]. Many fields, such as ecology, biology, economics,
psychology, and zoology, employ PCA.
Suppose we have a p ⇥ n data matrix X = [x1 , . . . , xn ] where x j = [x1 j , . . . , x p j ]T ,j = 1, . . . , n, are independent and identically distributed as a p-dimensional distribution with mean zero and positive definite covariance matrix. The sample covariance matrix is S = n 1 XX T . The eigenvalues of sample covariance matrix arel1 l2 · · · l p 0.
PCA finds new components to illustrate a great part of the variance in the data
by using the sample covariance matrix S of that data. The new components arecalled principal components (PC). A principal component is a linear combinationof the original variables. It corresponds to an eigenvector u of S. Then the varianceof the PC is the eigenvalue l corresponding to u. The greater l is, the more“significant” the PC is. When reducing the dimension of data from p to q, we
can choose q principal components corresponding to the q largest eigenvalues of S.
PCA has been useful to various data with p < n.
Recently PCA is employed to the analysis of microarray datasets [1]. The
microarray dataset contains the relative activity of thousand of genes from a single
sample. Size n of observations in microarray datasets is less than the number pof variables. The microarray datasets have large number of variable because thesingle gene has many components to measure.
We consider the n ⇥ n dual sample covariance matrix SD = n 1 X T X with µ1µ2 · · · µn 0 being the eigenvalues. Note(µi (1  i  min(p, n))li =(1)0 (min(p, n) < i  p).
The representation of large dimension p of microarray datasets is difficult, so
we reduce the dimension p with PCA to q by taking q principal components.
The stopping rules are methods to determine the number q of important principal components. We concern two types of stopping rules, the first based on empirical results and the second based on statistical distributions. Guttman-Kaiser
1criterion [7] and Jolliffe’s rules [4] are the first types, while a broken stick model[1, 2] of the second type.
The question of stopping rules is to balance the accuracy (or fit) of the modelwith ease of analysis and the potential loss of information. In this paper, we apply
the three methods to 16 publicly available microarray datasets [6] and summarize
the results. Then, we have
(Guttman-Kaiser) > (Broken stick model) > (Jolliffe’s rule).

(2)

Our results contrast with result for p < n datasets. For simulated datasets withp < n, Jackson [3] gave
(Guttman-Kaiser) > (Broken stick model),while Cangelosi and Goriely [1] did

(3)

(

)
0.7 p
(Broken stick model) < another Jolliffe’s rule min i li >Â li .
p i=1

In view of the inequality (2) and the inequality (3), broken stick model may deserve
further study for general setting.

Acknowledgment
The first author gratefully acknowledge the scholarship for her master course
study from the MEXT (Ministry of Education, Culture, Sports, Science and Technology) Japan.

References[1] Cangelosi, R. & Goriely, A. (2007). Component Retention in Principal Component
Analysis with Application to cDNA Microarray Data. Biology Direct. 2:2.
[2] Frontier, S. (1976). Étude de la décroissance des valeurs propres dans une analyse encomposantes principales: comparaison avec le modèle du bâton brisé. Biol Ecol. 25.
67–75.
[3] Jackson, D. A. (1993). Stopping rules in principal components analysis: a comparison of heuristical and statistical approaches. Ecology. 74:8. 2204–2214.
[4] Jolliffe, I. (2002). Principal Component Analysis. New York: Springer.
[5] Pearson, K. (1901). On lines and planes of closest fit to systems of points in space.
Phil Mag. 2. 559–572.
[6] Ramey, J. (2013). Datamicroarray. R package version 1.14.4.
[7] Yeomans, K. A. & Golder, P. A. (1982). The Guttman-Kaiser criterion as a predictorof the number of common factor. Journal of the Royal Statistical Society. 3D 31.
221–229.

2௒ཱํମʹ಺઀͢Δ௒ପԁ‫ʹٿ‬ΑΔઢ‫ܗ‬ճ‫ؼ‬ͷղऍԼ໺ण೭ (‫ࣜג‬ձࣾσδλϧΨϨʔδ)ং࿦1p ‫ݸ‬ͷ Xi (i = 1, 2, .., p) Λಠཱม਺ɺY Λैଐม਺ͱ͢Δɻઢ‫ܗ‬ճ‫ؼ‬Ϟσϧ
Ŷ =

p
!

âi Xi + b̂

i=1͸޿͘༻͍ΒΕΔ͕ɺp ≥ 2 ͱͳ్ͬͨ୺ʹɺॏճ‫ؼ‬Λ͢Δͱɺճ‫ ਺܎ؼ‬âi ͷ஋ͷਖ਼ෛͱେখ͕
௚‫ʹײ‬൓ͨ͠Γɺͦͷ஋ͷҙຯͷղऍ͕೉͘͠ͳͬͨΓɺଟॏ‫ڞ‬ઢੑ͕ൃੜͨ͠Γ͢ΔͳͲͷࠔ೉͕஌ΒΕ͍ͯΔɻi = 1, .., p ʹରͯ͠ ρi Λ Xi ͱ Y ͷϐΞιϯͷੵ཰૬ؔ܎਺ͱ͢Δͱɺॏ૬ؔ
܎਺͸Լ‫ ݶ‬max{|ρ1 |, |ρ2 |, .., |ρp |} ͱ্‫ ݶ‬1 ͷؒʹ஋ΛऔΔ͕ɺͲͷΑ͏ͳ৔߹ʹͦͷԼ‫ͨ·ݶ‬͸্‫ʹݶ‬Ұகͨ͠Γ͔ۙͬͨΓ͢Δ͔Λɺ‫ʹػࢉܭ‬ΑΔࢉग़ແ͠ʹ௚‫ײ‬తʹ൑அ͢Δͷ͸೉͍͠৔߹͸ଟ͍ɻ͜ΕΒͷ໰୊͸ɺ‫ػ‬ցֶशͰઢ‫ܗ‬ϞσϦϯάΛ‫ؚ‬Μͩख๏Λ࣮ߦͨ͠৔߹ʹ΋ಉ༷ʹ‫ݱ‬ΕΔ͕ɺԼ‫ࣔ͢ʹه‬Α͏ͳ‫ز‬Կֶతͳ࡞ਤΛ༻͍ͨ 3 ‫ݸ‬ͷ৽͍͠ௗᛌతͳఆཧʹΑΔ৽͍͠‫ʹ఺؍‬ΑΓɺղܾͷՄೳੑ͕͋Δͱߟ͑ΒΕΔɻϢʔΫϦου‫ز‬Կֶతͳൃ૝Λ༻͍ͯɺ࣍ϖʔδʹࣔࠦ͞ΕΔ
Α͏ʹ༷ʑͳ༗༻ͳ໋୊Λಋ͘͜ͱ͕‫ظ‬଴Ͱ͖Δ͔ΒͰ͋Δɻ৽‫߸ه‬ͷఆٛ2(1) X!
i ͱ͸ɺ(X1 , .., Xi−1 , Xi+1 , .., Xp ) ͢ͳΘͪ X ͷ࣋ͭ p ‫ݸ‬ͷม਺ͷ಺ɺXi Ҏ֎ͷ p − 1 ‫ݸ‬ͷม਺ΛूΊͨ΋ͷͱ͢Δɻ(2) RA⊢B ͱ͸ɺม਺ͷू·Γ A Ͱม਺ B Λॏճ‫ͨ͠ؼ‬৔߹ͷॏ૬ؔ܎
਺ͱ͢Δɻ(3) A = (Ai )Ii=1 , B = (Bj )Jj=1 ͕ͦΕͧΕม਺ͷฒͼͷ৔߹ (I = 1 ·ͨ͸ J = 1 ͷ৔߹΋͋Γ͏Δ)ɺRA×B ͱ͸ɺI ߦ J ྻͷߦྻͰɺୈ (i, j) ཁૉ͸ม਺ Ai ͱ Bj ͷϐΞιϯͷੵ཰૬ؔ܎਺ͱ͢Δ (௨ৗɺA = B ͷ৔߹ʹʮ૬ؔߦྻʯͱ‫ݺ‬͹ΕΔ)ɻ

‫ط‬஌ͷ݁Ռ

3−1
શͯͷ Xi ͱ Y Λඪ४Խ (ฏ‫ ͕ۉ‬0 Ͱ෼ࢄ͕ 1) ͨ͠ͱ͢ΔɻRX×XͷଘࡏΛԾఆ͢Δɻ͢Δͱɺ(1)−1Xi ʹରԠͨ͠ภճ‫ ਺܎ؼ‬âi ͸ p ࣍‫ݩ‬ϕΫτϧ RX×X RX×Y ͷ i ൪໨ͷ੒෼ʹ౳͍͠ [1, 68 ϖʔδͱ
−178 ϖʔδ]ɻ(2) ॏ૬ؔ܎਺ RX ⊢Y ͸ (RY×X RX×X
RX×Y )1/2 ʹ౳͍͠ [1, 73 ϖʔδ]ɻ(3) X!
i ͷӨ−1‫ڹ‬Λআ͍ͨ Xi ͱ Y ͷؒͷภ૬ؔ܎਺͸ɺp ̸= 1 ͷ৔߹ʹ (RXi ×Y − RXi×X!i RX!×X! RX!i ×Y )/{(1 −ii1/2 [1, 77 ϖʔδ] ʹ౳͍͠ɻ(C. R. Rao [2] ΍ T. W. Anderson [3] ͷຊΛ‫ؚ‬Ίଟ
2
2RX! ⊢X )(1 − RX! ⊢Y )}iii਺ͷจ‫͜Ͱݙ‬ΕΒͷࣜΛௐ΂͕ͨɺภ૬ؔ܎਺ͷࣜʹ͍ͭͯ͸্‫ه‬ͷࣜʹ༰қʹม‫͖Ͱܗ‬Δ΋ͷ͸ [1] ͷଞʹ͸‫͔ͭݟ‬Βͳ͔ͬͨɻ)

4

ఆཧͷߏ੒

্‫͔ه‬ΒɺҎԼʹड़΂ΔϢʔΫϦου‫ز‬ԿֶతͳఆཧΛಋ͘͜ͱ͕ग़དྷΔ [4]ɻิ୊: M Λ p × p ͷਖ਼ఆ஋ରশߦྻͰର֯੒෼͸શͯ 1 ͱ͢Δɻۭؒ Rp ʹ௚ަ࠲ඪ‫ܥ‬Λಋೖ͠ x1 ࣠, x2 ࣠, .., xp ͕࣠͋Δͱ͢Δɻͦͯ͠ɺx⊤ M −1 x = 1 Λຬͨ͢ x ͷू߹Λߟ͑ΔɻͦΕ͸ɺxi = ±1 (i = 1, .., p) Ͱද͞ΕΔ 2p ຕͷ௒ฏ໘Ͱғ·Εͨ௒ཱํମ S ʹ಺ଆ͔Β઀͢Δ௒ପԁ‫ٿ‬໘ E Ͱ͋ΔɻM Λ p ࣍‫ݩ‬ͷॎϕΫτϧ p ຊʹ෼ղͯ͠(R1 | . . . |Rp ) ͱ͢ΔɻS ͱ E ͷ઀఺ͷू߹ S∩E ͸ 2p ‫ݸ‬ͷ఺ͷू߹ {±R1 , ±R2 , .., ±Rp }ͱ౳͍͠ɻ͜ͷิ୊ͷ M ʹ RX×X Λ୅ೖ͠ɺ·ͣɺ௒ཱํମ S ͱ௒ପԁ‫ٿ‬໘ E ͱͦΕΒͷ઀఺ +R1 , .., +Rp ,−R1 , .., −Rp ΛಘΔɻͦͯ͠৽ͨͳ఺ P ͷ࠲ඪΛ RX×Y (= (ρ1 , .., ρp )) ͱ͢Δɻ
ఆཧ 1 (ॏ૬ؔ܎਺): ‫ ఺ݪ‬O ͱ఺ P Λ௨Δ௚ઢͱ E (௒ପԁ‫ٿ‬໘) ͱͷަ఺Λ P ′ ͱ͢Δͱɺॏ૬ؔ܎਺ RX ⊢Y ͸௕͞ͷൺ |OP |/|OP ′ | ʹ౳͘͠ͳΔɻ

ఆཧ 2 (ภճ‫)਺܎ؼ‬: ֤ i = 1, .., p ʹରͯ͠ɺઢ‫ ਺ؔܗ‬fi : Rp → R Λɺ{O} ∪ (S ∩E)\{±Ri } ͷ೚ҙͷ఺Ͱ͸஋͕ 0 Ͱɺ఺ Ri Ͱ͸஋͕ 1 Λ༩͑ΔΑ͏ʹ͢Δɻ͢Δͱ
fi (P ) ͸ Xi ͱ Y Λඪ४Խ্ͨ͠Ͱͷภճ‫ ਺܎ؼ‬âi ʹ౳͍͠ɻఆཧ 3 (ภ૬ؔ܎਺): ֤ i = 1, .., p ʹରͯ͠ɺ Pi− , Pi+ ∈ S ͸ɺઢ෼ Pi− Pi+ ͕ xi ࣠ͱฏߦ͔ͭಉ͡޲͖Ͱ P Λ௨Δͱ͢ΔɻΞϑΟϯؔ਺ gi : R → Rp ͕ gi (±1) = Pi±(෮߸ಉॱ) Λຬͨ͢Α͏ʹ͢Δɻม਺ X1 , .., Xi−1 , Xi+1 , .., Xp ͷӨ‫ڹ‬Λআ͍ͨ Xi ͱ
Y ͷؒͷภ૬ؔ܎਺͸ gi−1 (P ) ʹ౳͍͠ɻ্‫ه‬ͷ͜ͱ͸ɺ࣍‫ ݩ‬p ͕ 2 ·ͨ͸ 3 ͷ৔߹͸ɺԼʹ͋Δ༷ͳਤͰߟ͑Δ͜ͱ͕ग़དྷΔɻਖ਼ํ‫ܗ‬ͱཱํମ͕ S ʹ૬౰͠ɺପԁͱପԁ‫ ͕ٿ‬E ʹ૬౰͢ΔɻS ͱ E ͸ 2p ‫ݸ‬ͷ఺ ±Ri (i = 1, .., p) Ͱ઀͍ͯ͠ΔɻE ͷ಺෦ʹ఺ P ͕ଧ఺͞Ε͍ͯΔ (R(X,Y )×(X,Y ) ͸൒ਖ਼ఆ஋Ͱ͋Δ͜ͱʹΑΔ)ɻP ͕‫ ఺ݪ‬O ʹ͍͔ۙ E ʹ͍͔ۙͰॏ૬ؔ܎਺͕ܾ·ͬͨΓɺؔ਺ fi ʹ 0 ΍ ±1 ͷ஋Λ༩͑ͤ͞Δ௒ฏ໘ͷߟ࡯͔Βඪ४Խճ‫ ͕਺܎ؼ‬±1 ͷൣғΛͲΜͳ৔߹ʹͲͷఔ౓཭ΕΔ͔Λ‫ز‬Կతʹಋ͍ͨΓɺઢ෼ Pi− Pi+ Λ෺ࠩ͠ (ఆ‫ ͠ͳݟͱ )ن‬−1 ͔Β +1 ·Ͱͷ໨੝ΓΛೖΕΔͱภ૬ؔ܎਺ΛಡΜͩΓ͢Δ͜ͱ͕ग़དྷΔɻࢀߟจ‫ݙ‬[1] ஛಺‫ܒ‬, ༄Ҫ੖෉ (1972). ଟมྔղੳͷ‫ૅج‬, ౦༸‫৽ࡁܦ‬ใࣾ.
[2] Calyampudi Radhakrishna Rao (1973). Linear Statistical Inference and Its Applications,Wiley Series in Probability and Statistics.
[3] Theodore Wilbur Anderson (2003). An Introduction to Multivariate Statistical Analysis,
Wiley Series in Probability and Statistics.
[4] Toshiyuki Shimono (2019). Interpreting Multiple Regression via an Ellipse Inscribed in a
Square Extensible to Any Finite Dimensionality, In Proceedings of Data Science, Statistics& Visualisation 2019 (DSSV 2019) in Kyoto, Japan, page 119.

マスター方程式から厳密に得られる期待値変数の情報幾何学, 接触幾何学およびその周辺
後藤 振一郎, 日野 英逸
情報 · システム研究機構

統計数理研究所

概 要

本報告では, 時間連続マスター方程式から厳密に得られる期待値変数に対する力学系を導入し, その力学系の微分幾何学を用いた記述を行う. 特にその微分幾何学として平衡系に対しては情報幾何学, 非平衡系に対しては接触幾何学を用い, かつ期待値変数に対する力学系は接触幾何学における接触ハミルトン力学系を用いる.

導入
情報幾何学は数理統計学の微分幾何学化として知られており, その微分幾何学的側面や応用の探察や拡張が行われている. その例は様々である. 本報告では特に接触幾何学と呼ばれる奇数次元版シンプレクティッ
ク幾何学と情報幾何学を有機的に統合する研究に着目する. この文脈において, 疑リーマン計量等を導入した場合, パラ接触計量多様体の一つであるパラ佐々木多様体が熱力学相空間を記述するのに適していることが判明している. これらを鑑みると, パラ接触計量多様体がどのように非平衡熱統計力学を記述するかが興味の対象になる. 特にマスター方程式は数学的に非自明でありながら単純で, 非平衡熱力学で頻繁に用いられているので, これに着目する. またマスター方程式はモンテカルロ法の基礎ともなるため, 数理工学への応用も期待できる.
本研究では連続時間マスター方程式から期待値変数を記述する力学系を導出する. そしてその非平衡熱力学過程をパラ接触計量多様体上で構成する. 本稿の大部分は文献 [1, 2] をもとにしている. 本稿で用いる用語の定義はそれらの文献や予稿に記述があるので必要に応じて参照されたい.

可解マスター方程式
この節ではマルコフ核を選ぶことにより, あるクラスのマスター方程式を導入する. そして, その可解性を示す. 集合 Γ を離散状態を要素にもつ有限集合, t ∈ R を時間, そして p(j, t) dt を時刻 t と t + dt の間に!
π θ (j)
状態 j ∈ Γ を見つける確率とする. 第一目標は, 与えられた分布関数 p eqj∈Γ πθ (j),
θ (j) = Z(θ) , Z(θ) :=を実現することである. ただし, Θ はパラメーター θ = {θ 1 , . . . , θ n } を要素にもつ集合で Z : Θ → R はい!
eq
わゆる分配関数で p eqj∈Γ p θ (j) = 1.
θ が規格化するために用いられる:

以下ではあるクラスのマスター方程式に着目する. 時間依存する分布関数を p : Γ × R → R≥0 とする. そして, マスター方程式とよばれる次を考える"∂
p(j, t) =[ w(j|j ′ ) p(j ′ , t) − w(j ′ |j) p(j, t) ] ,
∂t
′

(1)

j (̸=j)

ここで w : Γ × Γ → I, (I := [ 0, 1 ] ⊂ R) は w(j|j ′ ) が状態が j ′ から j へジャンプする確率を表す. 式 (1)eqと仮定 w θ (j|j ′ ) = p eq
θ (j), および, p θ (j) ̸= 0, ∀j ∈ Γ, により, 可解マスター方程式∂
p(j, t) = p eq
θ (j) − p(j, t).
∂t(2)を導出することができる. 解 p(j, t) の陽な表式は (2) を解くことによって得られる. そして解 p は θ に依存することに気がつく. これを考慮し, p(j, t) は p(j, t; θ) と書くことにする. また,(2) により平衡状態が時間に関して漸近極限で実現されていることが確認できる.

観測量の時間発展とその幾何学
本節では観測量の時間発展を記述する微分方程式をある仮定のもと可解マスター方程式から導出する. そ

して, それらの観測量の漸近極限について述べる. ここで本稿における 観測量とは状態 (や確率変数) に依らない関数として定義しておく. それゆえ, 分布関数に関する期待値変数は観測量である.

O a : Γ → R (a ∈ {1, . . . , n}) を関数, そして p : Γ × R → R≥0 を可解マスター方程式 (2) に従う分布
!
!
eq
eq
j∈Γ O a (j) p(j, t; θ), および ⟨ O a ⟩ θ :=j∈Γ O a (j) p θ (j), は O a の期待値と呼ばれる.
関数とする. すると ⟨ O a ⟩ θ (t) :=もし平衡分布関数が指数分布族に属していれば, 以下で指定される関数 Ψ eq : Θ → R と Ψ : Θ × R → R
⎛
⎞
⎛
⎞
" b
"
"
1
p(j, t; θ) ⎠ eq
Ψ eq (θ) := ln ⎝e θ O b (j) ⎠ ,Ψ(θ, t) := ⎝ 0
Ψ (θ), where J 0 :=1. (3)eqJpθ (j)
′
j∈Γ

j∈Γ

j ∈Γ

は様々な役割を果たす. これ以降では (3) が存在することを仮定する. 情報幾何学の文脈ではこの関数は θポテンシャルとして引用される. 本稿では離散分布関数が考察の対象であり, 従って分布関数は指数分布族に属する. 従って,(3) における Ψ eq は本稿でも重要な役割を果たす. 値 Ψ eq (θ) は負の無次元自由エネル
ギーである. 期待値と {⟨ O a ⟩ θ } と Ψ に対する微分方程式は以下のように導出される.

命題 1. ([1]). θ を時間依存しないパラメーターの組でこれにより分布 p eq
θ をパラメタライズする. すると, {⟨ O a ⟩ θ } および Ψ は R 2n+1 上の以下の微分方程式の解となる:d ad∂ Ψ eqdθ = 0,⟨Oa ⟩θ = − ⟨Oa ⟩θ +, and
Ψ = − Ψ + Ψ eq ,
dt
dt
∂θ a
dt
この力学系をモーメント力学系と名付ける. モーメント力学系は接触ハミルトン力学系である :命題 2. ([1]). 命題 1 での力学系は接触幾何学で知られる接触ハミルトン力学系として記述される.
そしてこの命題をパラ接触計量多様体の上で考察すると, 以下が示される :定理 1. ([2]). 命題 2 における接触ハミルトンベクトル場を X h , その接触ハミルトニアンを h とする. またパラ接触計量多様体における (1, 1)-型テンソル場を φ とすると, φ(X h ) や φ2 (X h ) に沿って h は保存する L φ(X h ) h = L φ 2 (X h ) h = 0.

非平衡統計力学では状態がどれほど平衡状態に近いか, しばしば着目される. 一般にそのような距離を幾

何学を用いて定義するには曲線の長さを使うことができる. リーマン幾何学において, ベクトル場の積分曲線で結ばれた多様体上の 2 点間の距離を計算する手法が確立されている. 以下の本稿での主張が得られる.
定理 2. (期待値変数の幾何学的記述とその収束, [2]). 可解マスター方程式から導出されたモーメント力学
系はパラ接触計量多様体の上で記述され, Mrugala 計量テンソル場と呼ばれる計量に付随した収束は指数型である.
謝辞
本研究の実施にあたり, 著者 S.G. は日本学術振興会から JSPS 科研費 19K03635 の部分的助成を受けました. また, 著者 H.H. は同じく日本学術振興会から JSPS 科研費 17H01793 の部分的助成を得ました. これらに加え, 両著者は JST CREST JPMJCR1761 の部分的助成を受けました.
参考文献[1] S. Goto and H. Hino, Information and contact geometric description of expecation variables exactly
derived from master equations, arXiv:1805.10592v2, Submitted.
[2] S. Goto and H. Hino, Expectationo variables on a para-contact metric manifold exactly derived frommaster equations, GSI 19 proceedings, Lecture Notes in Computer Science, to appear, (2019).

Similarity Measures and Statistical Models in
Recommendation Problems
Kotaro Sudo (NS Solutions Co.), Naoya Osugi (Recruit Technologies Co.,Ltd.),
and Takafumi Kanamori (Tokyo Institute of Technology)

In this paper, we study recommendation problems, in particular, the reciprocal recommendation. The reciprocal recommendation is regraded as a kind of edge prediction problem ofrandom graphs. For example, the job recruiting service provides preferable matches between
companies and job seekers. The corresponding graph is a bipartite graph, and nodes are categorized into two groups; one is job seekers and the other is companies. Directed edges fromone group to the other one mean the expression of user’s interests. The job recruiting service
recommends unobserved potential matches between users and companies. Another common
example is online dating services. Again, the corresponding graph is expressed as a bipartite graph with two groups, i.e., males and females. The directed edges mean the preference
expressions among users. Then, the recommendation system provides potentially preferable
partners to each user. The quality of such services totally depends on the prediction accuracyof unobserved or newly added edges. The edge prediction has been widely studied as a classof important problems in social networks [15, 10, 8, 11, 1].
In recommendation problems, it is often assumed that the similar people like or dislike
similar items, people, etc.
Based on this assumption, researchers have proposed many
similarity measures. The similarity is basically defined through the topological structure of thegraph that represents the relationship among users or items. Neighbor-based metrics, pathbased metrics, and random walk based metrics are commonly used. Then, a similarity matrix
defined from the similarity measure is used for the recommendation. As the other approach,statistical models such as stochastic block models [13] are used in order to estimate network
structures such as clusters or edge distributions. The learning methods using statistical models
often achieve high prediction accuracy in comparison to similarity-based methods. Details arereported in [12] and references therein.
The main purpose of this paper is to investigate the relationship between similarity-based
methods and statistical models. We show that a class of widely applied similarity-based methods can be derived from the Bernoulli mixture models or from the stochastic block models ingeneral. More precisely, the Bernoulli mixture model with the Expectation-Maximization(EM) algorithm [5] naturally derives a completely positive matrix [2] as the similarity matrix. The class of completely positive matrices is a subset of doubly nonnegative matrices,
i.e., positive semidefinite and element-wise nonnegative matrices [3]. Also, we provide aninterpretation of completely positive matrices as a statistical model satisfying exchangiability [6, 16, 7, 4]. Based on the above argument, we connect the similarity measures using
completely positive matrices to statistical models. First, we prove that most of commonly1used similarity measures yield completely positive matrices as the similarity matrix. Then, we
propose an algorithm that transforms the similarity matrix to the Bernoulli mixture model. As
a result, we obtain a statistical interpretation of similarity-based methods through Bernoulli
mixture models. We conduct numerical experiments using synthetic data and real-world data
provided from an online dating site, and report the eﬃciency of the recommendation method
based on Bernoulli mixture models.
This work is based on [9, 14].

References[1] Deepak K. Agarwal and Bee-Chung Chen. Statistical Methods for Recommender Systems. Cambridge University Press, 2016.
[2] A. Berman and N. Shaked-Monderer. Completely Positive Matrices. World Scientific Publishing
Company Pte Limited, 2003.
[3] Samuel Burer, Kurt M. Anstreicher, and Mirjam Dür. The diﬀerence between 5 × 5 doubly
nonnegative and completely positive matrices. Linear Algebra and its Applications, 431(9):1539–
1552, 2009.
[4] Bruno de Finetti. Theory of Probability. Wiley, 1970.
[5] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via
the em algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1–38, 1977.
[6] P. Diaconis. Finite forms of de finetti’s theorem on exchangeability. Synthese: An International
Journal for Epistemology, Methodology and Philosophy of Science, 36:271–281, 1977.
[7] P. Diaconis and D. Freedman. Finite exchangeable sequences. The Annals of Probability, 8(4):745–
764, 1980.
[8] Mohammad Al Hasan and Mohammed J. Zaki. A survey of link prediction in social networks. In
Social Network Data Analytics, pages 243–275. 2011.
[9] Takafumi Kanamori and Naoya Osugi. Model description of similarity-based recommendation
systems. Entropy, 21(7), 2019. 702.
[10] David Liben-nowell and Jon Kleinberg. The link-prediction problem for social networks. Journalof the American Society for Information Science and Technology, 2007.
[11] Linyuan Lü and Tao Zhou.
390(6):1150–1170, 2011.

Link prediction in complex networks: A survey.

Physica A,[12] Wang Mengdi. Vanishing price of decentralization in large coordinative nonconvex optimization.
SIAM Journal on Optimization, 27(3):1977–2009, 2017.
[13] Natalie Stanley, Thomas Bonacci, Roland Kwitt, Marc Niethammer, and Peter J. Mucha. Stochastic block models with multiple continuous attributes, 2018. arXiv:1803.02726.
[14] Kotaro Sudo, Naoya Osugi, and Takafumi Kanamori. Numerical study of reciprocal recommendation with domain matching. Japanese Journal of Statistics and Data Science, 2(1):221–240,
2019.
[15] Peng Wang, BaoWen Xu, YuRong Wu, and XiaoYu Zhou. Link prediction in social networks: thestate-of-the-art. Science China Information Sciences, 58(1):1–38, 2015.
[16] G. R. Wood. Binomial mixtures and finite exchangeability. The Annals of Probability, 20(3):1167–
1173, 1992.

2

高次元遺伝子解析の呪いからの解放
成蹊大学名誉教授

新村秀一「高次元 Microarray データを用いて癌遺伝子の特定と癌の亜種を見つける研究」が 1970 年頃から行われてきた(Golub, 1999)。これらの研究で用いられたデータが公開されているので、統計に限らず機械学習（AI）、パター
ン認識、Bio 工学の新テーマとして研究されてきたが、いずれの研究も成功していない(判別分析の Problem5)。
しかし、仮に症例数が n=100 で遺伝子数が p=10,000 の発現量データとすれば、2 群判別が最も適した手法である。筆者は 2015 年 10 月 28 日から 12 月 20 日の僅か 54 日間で、簡単にこの問題を解決した。用いたデータは、1999 年から 2004 年の間に米国の 6 医学研究プロジェクトが論文を発表し、研究に用いた公開データである。これらは癌と健常、あるいは 4 種の異なった癌の 2 クラスである。
結果は非常に単純である。6 種のデータは線形分離可能なデータ(Linearly Separable Data, LSD)である（判別分
析の Fact3）。この重要な事実であり信号が、これまでの研究で誰も指摘していない。さらに、筆者が開発したMatryoshka Feature Selection Method (Method2)で簡単に線形分離可能な含まれる遺伝子数が n 個以下の遺伝子のｋ組の部分空間(SMall Matryoshka, SM)と最小誤分類数(Minimum Number of MisclassificationSMNM)が 1 以上の遺伝子の雑音部分空間に分割できた(Fact4)。各 SM は統計分析が容易な小標本であるが、ロジスティック回帰以外の統計手法（一元配置の分散分析、ｔ検定、相関分析、クラスター分析、PCA）で線形分離可能な事実が示されなかった(Problem6)。そこで、MNM 基準による改定 IP-OLDF（RIP）の判別スコア(RIP Discriminant Score, RipDS)を変数とし、n 症例*k 次元の信号データ(k<=n)を作成した。これを上記の統計手法で分析し「癌の遺伝子診断の統計分析法を世界で初めて提案」できた。今年 5 月に Springer から Springer2 を出版した。
以上の研究が簡単にできたのは、大学卒業以来行ってきた判別分析の新理論(Springer1）が 2015 年に完成し、新理論がその応用問題として 1970 年頃から未解決の Microarray を用いた癌の遺伝子解析（Problem5）を簡単に解決できた。本来であれば癌の遺伝子研究の専門家でない筆者が「癌の遺伝子診断」までを行うことは適していない。しかし、癌は遺伝子の病気であり、高次元の Microarray 空間で 2 群が完全に分かれていて、さらに MNM＝０である k 組の SM に分割できる。そして RipDS で信号データを作ることで、上記の統計手法で線形分離可能であり有効と考えられる Malignancy Indexes が数多く発見できた。しかし、これ等のどの Malignancy Indexes が医学的に役に立つか否かは医学専門家の検証が必要である。
残念ながら Golub らの研究後に、「NIH が乳がん以外の癌に関して Microarray による研究は成果が出ないと判断し、医学研究が終わったようである」。このため、いかに医学専門家の検証につなげるかを 2016 年から模索している。しかし統計や工学研究者は、NIH の報告を知らずに研究を続けているのは一般的に問題であろう。また、データが LSD であるのに、そのデータを学習標本に用いた AI 研究が LSD の事実を指摘しない点だけが、まだ説明できていない。
大学卒業以来の研究テーマである判別分析の新理論を確立し、その応用として「高次元 Microarray の癌の遺伝
子解析と診断」にはじめて成功した。そこでこれまでの研究を見直した結果、LSD である高次元データは、ケー
ス数 n 個以下の遺伝子のｋ組の小標本に必ず分割できるという事実が統計にとって一番重要と考えた。
すなわち、
我々は「高次元データの呪いから数理計画法(MP)の LP と IP で定式化した LDF で解放される（2 次計画法 QPで定式化した SVM ではできない）。そして、分割された SM を統計分析するとこれまで見えてこなかった新しい癌の遺伝子診断の世界が広がる」。
以上の重要なテーマを以下の 4 回のシンポジュームで報告したい。
1) 九州大学：「高次元遺伝子解析の呪いからの解放 1 -統計が 1970 年からこの問題を解決できなかった理由-」
12) 新潟大学：「高次元遺伝子解析の呪いからの解放 2 -癌の遺伝子診断-」3) 東京工業大学：「高次元遺伝子解析の呪いからの解放 3 -機械学習などの工学研究の問題点-」
4) 秋田大学：「高次元遺伝子解析の呪いからの解放 4 -高次元データの分割法の最新結果-」
予稿集は、以下の 6 章からなり、1 章と 2 章は共通の基礎知識、3 章から 6 章は 4 大学での発表に対応していて、各大学の予稿はその章しか含んでいないで、必要であれば他大学の予稿を参考にしてほしい。
１章では、Springer1 と「新村(2010). 最適線形判別関数．日科議連」の中から、統計的判別関数がなぜ癌の遺伝子解析に役に立たなかったかの理由を報告する。すなわち LSD 判別は、MNM 基準による改定 IP‐OLDF(RIP)とハードマージン最大化 SVM（H-SVM）でしか理論的に正しくできないことが原因である。回帰係数や判別係
数を０にすることで、Problem5 に対応できると考える LASSO 研究の間違いを指摘する
２章では、1970 年頃から解決できなかった Problem5 の結果を紹介する。
３章では、高次元の Microarray がなぜ n 個以下の MNM＝０であるｋ組の SM に簡単に分割できるかを数理計画法(MP)の基礎知識（新村(2010).

数理計画法による問題解決法．日科議連」）と連立方程式の解の基礎知識の簡単な組み合わせで説明する。そして、統計的判別関数と 2 次計画法 QP で定式化された H

SVM が高次元のLSD である Microarray をｋ組の SM に分割できない理由を説明する。
4 章では、本研究における 8 種類の LDF の役割を概観する。Microarray が LSD である Fact3 は、RIP、H-SVM、Revised LP-OLDF と SVM4(C=104)で発見できる。そして RIP と Revised LP-OLDF が高次元の呪いから研究者を解放し、SVM ができない理由を示す。高次元 Microarray はｋ組の n 個以下の遺伝子の部分空間の SM に分割できる。これらは小標本であり統計手法で簡単に分析し癌の遺伝子診断が行えると考えた。しかし、ロジスティック
回帰だけが全ての SM がＮＭ＝０で、LSD であることが分かる。しかし他の統計手法で LSD の事実が得られなかった（Problem6）。試行錯誤の末、信号データを作成してこれを解決し、癌の遺伝子診断が可能になった。しかし LSD である Microarray データを学習に用いているのに、なぜ AI 研究は LSD の事実を発見できないかを参加者と議論したい。6 月開催の IEEE の機械学習の国際会議で良い情報が得られればそれも報告する。
5 章では、世界で初めて成功した癌の遺伝子診断の結果の概略を Springer２から説明する。
6 章では、Method２が Microarray データだけでなく、6 変数の普通車と小型車の 2 群判別にも適用できることを示す。即ち本研究は、LSD は必ずより小さい SM や最小次元の Basic Gene Sets(BGS)に分割できることが今後の統計にとって重要なことを示す。そして Method2 が求めた SM をさらに BGS（iPS 研究の山中 4 因子と同じ概念）に分割すると、多くの場合に 2 個の BGS が含まれることが分かった。
筆者の方法によって、今後高次元の他の LSD であっても、容易に統計分析の研究対象になる。本研究は、質が高く、2 群が LSD であるという検証しやすいデータを用いたことで、LINGO[2]と JMP[1]の組み合わせで初めて役に立つ研究を退官後に完成できたことは医学データを研究対象としたことが幸運であったと考える。
1

新村秀一 (2004).『JMP活用

2

新村秀一 (2010). 『最適線形判別関数』. 日科技連出版.

3

新村秀一 (2011). 『数理計画法による問題解決法』. 日科技連出版.

4

Shinmura S (2000b). Optimal Linear Discriminant Function using Mathematical Programming. Disertation,

統計学とっておき勉強法』．講談社．

Okayama Univ.
5

Springer1: Shinmura S (2016). The New Theory of Discriminant Analysis after R Fisher, Springer. DOI:
10.1007/978-981-10-2164-0

6 Springer2: Shinmura S (2019a) High Dimensional Microarray Data Analysis – Cancer Gene Diagnosis andMalignancy Indexes by Microarray. Springer.
2֬཰ີ౓ؔ਺ͷϞʔυ୳ࡧͱͦͷԠ༻͸ͩͯ͜ະདྷେֶෳࡶ‫ܥ‬஌ೳֶՊ ࠤʑ໦ തত

1 ͸͡Ίʹ
౷‫ܭ‬తσʔλղੳʹ͓͍ͯɼ֬཰ີ౓ؔ਺ͷϞʔυʢ‫ۃ‬େ఺ʣΛਪఆɾ୳ࡧ͢Δ͜ͱ͸ॏཁͳ‫ڀݚ‬՝୊Ͱ͋Δɽྫ͑͹ɼϞʔυ୳ࡧΫϥελϦϯά͸ɼਪఆͨ֬͠཰ີ౓ؔ਺ͷϞʔυ఺΁޲͚ͯσʔλ఺Λߋ৽͠ɼಉ
͡Ϟʔυ఺΁ऩଋͨ͠σʔλ఺ʹରͯ͠ɼಉ͡ΫϥελϦϯάϥϕϧΛׂΓ౰ͯΔ [1]ɽ֬཰ີ౓ؔ਺ͷϞʔυΛར༻ͨ͠ଞͷσʔλղੳख๏͸ɼจ‫[ ݙ‬2, 3] ΛࢀরͤΑɽ֬཰ີ౓ؔ਺ͷϞʔυΛਪఆɾ୳ࡧ͢Δ্ͰॏཁͳλεΫͷ 1 ͕ͭɼ֬཰ີ౓ؔ਺ͷඍ෼Λਪఆ͢Δ͜ͱͰ͋Δɽ࠷΋୯७ͳΞϓϩʔν͸ɼ࠷ॳʹσʔλͷ֬཰ີ౓ؔ਺Λਪఆ͠ɼ࣍ʹͦͷີ౓ؔ਺ͷਪఆ݁Ռͷඍ෼Λ‫͢ࢉܭ‬Δ̎ஈ֊ਪఆͰ͋Ζ͏ɽ͔͠͠ͳ͕Βɼ͜ͷ 2 ஈ֊ਪఆ͸ɼ֬཰ີ౓ؔ਺ͷඍ෼Λਪఆ͢Δ্Ͱద੾ͳΞϓϩʔνͰ͸ͳ͍ɽԿ‫ͳނ‬Β͹ɼྑ͍֬཰ີ౓ؔ਺ͷਪఆ݁Ռ͕ɼඞͣ͠΋ྑ͍֬཰ີ౓ؔ਺ͷඍ෼ਪఆ݁ՌΛ΋ͨΒ͢ͱ͸‫ݶ‬Βͳ͍͔ΒͰ͋Δɽ
ΑΓద੾ͳΞϓϩʔν͸ɼ֬཰ີ౓ؔ਺ͷਪఆΛ࣮ߦͤͣɼ௚઀తʹ֬཰ີ౓ؔ਺ͷඍ෼Λਪఆ͢Δ͜ͱͰ
͋Ζ͏ɽ͜͜Ͱ͸ɼ͜ͷ௚઀ਪఆͷߟ͑ʹ‫ͮ͘ج‬ඍ෼ਪఆ๏ͱͦͷϞʔυਪఆ΁ͷԠ༻Λ঺հ͢Δ [4, 5, 6]ɽ
ඍ෼ਪఆ͸࠶ੜ֩ώϧϕϧτۭؒͷཧ࿦ʹ‫࣮͖ͮج‬ફతͳํ๏͕ߏங͞Εɼͦͯ͠ɼͦͷਪఆ๏Λ༻͍ͨϞʔυ୳ࡧͷͨΊͷஞ࣍తͳߋ৽ࣜΛ঺հ͢Δɽ

2 ର਺ີ౓ඍ෼ͷ௚઀ਪఆ [4, 6]
(1)

(2)

(d )

֬཰ີ౓ؔ਺ p(z) ΑΓੜ੒͞Εͨ n ‫ݸ‬ͷσʔλ఺ {zi = (zi , zi , . . . , zi z )⊤ }ni=1 ͕༩͑ΒΕ͍ͯΔͱ

͢Δɽ⊤ ͸సஔΛҙຯ͢Δɽ‫ج‬ຊతͳΞϓϩʔν͸ɼϞσϧ g (j) (z) Λਅͷର਺ີ౓ඍ෼΁ ∂j log p(z) Λ௚઀ద߹͢Δ͜ͱͰ͋Δɽ

Jj (g

(j)

!
1
)=
{g (j) (z) − ∂j log p(z)}2 p(z)dz
2
!
! "
!
#
1
1
=
{g (j) (z)}2 p(z)dz +∂j g (j) (z) p(z)dz +{∂j log p(z)}2 p(z)dz.
22্ࣜ͸ɼlim|z (j) |→∞ |g (j) (z)p(z)| → 0 ͱ͍͏ԾఆԼͰ෦෼ੵ෼Λ࣮ߦ͠ɼಋग़͞Ε͍ͯΔɽ{zi }ni=1 Λ༻͍
ͯɼg (j) ʹແؔ܎ͳӈลୈ 3 ߲Λআ͍ͨ Jj ͸࣍ͷΑ͏ʹਪఆͰ͖Δɽn'
1 % & (j)J$j (g (j) ) =g (zi )2 + 2∂j g (j) (zi ) .
2n i=1࣍ʹɼg (j) Λ࠶ੜ֩ώϧϕϧτۭؒ H ʹ੍‫͠ݶ‬ɼਪఆྔͷಋग़Λߦ͏ɽk Λ H ʹ͓͚ΔΧʔωϧؔ਺ͱ͢Δͱɼඍ෼ʹؔ͢Δද‫ݱ‬ఆཧ [7] ʹΑΓɼgj ͷ࠷దͳ‫ࣜܗ‬͸࣍Ͱ༩͑ΒΕΔɽ

g (j) (z) =

n
%
i=1

(
(j)
(j)
αi k(z, zi ) + βi ∂j′ k(z, z ′ )(z′ =z = α(j)⊤ k(z) + β (j)⊤ ∂j′ kj (z).
i

(

(1)

ࣜ (1) ͓͚Δ ∂j′ k(z, zi ) := ∂j′ k(z, z ′ )(z′ =z ɼ∂j′ ͸ k ͷ 2 ൪໨ͷม਺ z ′ ͷ j ൪໨ͷཁૉʹ͍ͭͯͷiඍ෼ɼk(z) := (k(z, z1 , . . . , k(z, zn ))⊤ , ∂j′ k(z) = (∂j′ k(z, z1 ), . . . , ∂j′ k(z, zn ))⊤ ɽͦͯ͠ɼ܎਺ϕΫτϧ

1

(j)

(j)

(j)

(j)

α(j) := (α1 , . . . , αn )⊤ ͱ β (j) = (β1 , . . . , βn )⊤ Λ࣍ͷ࠷খԽ໰୊Λղ͘͜ͱͰܾఆͰ͖Δɽ)*λj$ (j) , β$(j) := argmin J$j (g (j) ) + ∥g (j) ∥2H .
α
2α(j) ,β (j)্ࣜͷ ∥ · ∥H ͸ H ʹ͓͚ΔϊϧϜɼλj ͸ඇෛͷਖ਼ଇԽύϥϝʔλͰ͋Δɽ·ͨɼα(j) ͱ β (j) ͷϊϧϜΛਖ਼$ (j) ͱ β$(j) ͸ɼղੳతʹ‫ࢉܭ‬ՄೳͰ͋Δɽ࠷ऴతʹ, ରଇԽ߲ͱͯ͠༻͍Δ৔߹΋͋Δɽৄࡉ͸ׂѪ͢Δ͕ɼα਺ີ౓ඍ෼ͷਪఆྔ͸

g$(j) (z) =Ͱ༩͑ΒΕΔɽ

n
%
i=1

(j)
(j)
α
$i k(z, zi ) + β$i ∂j′ k(z, zi )3 Ϟʔυ୳ࡧ๏ [6]·ͣɼΧʔωϧؔ਺Λ࣍ͷ‫͢ݶ੍ʹࣜܗ‬Δɽ

k(z, zi ) = φ+∥z − zi ∥2
2σ 2

,

.

σ > 0 ͸Χʔωϧؔ਺ͷ෯Λද͢ύϥϝʔλɼφ ͸ඇෛɼ୯ௐඇ૿Ճɼඍ෼Մೳͳತؔ਺Ͱ͋Δɽ͜ͷΧʔωϧؔ਺Λ༻͍ͯɼඍ෼ͷਪఆྔ͸࣍ͷΑ͏ʹද‫͖Ͱݱ‬Δɽ

g$(j) (z) =(j)ࣜ (2) ʹ͓͍ͯɼβ.i

n
%
i=1

-

(j)
α
$i φ

+

∥z − zi ∥2
2σ 2

,

+
,
(j)
(j)
∥z − zi ∥2(j) zi − z
.
+ βi
ϕ
2
2
σ

2σ

/

.

(2)

(j)
d
= −β$i ɼϕ(t) = − dt
φ(t) Ͱ͋Δɽ

ෆಈ఺๏ʹ‫͖ͮج‬ɼg$(j) (z) = 0 ͱ͢Δ͜ͱͰɼ࣍ͷߋ৽ࣜΛಘΔɽz (j,τ +1) =

1 τ
2
1 τ
2'
2
∥z −zi ∥2
2 (j).(j) z (j) ϕ ∥z −z2 i ∥
σ
α
$
φ
+
β
2
i
i
i
i=1
2σ
2σ
.
0n .(j) 1 ∥zτ −zi ∥2 2
β
ϕ
2
i=1 i
2σ

0n

&

(3)

ࣜ (3) தͷ z τ ͸ద౰ͳॳ‫ظ‬஋͔Βͷ τ ճ໨ͷߋ৽݁Ռɼz (j,τ ) ͸ z τ ͷ j ൪໨ͷཁૉΛҙຯ͢Δɽ͋Δ৚݅Լ
Ͱߋ৽ࣜ (3) ͸ޯ഑্ঢ๏ͱ౳ՁͰ͋ΔͨΊɼϞʔυ୳ࡧ΁Ԡ༻ՄೳͰ͋Δɽࢀߟจ‫ݙ‬[1] K. Fukunaga and L. Hostetler. The estimation of the gradient of a density function, with applications in pattern recognition.
IEEE Transactions on Information Theory, 21(1):32–40, 1975.
[2] Y.-C. Chen. Modal regression using kernel density estimation: A review. Wiley Interdisciplinary Reviews: Computational
Statistics, 10(4):e1431, 2018.
[3] J.E. Chacón. The modal age of statistics. arXiv preprint arXiv:1807.02789, 2018.
[4] D. D. Cox. A penalty method for nonparametric estimation of the logarithmic derivative of a density function. Annals of
the Institute of Statistical Mathematics, 37(1):271–288, 1985.
[5] H. Sasaki, Y. Ono, and M. Sugiyama. Modal regression via direct log-density gradient estimation. In Proceedings ofthe 23th International Conference on Neural Information Processing (ICONIP), volume 9948, pages 108–116. Springer,
2016.
[6] H. Sasaki, T. Kanamori, A. Hyvärinen, G. Niu, and M. Sugiyama. Mode-seeking clustering and density ridge estimation
via direct estimation of density-derivative-ratios. Journal of machine learing research, 18(180), 2018.
[7] D.X. Zhou. Derivative reproducing properties for kernel methods in learning theory. Journal of Computational and Applied
Mathematics, 220(1-2):456–463, 2008.

2

Asymptotic properties of kernel PCA with
Gaussian kernel for high-dimensional data
Yugo Nakayama 1 , Kazuyoshi Yata2 and Makoto Aoshima2
1

1

Graduate School of Pure and Applied Sciences, University of Tsukuba
2Institute of Mathematics, University of Tsukuba

Introduction

Suppose we have independent and d-variate two populations, ⇧i , i = 1, 2, having an unknown mean
vector µi and unknown covariance matrix ⌃i ( O). We assume that lim supd!1 kµi k2 /d < 1
and tr(⌃i )/d 2 (0, 1) as d ! 1 for i = 1, 2, where k · k denotes the Euclidean norm. Here, for afunction, f (·), “f (d) 2 (0, 1) as d ! 1” implies lim inf d!1 f (d) > 0 and lim supd!1 f (d) < 1.
Suppose we have a d ⇥ n data matrix X = (x1 , ..., xn ), where xj s are independently taken from ⇧1
or ⇧2 . Let
ni = #{j|xj 2 ⇧i for j = 1, ..., n},where #A denotes the number of elements in a set A. Note that n = n1 + n2 . We assume that n
and ni s are independent of d, and ni
1 for i = 1, 2. For the sake of simplicity, we assume thattr(⌃1 )  tr(⌃2 ) andxj 2 ⇧1 for j = 1, ..., n1 and xj 2 ⇧2 for j = n1 + 1, ..., n.

(1)

In this talk, we studied asymptotic properties of the kernel PCA in the HDLSS context thatd ! 1 while n is fixed. Yata and Aoshima (2015) showed that the linear PCA enjoys geometricconsistency properties for the PC scores in high-dimensional mixture models. Let K be an n ⇥ ngram matrix with the (j, j 0 ) element k(xj , xj 0 ) = (xj )T (xj 0 ), where (·) is a feature map. Let
P n = I n n 1 1n 1Tn , where I n denotes the n-square identity matrix and 1n = (1, ..., 1)T . We definethe (centroid) gram matrix by
K 0 = P n KP n .
Note that rank(K 0 )  n 1. Let ˆ 1 · · · ˆ n 1 be the eigenvalues of K 0 . Then, we define theeigen-decomposition of K 0 by
K0 =

n
X1
i=1

ˆ i ûi ûT , where ûi = (ûi1 , ..., ûin )T , kûi k = 1 and ûT ûi0 = 0 for all i 6= i0 .
i

i

The ith (normalized) PC score of xj is given bypnûij (hereafter called sij ).
PP
We note that nj=1 s2ij /n = 1 for all i. Also, note that nj=1 sij = 0 when ˆ i > 0 from the facts thatPp
1Tn ûi = nj=1 sij / n and 1Tn K 0 1n = 0. Since the sign of an eigenvector is arbitrary, we assume
that (1Tn1 , 1Tn2 )û1 0 without loss of generality.
1

In this talk, we considered the following two typical kernels:(I) The linear kernel: k(xj , xj 0 ) = xTj xj 0 ; and(II) The Gaussian (radial basis function) kernel: k(xj , xj 0 ) = exp( kxj
where > 0.

2

xj 0 k2 / ),Kernel PCA with the linear kernel (I)In this section, we consider the KPCA with (I). We assume the following condition:(A-i) Var(kxµi k2 |x 2 ⇧i ) = O{tr(⌃2i )} as d ! 1 for i = 1, 2.

If ⇧i s are Gaussian, it holds that Var(kx µi k2 |x 2 ⇧i ) = 2tr(⌃2i ) for i = 1, 2, so that (A-i)
naturally holds. Let K 0(I) and sij(I) denote K 0 and sij given by using the kernel functions (I),respectively. Let µ = kµ1 µ2 k2 and ⌃ = |tr(⌃1 ) tr(⌃2 )|. We assume(A-ii) tr(⌃2i )/2µ = o(1) as d ! 1 for i = 1, 2.

Then, we have the following result.
Theorem 1. Assume (A-i) and (A-ii). Assume also
(A-iii) lim sup
d!1

⌃

n1

µ

< 1 when n22.

Then, it holds that as d ! 1(pn /n + oP (1)p2 1
s1j(I) =n1 /n2 + oP (1)when j = 1, ..., n1 ,when j = n1 + 1, ..., n.

(2)

Remark 1. Yata and Aoshima (2015) gave the results similar to Theorem 1 under ⌃ / µ = o(1)as d ! 1. Note that (A-iii) is milder than ⌃ / µ = o(1). When n2 = 1, (2) holds under (A-i)
and (A-ii).
Remark 2. If tr(⌃1 ) > tr(⌃2 ), (2) holds as d ! 1 under (A-i), (A-ii) and the following condition:
lim supd!1⌃ /(n2µ) < 1

when n12.

From Theorem 1, under (A-iii), one can classify xj s into two groups, e↵ectively, by the first PC
scores. If µ / ⌃ is small, we do not recommend to use the linear PCA.
In this talk, we investigated asymptotic properties of KPCA with kernel function (II). We showedthat the Gaussian kernel gives better performances than the linear kernel in HDLSS settings. Finally,
we checked performances of KPCA by numerical simulations and actual data analysis.

References[1] Yata, K. and Aoshima M. (2015). Principal component analysis based clustering for highdimension, low-sample-size data. arXiv:1503.04525.
2௒ߴ࣍‫ݩ‬εύʔεՃ๏Ϟσϧʹ͓͚Δม਺બ୒໊‫ݹ‬԰޻‫ۀ‬େֶ

1

ക௡ ༎ଠ

͸͡Ίʹ

‫؍‬ଌσʔλΛ (yi , xi ) ∈ R × Rd (i = 1, . . . , n) ͱ͢Δඇઢ‫ܗ‬ճ‫ؼ‬ϞσϧΛߟ͑Δ. എ‫͋ʹޙ‬Δਅͷճ‫ߏؼ‬!d଄͸Ճ๏త͔ͭεύʔεͰ͋Δͱ͢Δ: ͭ·Γ, f ∗ (x) = E[y | x] = j=1 fj∗ (xj ) ͔ͭ S ∗ = {j | fj∗ ̸≡ 0} ʹରͯ͠ s = |S ∗ | ≪ d Ͱ͋Δ. Fan et al. (2011) ͸ B-εϓϥΠϯ‫ج‬ఈΛ༻͍ͯपลճ‫਺ؔؼ‬Λม਺͝ͱʹਪఆ͠, ਪఆͨؔ͠਺ fˆj ʹରͯ͠ S NIS = {j | ∥fˆj ∥2 ≥ λn } ʹΑͬͯม਺બ୒͢Δ͜ͱΛఏҊͨ͠ (NIS). ͜n͜Ͱ, ∥ · ∥n ͸‫ ݧܦ‬ℓ2 ϊϧϜ, λ ͸ద౰ͳఆ਺Ͱ͋Δ. NIS ͸ sure screening property, ͭ·Γ, ద౰ͳ৚݅ͷ΋ͱ, 1 ʹऩଋ͢Δ֬཰Ͱ S ∗ ⊂ S NIS Λຬ଍͢Δ͜ͱ͕஌ΒΕ͍ͯΔ.

ຊߨԋͰ͸, ઢ‫ܗ‬ճ‫ؼ‬Ϟσϧʹର͢Δม਺બ୒‫ج‬४ͱͯ͠ఏҊ͞Εͨ sure independence screening (SIS:

Fan and Lv, 2008) Λࣗવʹඇઢ‫ܗ‬ճ‫ؼ‬Ϟσϧ΁ͱ֦ு͢Δ͜ͱͰ, ࠶ੜ֩ώϧϕϧτۭؒʹ͓͚Δճ‫ؼ‬Ϟσϧʹ‫ͳͨ৽ͮ͘ج‬ม਺બ୒‫ج‬४Λಋग़͢Δ. ·ͨ, ͜ͷม਺બ୒‫ج‬४͕ sure screening property Λຬͨ͢͜ͱΛࣔ͢.

2

KRIS: Kernel Regression based Independence Screeningઆ໌ม਺ߦྻͷྻϕΫτϧΛ z1 , . . . , zd ∈ Rn ͱͨ͠ͱ͖, SIS ͸ |zj⊤ y|/n ΛεΫϦʔχϯάͷͨΊͷείΞͱͯ͠ར༻͠, S SIS = {j | |zj⊤ y|/n ≥ λn } ͳΔม਺Λબ୒͢Δ. ͜͜Ͱ, y ͸໨తม਺, λn ͸ௐ੔ύϥϝʔλͰ͋Δ. SIS ͷείΞΛ “આ໌ม਺ͱ໨తม਺ͷ૬ؔ”, ͋Δ͍͸ “पลճ‫ؼ‬ͷਪఆྔ” ͱͯ͠ղऍ
͢Δ͜ͱͰ, SIS Λඇઢ‫֦΁ܗ‬ுͰ͖Δ (ྫ͑͹, Fan et al., 2011; Li et al., 2012; Balasubramanian et al.,2013; Zambom et al., 2018) ͕, ͜͜Ͱ͸, ࣍ͷΑ͏ʹਖ਼ଇԽਪఆྔͱͯ͠ղऍ͢Δ.
ิ୊ 1. SIS ʹΑͬͯબ୒͞ΕΔม਺Λ S SIS = {j | |zj⊤ y/n| ≥ λn } ͱ͢Δ. ͜ͷͱ͖,nβ̂jML = arg min
βj ∈R

1 "
(yi − xij βj )2 + λn |βj |,2n i=1

j = 1, . . . , d(1)ͱ͢Ε͹, S ML := {j | β̂jML ̸= 0} = S SIS ͕੒Γཱͭ.
ิ୊ 1ΑΓ, (1) ͷ໨తؔ਺Λඇઢ‫ܗ‬Խ͢Δ͜ͱͰ, ࣍ͷ࠷దԽ໰୊Λߟ͑Δ͜ͱ͕Ͱ͖Δ.
n
1 "fˆj = arg min(yi − fj (xij ))2 + λn ∥fj ∥Hj ,fj ∈Hj 2n i=1

j = 1, . . . , d.

(2)ͨͩ͠, Hj ͸Χʔωϧ kj Λ࣋ͭ RKHS Ͱ͋Δ. ද‫ݱ‬ఆཧ (Kimeldorf and Wahba, 1971) ΑΓ, (2) ͷ࠷ద!nղ͸ fj = i=1 αij kj (·, xij ) ͱ͔͚Δ͔Β, (2) ͸࣍ͷ࠷దԽ໰୊Λղ͘͜ͱͱ౳ՁͰ͋Δ.
#
1
α̂j =
arg min∥y − Kj αj ∥2n + λn α⊤j = 1, . . . , d.
(3)
j Kj α j ,αj =(α1j ,...,αnj )⊤ ∈Rn 21

ͨͩ͠, Kj = (kj (xpj , xqj ))p,q=1,...,n ͸, kj ʹ‫ͮ͘ج‬άϥϜߦྻͰ͋Δ. KKT ৚݅ΑΓ α̂j ̸= 0 (͕ͨͬͯ͠, fˆj ̸≡ 0) Ͱ͋Δ͜ͱͱ, ∥y∥K /n ≥ λn ͸౳ՁͰ͋Δ. Ҏ্ΑΓ, Χʔωϧճ‫ͮ͘جʹؼ‬มબ୒‫ج‬४ͱͯ͠j

S KRIS = {j | ∥y∥Kj /n ≥ λn }.

(4)Λߟ͑, ͜ΕΛ KRIS ͱ‫͢ʹͱ͜Ϳݺ‬Δ.
ద౰ͳ৚݅ͷ΋ͱ, ࣍ͷఆཧΛࣔ͢͜ͱ͕Ͱ͖Δ.
ఆཧ 1. λn = 2ξn(1−κ)/(4+6κ) ͜ͷͱ͖, ೚ҙͷ ζ ∈ (0, 1) ʹରͯ͠, ద౰ͳ৚݅ͷ΋ͱ,
&
$
%
'
(
M
P max ∥fˆj − fj ∥Hj ! λn " d exp(−nζ ) + exp −Cn(3+2κ)/(2+3κ)
1≤j≤d

+n

2/(2+3κ))3exp − n2/(2+3κ)
10

*

)

3
+ exp − n(3+2κ)/(2+3κ)
8*+͕੒Γཱͭ. ͨͩ͠, κ ͱ ξ ͸ͦΕͧΕ, Χʔωϧؔ਺ͷ‫ݻ‬༗஋͓Αͼ, ϊΠζʹؔ࿈͢Δఆ਺Ͱ͋Γ, C ͸

universal constant Ͱ͋Δ. ͞Βʹ, minj∈S ∗ ∥fjM ∥Hj ≥ 2λn ͳΒ͹,
&
'
(
∗
KRIS
P(S ⊂ S
) ! 1 − s exp(−nζ ) + exp −Cn(3+2κ)/(2+3κ)+n2/(2+3κ))3exp − n2/(2+3κ)
10

*

)

3
+ exp − n(3+2κ)/(2+3κ)
8*+͕੒Γཱͭ.
ఆཧ 1ΑΓ, n ͷࢦ਺෦෼ͷେখؔ܎ʹ஫ҙ͢Ε͹, KRIS ʹΑΔม਺બ୒͸,log d = o(nζ + n(3+2κ)/(2+3κ) )ͳΔ௒ߴ࣍‫Ͱݩ‬΋ޮ཰తʹม਺બ୒Λߦ͑Δ͜ͱ͕‫ظ‬଴ग़དྷΔ. ·ͨ, κ ͷ‫ݶۃ‬Λߟ͑Δ͜ͱͰ, Χʔωϧ

kj ͷ‫ݻ‬༗஋͕଎͘‫ݮ‬গ͢Δ΄Ͳ, ΑΓখ͞ͳγάφϧΛ‫ݕ‬ग़Ͱ͖Δ͜ͱ΋Θ͔Δ.

ࢀߟจ‫ݙ‬
Balasubramanian, K., Sriperumbudur, B., and Lebanon, G. (2013) “Ultrahigh dimensional feature screening via RKHS embeddings,” in Artificial Intelligence and Statistics, pp. 126–134.
Fan, J., Feng, Y., and Song, R. (2011) “Nonparametric independence screening in sparse ultra-highdimensional additive models,” Journal of the American Statistical Association, Vol. 106, pp. 544–557.
Fan, J. and Lv, J. (2008) “Sure independence screening for ultrahigh dimensional feature space,” Journalof the Royal Statistical Society: Series B, Vol. 70, pp. 849–911.
Kimeldorf, G. and Wahba, G. (1971) “Some results on Tchebycheﬃan spline functions,” Journal ofmathematical analysis and applications, Vol. 33, pp. 82–95.
Li, R., Zhong, W., and Zhu, L. (2012) “Feature screening via distance correlation learning,” Journal of
the American Statistical Association, Vol. 107, pp. 1129–1139.
Zambom, A. Z., Akritas, M. G. et al. (2018) “Hypothesis testing sure independence screening for nonparametric regression,” Electronic Journal of Statistics, Vol. 12, pp. 767–792.
2ΨϯϚɾμΠόʔδΣϯε࠷খԽʹ‫ͮ͘ج‬ϩόετ͔ͭεύʔεͳճ‫ؼ‬౦‫ۀ޻ژ‬େֶɹ઒ౡɹ޹ߦ
౷‫਺ܭ‬ཧ‫ॴڀݚ‬ɹ౻ᖒɹ༸ಙ

1

͸͡Ίʹ

KL μΠόʔδΣϯεʹ‫ͮ͘ج‬ճ‫ؼ‬͸ɼ࣍ͷΑ͏ʹఆٛͰ͖Δɼ
!
DKL (g(y|x), f (y|x; θ); g(x)) = DKL (g(y|x), f (y|x; θ))g(x)dx,
ͨͩ͠ɼg(y|x) ͓Αͼ g(x) ͸ɼσʔλΛੜ੒͢Δ෼෍Ͱɼf (y|x; θ) ͸ύϥϝτϦοΫϞσϧͰ͋Δɽg(y|x) ͓Αͼ g(x) ΛɼͦΕͧΕ‫ ਺ؔ౓ີݧܦ‬ḡ(y|x) ͱ ḡ(x) Ͱஔ͖‫͑׵‬Δͱɼ্‫ه‬ͷ KL μΠόʔδΣϯεʹ‫ͮ͘ج‬ճ‫ؼ‬ͷ‫ݧܦ‬ਪఆ͸࠷໬ਪఆʹ‫ͮ͘ج‬ճ‫ʹؼ‬Ұக͢Δɽ·ͨɼద੾ͳύϥϝτϦοΫϞσϧΛબ୒͢Δ͜ͱͰɼઢ‫ܗ‬ɼϩδεςΟοΫ͓ΑͼϙΞιϯճ‫͍ͨͬͱؼ‬ओཁͳճ‫ؼ‬Ϟσϧͷଟ͘ΛҰൠԽઢ‫ܗ‬ճ‫ؼ‬ͷ࿮૊ΈͰଊ͑Δ͜ͱ͕Ͱ͖Δ (Nelder and Wedderburn, 1972)ɽ
͔͠͠ɼKL μΠόʔδΣϯε͸ɼ֎Ε஋ʹऑ͍ɽͦ͜Ͱɼզʑ͸ɼϩόετͳμΠόʔδΣϯεͱͯ͠஌ΒΕ͍ͯΔɼΨϯϚɾμΠόʔδΣϯε (Fujisawa and Eguchi, 2008) ʹ‫ͮ͘ج‬ճ‫ؼ‬Λߟ͑Δɽ·ͨɼ͜Εʹεύʔεਖ਼ଇԽΛ૊Έ߹ΘͤΔ͜ͱͰɼϩόετ͔ͭεύʔεͳճ‫ؼ‬Λୡ੒͢Δɽ

2ΨϯϚɾμΠόʔδΣϯεʹ‫ͮ͘ج‬ϩόετ͔ͭεύʔεͳճ‫ؼ‬·ͣ͸ɼΨϯϚɾμΠόʔδΣϯεΛճ‫ؼ‬໰୊ͷઃఆʹରԠͤ͞ΔͨΊʹɼ৚݅෇͖෼෍͔ΒͳΔճ‫༻ؼ‬ͷΨϯϚɾμΠόʔδΣϯε΁ͱ֦ுΛߦ͏ɽճ‫༻ؼ‬ͷΨϯϚɾμΠόʔδΣϯε͸ҎԼͷࣜͰද͞ΕΔɽ

Dγ (g(y|x), f (y|x); g(x))
# 1
! "!
1+γ
1
1+γ
= log
g(y|x) dy
g(x)dxγ! !
1f (y|x)γ− log$%& γ g(x, y)dydx.
γf (y|x)1+γ dy 1+γ͜Εͷ‫ݧܦ‬ਪఆΛߟ͑ɼεύʔεਖ਼ଇԽΛՃ͑ͨ΋ͷΛ࠷খԽ͢Δ͜ͱͰɼҎԼͷࣜͰද͞ΕΔ
ϩόετ͔ͭεύʔεͳճ‫ؼ‬ͷ࿮૊Έ͕ୡ੒͞ΕΔɽ

arg min Dγ (ḡ(y|x), f (y|x; θ); ḡ(x)) + λP (θ)
θ
' n
)
1(
f (yi |xi ; θ)γ= arg min − log+ λP (θ).
$%
& γ
n
θ
f (y|xi ; θ)1+γ dy 1+γ

(1)

i=1

3

ਪఆΞϧΰϦζϜ

্‫ه‬ͷ࠷దԽ͸ɼ௨ৗͷํ๏Ͱ͸ɼਪఆΞϧΰϦζϜͷಋग़ࣗମ͕ࠔ೉ͱͳΔɽͦ͜Ͱɼิॿؔ਺
๏ͷҰͭͰ͋ΔɼMM ΞϧΰϦζϜ (Hunter and Lange, 2004) ͷߟ͑ํΛ༻͍Δ͜ͱͰɼ໨తؔ

਺ͷ஋ʹؔͯ͠୯ௐੑΛ΋ͭਪఆΞϧΰϦζϜͷಋग़ʹ੒ޭͨ͠ɽ໨తؔ਺ (1) ʹରԠ͢Δ MM
ΞϧΰϦζϜͷߟ͑ʹ‫਺ؔॿิͮ͘ج‬͸ҎԼͷࣜͰද͞ΕΔɽ
*+arg min hM M θ|θ(m)
θ
⎧
⎫
⎪
⎪
n
⎨
⎬
1 ( * (m) +f (yi |xi ; θ)γ= arg min −
αi θ
log *
+ λP (θ),γ+⎪γθ⎩ % f (y|x ; θ)1+γ dy 1+γ ⎪
⎭
i=1
i
ͨͩ͠ɼ

*

+

αi θ(m) =

⎧
⎪
⎨

$

⎫
⎧
3⎪ n
⎪
⎬
⎨(

&

γ
yi |xi ; θ(m)

f
*
+ γ
⎪
⎩ % f $y|x ; θ(m) &1+γ dy 1+γ ⎪
⎭
i

⎪
⎩ l=1

*%

f
f

$

$

&

γ
yl |xl ; θ(m)&1+γy|xl ; θ(m)
dy

⎫
⎪
⎬

+ γ ⎪.
1+γ ⎭۩ମྫͱͯ͠ɼઢ‫ܗ‬ճ‫ؼ‬+L1 ਖ਼ଇԽ (Tibshirani ,1996) Λର৅ͱͨ͠৔߹ͷ MM ΞϧΰϦζϜͷ
ߟ͑ʹ‫ͮ͘ج‬ਪఆΞϧΰϦζϜ͸ҎԼͷࣜͰද͞ΕΔɽ

arg min
β0 ,β,σ 2

n

p

i=1

j=1

(
γ
γ ( (m) (yi − β0 − xTi β)2log σ 2 +αi
+λ|βj |.
2
2(1 + γ)2σ࠲ඪ߱Լ๏ʹ‫ͮ͘ج‬ɼΑΓ۩ମతͳ֤ύϥϝʔλͷߋ৽ࣜ͸ҎԼͰද͞ΕΔɽn

1 ( (m)αi (yi − xi T β (m) ).
n
i=1
4 n
564 n
5
(m)
( (m)
( (m)
σ2
(m+1)
[−j]
βj
=S
αi (yi − ri )xij ,λαi x2ij .
γ
(m+1)

β0

=

i=1

σ2

(m+1)

= (1 + γ)

i=1

n
(
i=1

(m)

αi

(m+1)

(yi − β0

− xTi β (m+1) )2 .

7[−j]ͨͩ͠ɼS(a, λ) = sign(a)(|a| − λ)+ ɼri= k̸=j xik βk ɽൃද౰೔͸ɼ৚݅෇͖෼෍΁ͱ֦ுͨ͠ΨϯϚɾμΠόʔδΣϯεͷϩόετੑɾ਺஋࣮‫ݧ‬ͷ݁Ռʹ͍ͭͯ΋ใࠂΛߦ͏ɽࢀߟจ‫ݙ‬
Nelder, J. A. and Wedderburn, R. W. M. (1972). Generalized Linear Models. Journal of theRoyal Statistical Society: Series A, Vol. 135, No. 3, 370-384.
Fujisawa, H. and Eguchi, S. (2008). Robust parameter estimation with a small bias against heavy
contamination. Journal of Multivariate Analysis, Vol.99, 2053-2081
Hunter, D. R. and Lange, K. (2004) A tutorial on MM algorithms. The American Statistician,Vol. 57, No.1, 30-37
Tibshirani, R. (1996). Regression Shrinkage and Selection via the Lasso. Journal of the Royal
Statistical Society: Series B, Vol. 58, 267-288.