まえがき: 渡辺澄夫ベイズ理論の素晴らしさを多くの方に伝えたい

渡辺澄夫先生と初めてお会いしたのは、私が産総研の麻生英樹先生が主催していた研究会に呼ばれて、90分程度のセミナーで話をしたときでした。大阪大学に(専任)講師として着任した1994年の初夏で、ベイジアンネットワークの構造学習に関する内容だったと思います。そのときに、2-3分に1回くらい、終わってみると全部で20-30回くらい私に質問をされた方がいました。その方が渡辺先生でした。

渡辺先生が、「学習理論の代数幾何的方法」というタイトルで、IBIS(情報論的学習理論ワークショップ)という機械学習の研究会で講演されたのは、それから5年ほど後のことでした。私自身も当時、代数曲線暗号や平面曲線に関する論文も書いていて(J. Silverman氏との共著論文は、100件以上引用されている)、ベイズ統計学と代数幾何学はともに自信がありました。しかし、渡辺先生のIBISの話は、オリジナリティに富みすぎていて、まったく理解できませんでした。

2005-2010年あたりが、渡辺ベイズ理論が最も発展した時期で、多くの学生が渡辺研究室に入門しました。当時、私は渡辺研究室の若手の成果発表などを何度か聞きましたが、その基礎を勉強していないと理解は無理だと思いました。幸いにも、渡辺先生は2006年に『代数幾何と学習理論」(森北出版)、2009年に”Algebraic Geometry and Statistical Learning Theory” (Cambridge University Press)を出版されました。ともに、学習理論の代数幾何的な方法に関して述べた名著ですが、渡辺ベイズ理論の本質に関しては、語られていませんでした。後者の洋書に関しては、WAIC (widely applicable information criterion 広く使える(渡辺-赤池)情報量規準)に関する記述があります。

通常のベイズ統計学では、正則性(詳細は本文で定義します)を仮定していて、その場合には、サンプルを得たもとでの事後分布は正規分布になります。渡辺ベイズ理論は、代数幾何の手法を用いて、正則性を仮定しない場合の事後分布を導出する、既存のベイズ統計学の一般化になります。また、その帰結として、情報量規準であるWAICやWBIC(Widely applicable Bayesian information criterion)が導出されます。これらはAICやBICと同様の情報量規準になりますが、真の分布と統計モデルの間の関係が正則でない場合にも適用されます。そして、サンプルデータがあれば、それらの値はStanなどで容易に計算できます(本書の第2章)。

他方、2012に出版された『ベイズ統計の理論と方法』(コロナ社)は、WAICだけでなく、渡辺ベイズ理論に関する記述も含んでいます。ただ、数学の初心者を読者として想定していて、理論の詳細には触れておらず、本質を理解することが難しいと思いました。正直なところ、最初の2冊のいずれかを1年くらいかけて読んでから、『ベイズ統計の理論と方法』を読まないと、挫折しかねないと思いました。「正則でない場合は、AICやBICでなくWAICやWBICを使え」という言説を信じて使っているだけの人が大多数ではないだろうか、というような懸念もありました。

本書を執筆する決意を固めたのは、2019年に大阪大学の基礎工学研究科の集中講義で渡辺先生がいらしたときでした(大阪大学理学部に在籍していた2009年にも来ていただきました)。15コマを4日間で終えるという強行日程で、お疲れのようでしたので、毎日の講義が終わってからホテルまで、最終日は新大阪の駅まで自家用車で送りました。そのときの資料を読み返してみると、講義では、渡辺ベイズ理論の本質というよりは、ベイズ理論全般に関して語られたことが思い出されました。渡辺先生は、弱者や(優秀でない)学生に対して、難しい話を避けるなど、いたわりの気持ちをもたれますが、私が渡辺先生なら、学生が逃げようが、渡辺ベイズ理論の本質を伝えただろうと思いました。その思いが、本書にも込められています。当時、共立出版から、機械学習の数理100問シリーズの企画をしていました。そのときに、迷いもなく、編集の人に「渡辺澄夫ベイズ理論」を6巻のひとつに加えてください、と伝えました。

ただ、半年程度で完成するだろうと見込んでいた本書も、完成には1年を要しました。渡辺ベイズ理論が難解であるということは、百も承知でした。しかし、執筆を始めた頃、自分がその理論の表面しかわかってなかったことを知りました。また、これまでの渡辺先生の書籍や論文にかかれていない主張や、渡辺先生すら認識してない本質まで踏み込まないと、納得のいくものが完成しないだろうと思いました。そして、なぜかを問いながら突き詰めていくと、新たな視界が見えてくるということを、何度も繰り返していきました。渡辺ベイズ理論は、ひとつふたつの思いつきではなく、考え抜いて得られたアイデアを組み合わせて完成した、逸品であると思いました。

渡辺ベイズ理論は、正則性を仮定しない一般化を実現するために、既存のベイズ統計学に代数幾何、経験過程、ゼータ関数を適用して構成されています。これらは、線形代数や微分積分と違って、数学を専攻していないと使わない数学なので、難解と思われがちです。しかし、実際の渡辺ベイズ理論では、それらのほんの一部しか用いていません。本書は、この複雑に絡み合ったひもを解きほぐし、私と同じような時間や労力を経ずに、スムーズに理解できるようなガイドのような役割を担っています。

第1章で、事前分布・事後分布・予測分布、真のモデルと統計モデル、正則性を仮定しない一般化、指数型分布族について述べます。第2章は、本書で用いるStanなどMCMCの役割とStanの実際的な使い方について述べます。第3章では数学的な準備を、第4では正則性を仮定した議論を、第5章では情報量規準について述べます。ここまでは、通常のベイズ統計学と大きな差異はありません。第6章では、代数的集合と解析的集合、多様体、特異点とその解消、広中の定理など代数幾何の入門的なことを述べます。第7章では、状態密度の公式、事後分布の一般化、WAICの性質、Cross-Validation (CV)との等価性について述べます。第8章は、WBICと機械学習への応用について述べます。

本書は以下の特長をもつように執筆しました。
1. WAIC/WBICから学習係数の計算までの主要トピックをカバー。渡辺澄夫3部作で述べられた内容以外に、WBICやCVとの等価性など最近の成果も盛り込んでいる。
2. R/Stanによるソースコードを掲載。
3. 例を豊富に載せ、難解とされた渡辺ベイズ理論を、初学者が理解できるレベルにする。
4. 渡辺ベイズ理論の理解に必要な代数幾何の初歩を丁寧に解説(第6章)。
5. 演習問題の100問を解くことで、セルフチェックができる。

また、本書は、以下のいずれかの読者を想定しています。
1. 数理統計学に興味がある
2. WAICまたはWBICを利用したことがある
3. 線形代数と微分積分などで大学初年度程度の数学の素養がある
数学の知識として難しいことはないと思いますが、数式を読んで理解する力が必要となります。

渡辺澄夫ベイズ理論は、赤池の情報量規準、甘利の情報幾何とならぶ、日本統計学の偉業の一つで、多くの方に知っていただきたい、というのが私の願いです。

数学が苦手な方にワンポイントアドバイス
 数学が苦手という方は、「書く」習慣を身に着けてください。本書を書きながら読んでください。
 先生が教科書と同じことを板書していると、ノートを取らない人がいます。これは、学習効果を下げます。
 逆に、書きながら、目と触覚で(感覚神経と運動神経で)自分の中に入れていくと良いと思います。卒論・修論の発表会でも、数学科の先生は、理解しようとするとき、学生の発表中にメモをとりながら聞いています。
本書を読んで、数学が難しいと感じる人は、たとえば、各章の命題とその章の式をゆっくり書き写すことをすすめています。
 そのようにして頭に入れておくと、自分のものになり、どうして成立するのか、証明を考えたくなります。書き写してわからない場合は、同じことを翌日もやってみるとよいでしょう。
 これは、小平邦彦先生という昔の有名な数学者がすすめていた勉強法です(「数学の学び方」岩波書店)。書き写すだけで、ずっと身近になり、難しいと思わなくなります。

謝辞
 最後に、本書を執筆するにあたり、ご協力いただいた渡辺澄夫先生、青柳美輝先生、車谷優樹氏、大阪大学学生の新村亮介君、池尻巨拓君、久保田理士君、瀧尾竜佳君に感謝します。また、本書の立案から編集までお世話いただいた、共立出版株式会社大谷早紀氏に感謝します。

Lasso の Post-Selection Inference

Post-Selection Inferenceの切断分布を求める処理を書いてみました。

J. Lee and Dennis L. Sun and Yuekai Sun and Jonathan E. Taylor, “Exact post-selection inference, with application to the lasso”, The Annals of Statistics, volume 44,
number=3, pages 907-927 (2016}

# X, yを中心化する関数
cent=function(z){
    if(is.matrix(z)){
        p=ncol(z)
        for(j in 1:p)z[,j]=z[,j]-mean(z[,j])
    }
    else z=z-mean(z)
  return(z)
}

# 線形回帰のLassoの係数を求める関数
lasso=function(X,y,lambda){
## X,yは、中心化されていると仮定 
    p=ncol(X)
    out=NULL
    for(j in 1:p){
        SD=sd(X[,j])
        X[,j]=X[,j]/SD
        beta=sum(X[,j]*y)
        if(beta>lambda)out=c(out,(beta-lambda)/SD)
        else if(beta< -lambda)out=c(out,(beta+lambda)/SD)
        else out=c(out,0)
    }
    return(out)
}

# 多面体で表現される区間(モデルと符号で条件付)
intervals=function(X,y,lambda,M,s,k){
    n=nrow(X)
    p=ncol(X)
    m=length(M)
    P=X[,M]%*%solve(t(X[,M])%*%X[,M])%*%t(X[,M])
    XX=X[,M]%*%solve(t(X[,M])%*%X[,M])
    A=rbind(1/lambda*t(X[,-M])%*%(diag(n)-P),
        -1/lambda*t(X[,-M])%*%(diag(n)-P),
        -diag(s)%*%solve(t(X[,M])%*%X[,M])%*%t(X[,M])
        )
    b=c(rep(1,p-m)-as.vector(t(X[,-M])%*%XX%*%s),
        as.vector(rep(1,p-m)+t(X[,-M])%*%XX%*%s),
        -as.vector(lambda*diag(s)%*%solve(t(X[,M])%*%X[,M])%*%s)
        )
    eta=(solve(t(X)%*%X)%*%(t(X)))[k,]
    cc=eta/as.vector(t(eta)%*%eta)
    z=(diag(n)-cc%*%t(eta))%*%as.matrix(y)
    Ac=as.vector(A%*%cc)
    Az=as.vector(A%*%z)
    nu.max=0
    nu.min=0
    nu.zero=0
    for(j in 1:p){
      if(Ac[j]>0)nu.max=max(nu.max,(b[j]-Az[j])/Ac[j])
      else if(Ac[j]<0)nu.min=min(nu.min,(b[j]-Az[j])/Ac[j])
      else nu.zero=min(nu.zero,b[j]-Az[j])
    }
    return(c(as.vector(t(eta)%*%as.matrix(y)),nu.min, nu.max,nu.zero))
}

# 10進数を2進数に変換する関数
binary=function(i,m){
  out=NULL
  for(j in 1:m){
    out=c(2*(i%%2)-1,out)
    i=i%/%2
  }
  return(out)
}

# モデルと符号に関する多面体の区間を、符号を動かして、合併させている。
bind.intervals=function(u,v){
  p=length(u); q=length(v)
  u=c(u,Inf); v=c(v,Inf)
  u.state=1; v.state=1
  w=NULL
  i=1; j=1
  while(i<=p||j<=q){
    if(u[i]<v[j]){
      if(v.state==1)w=c(w,u[i])
      i=i+1
      u.state=-u.state
    }
    else if(u[i]>v[j]){
      if(u.state==1)w=c(w,v[j])
      j=j+1
      v.state=-v.state
    }
    else {
      if(i!=p+1&&u.state==v.state)w=c(w,v[j])
      i=i+1; j=j+1
      u.state=-u.state; v.state=-v.state
    }
  }
  return(w)
}
bind.intervals(u,v)

##  実行例
# データ生成
n=100
p=5
X=matrix(rnorm(n*p),n,p)
y=X[,1]*2-X[,2]*3+rnorm(n)*0.4
# 中心化して、Lassoの係数を求め、アクティブ集合とそれぞれの符号を求める
X=cent(X)
y=cent(y)
lambda=40
beta=lasso(X,y,lambda)
M=NULL
ss=NULL
for(j in 1:p){
  if(beta[j]>0){M=c(M,j); ss=c(ss,1)}
  else if(beta[j]<0){M=c(M,j); ss=c(ss,-1)}
}
# 多面体の区間を求める
m=length(M)
L=2^m
print(intervals(X,y,lambda,M,ss,1)[1])
print(M)
print(ss)
S=NULL
for(i in 1:L){
  s=binary(i,m)
  u=intervals(X,y,lambda,M,s,1)
  print(s)
  print(u[2:3])
  S=bind.intervals(S,u[2:3])
}
S
pnorm(-1)

カーネルの苦手意識をいかに克服するか: 「機械学習のためのカーネル100問 with R」(共立出版)まえがきから抜粋

私は、機械学習の手法の中でもカーネルは、特に苦手でした。福水健次著「カーネル法入門」(朝倉書店)を読もうとして、何度も挫折していました。福水先生を、大阪大学の集中講義にお呼びして、学生と一緒に1週間講義を聞きましたが、本質は理解できませんでした。この書籍は、執筆を着手した当初は、自分自身の苦手意識を払拭することを目的としていました。しかし、本書が完成した現在、どうすれば読者にカーネルの苦手意識から脱却できるかを、お伝えできるようになりました。

ところで、機械学習の研究者ですら、カーネルを理解しないで、使っているだけの人がほとんどです。このページを開いている方は、苦手意識を克服したいという前向きな気持ちをお持ちだと思います。

そのための最短経路として最もおすすめしたいのが、数学を基礎から学ぶということです。カーネルは、その背後にある数学にしたがって動作します。理解するまで考え抜くことが重要です。カーネルの理解に必要な数学は、関数解析と呼ばれるものです(第2章)。線形代数や微分積分ならわかるという方でも、戸惑うことがあるかもしれません。ベクトルといえば有限次元ですが、関数の集合は無限次元で、線形代数として扱えます。完備化という概念が初めてという場合、時間をかけていただければと思います。しかし、この第2章を突破すれば、カーネルのすべてが理解できると思います。

本書は、機械学習の数理100問のシリーズの3巻目(全6巻)になります。書籍ですから、既存のカーネルの書籍が存在するのにどうして出版するのか(いわゆる大義)がないと、出版には至りません。本書の特徴として、以下の点をあげることができます。

  1. 数学的命題として証明し、正しい結論を述べているので、読者が本質までたどり着くことができる。
  2. 機械学習の数理100問シリーズの他書と同様、ソースプログラムと実行例を提示して理解を促している。数式だけであれば、特にカーネルの場合、読者が最後まで理解することは容易ではない。
  3. 関数解析の基本的事柄を理解(第2章)してから、それ以降の章での応用を検討していて、数学の予備知識を前提としていない。
  4. RKHSのカーネルと、ガウス過程のカーネルの両方を検討し、しかも両者の扱いを明確に区別している。本書では、それぞれ第5章、第6章で述べている。

国内外のカーネルの書籍を調査しましたが、上記で2個以上満足しているものはありませんでした。

本書の出版に至るまでに、いろいろな失敗を経験してきました。毎年、機械学習の各分野を数学とプログラミングの演習問題を100問解きながら学ぶ講義(大阪大学大学院)をしています。スパース推定(2018年)、グラフィカルモデル(2019年)では人気をはくし、2020年のカーネルも履修者が100名以上になりました。しかし、毎週2日以上講義の予習をしてのぞんだものの、苦手意識も手伝ってか、その講義はうまくいきませんでした。学生の授業アンケートを見ても明らかでした。ただ、そうした問題点の一つ一つを分析し、改良を加えて、本書が誕生しました。

読者の皆さんが,私と同じ道(試行錯誤で時間やエネルギーを消耗する)を辿らずに,効率的にカーネルを学ぶことができればという思いがあります。本書を読んだからといって直ちに論文が書けるわけではありませんが、確実な基礎が身につきます。難しそうに思えていたカーネルの論文がスムーズに読め、一段高いところからカーネルの全体が見えるようになります。また、機械学習の研究者の方でも楽しめるような内容になっています。皆さんが本書を活用し、それぞれの分野で成功を収めていただければ、幸いと考えています。

スパース推定でSCoTALASSの第2主成分以下を選択するとき

テキスト(7.7)の導出は、$L=u_k^{\top}Xv_k-\mu(u_k^\top u_k-1)$の最大化ではなく、
$$L’:=u_k^{\top}Xv_k-\mu(u_k^\top u_k-1)-\lambda\sum_{i=1}^{k-1}(u_i^\top u_k)^2$$の最大化によって得られます。また、(7.7)の$u_k$は大きさが1である$u_1,\ldots,u_{k-1}$と直交しています。

数学的帰納法で、$h=1,\ldots,k-1$の場合に成立していて、$k$について正しいことを示します。$L’$を$u_k$で微分して0とおくと、$$Xv_k-2\mu u_k-2\lambda\sum_{i=1}^{k-1}u_i=0$$となり、左から$P_{k-1}^\perp$をかけると、$$P_{k-1}^\perp Xv_k-2\mu(I- \sum_{j=1}^{k-1}u_ju_j^\top )u_k-2\lambda\sum_{i=1}^{k-1}(I- \sum_{j=1}^{k-1}u_ju_j^\top )u_i=0$$となります。また$L’$を$\lambda$で微分すると$u_ku_j^\top =0$, $1\leq j\leq k-1$となり、また、数学的帰納法の仮定から、$i\leq j\leq k-1$について $u_iu_j^\top =\delta_{i,j}$が成立します。したがって、前式は、$$P_{k-1}^\perp Xv_k-2\mu u_k=0$$となり、$L’$を$\mu$で微分して0とおいて得られる$\mu^\top \mu=1$より、(7.7)が得られます。

行列分解の更新式

(6.11)の劣微分をとって、(6.12)になります。そして、(6.13)を繰り返し適用すると、(6.12)の等号が成立するようになります。$M=\sum_{i=1}^r d_i{u}_i{v}_i$ ($r$は$M$の階数)と書くとき、$[\Omega,Z,M]$の$n$個の特異値で$\lambda$以下のものは、$M$の$r$個の特異ベクトルに対応する場合、しない場合のいずれでも、$S_\lambda(\cdot)$の操作によって0になります。

前者の場合、$S_\lambda([\Omega,Z,M])$の対応する特異値が0になり、$M=S_\lambda([\Omega,Z,M])$であれば、階数$r$が$M$と一致せず、$M$の階数を減らして、(6.13)の更新をさらに続けます。後者の場合は、$M$の特異値とは直交する特異ベクトルで特異値が$\lambda$以下のもの($\sum_{k=r+1}^nd_k\tilde{u}_k\tilde{v}_k$, $d_k\leq \lambda$)が、(6.13)の更新を行っても、$[\Omega,Z,M]$に含まれたままになります。

したがって、(6.12)の最初の項が$M- [\Omega,Z,M]$とかけ、(6.13)が平衡状態に達した場合、(6.12)全体が0になります。

Graphical Lassoの解がなぜ正定値になるのか

スパース推定の 5.2節にあるgraphical lassoの解が非負定値になるのかというご質問をいただきました。研究者でも理解している人がほとんどいない問題です。難しいと感じた方は、遠慮なくご質問ください。

$W$は最初サンプル共分散行列$S$であり($W=S+\lambda I$で始める方法もある)、正定値行列の逆行列は正定値ですから、$W$が最後まで非負定値であることを示せればよいことになります。すなわち、毎回の$W$の更新が非負定値を非負定値に変換するものであれば良いことになります。まず、$$ \det \left[ \begin{array}{ll}W_{11}&w_{12}\\w_{21}&w_{22}\end{array}\right]=\det \left[ \begin{array}{ll}W_{11}&w_{12}\\0&w_{22}-w_{21}W_{11}^{-1}w_{12}\end{array}\right]$$となることに注意します。更新前に$W$が非負定値なら$,W_{11}$も非負定値であり、$W_{11}$は更新しないので、右辺の右下の成分が減少しなければ、更新後も非負定値です。以下では、$w_{21}W^{-1}w_{12}$が増加しないことを示します。(5.11)は、$$\frac{1}{2}\beta^TW_{11}^{-1}\beta-\beta^{T}s_{12}+\lambda\|\beta\|_1$$の最小化になります。$\beta=W^{^1}_{11}(s_{12}+\lambda\psi_{12})$を代入すると、$\beta_j\not=0, =0$によらず$|\beta_j|=-\lambda\psi_{12,j}\beta_j$となり($\psi_{12,j}$は$\psi_{12}$の第$j$成分)、$\|\beta\|_1=-\lambda\psi_{12}^T\beta$となる。したがって、
$$-\frac{1}{2}(s_{12}+\lambda\psi_{12})^TW_{11}^{-1}(s_{12}+\lambda\psi_{12})$$となるので、双対問題である$\|\gamma\|_\infty\leq \lambda$のもとでの
$$-\frac{1}{2}(s_{12}+\gamma)^TW_{11}^{-1}(s_{12}+\gamma)$$の最大化になり、その最適解$\gamma$を用いて、$\psi_{12}=\gamma/\lambda$および $w_{12}=s_{12}+\lambda\psi_{12}$((5.9)式)が得られます。そして、次回($p$回後)回ってきたときに$W_{11}$の値は変わっていますが、$W$と$W_{11}$の正定値性は維持されます。更新によって、$w_{12}$の値はより良い値となるので、$w_{21}W^{-1}_{11}w_{12}$の値はより小さくなり、正定値性が維持されます。

参考文献: R. Mazumder and T. Hastie, “The graphical lasso: New insights and alternatives”, Electronic Journal of Statistics. Vol 6, pp 2125-2149 (2012)

「カーネルの機械学習への応用」が登場

カーネルの機械学習への応用の原稿を共立出版に提出しました。誤植を直したり、まえがきや索引をつけるのに2ヶ月位かかるのが普通です。数学だけでは難しくてめげやすい分野です。今回もプログラムをたくさん入れました。Python版もまもなく出てくると思います。

機械学習の数理100 問シリーズ3 「カーネルの機械学習への応用100 問with R」鈴木 讓

第1章 正定値カーネル
1.1 行列の正定値性
1.2 カーネル
1.3 正定値カーネル
1.4 確率
1.5 Bochnerの定理
1.6 文字列、木、グラフのカーネル

第2章 Hilbert空間
2.1 距離空間と完備性
2.2 線形空間と内積空間
2.3 Hilbert 空間
2.4 射影定理
2.5 線形作用素
2.6 コンパクト作用素

第3章 再生核Hilbert空間
3.1 RKHS
3.2 Sobolev 空間
3.3 Mercer の定理

第4章 カーネル計算の実際
4.1 カーネルRidge 回帰
4.2 カーネル主成分分析
4.3 カーネルSVM
4.4 スプライン
4.5 Random Fourier Features
4.6 Nystrom 近似
4.7 不完全Cholesky 分解

第5章 MMDとHSIC
5.1 RKHSにおける確率変数
5.2 MMDと2標本問題
5.3 HSICと独立性検定
5.4 特性カーネルと普遍カーネル
5.5 経験過程入門

第6章 Gauss 過程と関数データ解析
6.1 回帰
6.2 分類
6.3 補助変数法
6.4 Karhunen-Loeve 展開
6.5 関数データ解析

スパース推定の命題17の証明

条件付き独立性などの関係が、以下の条件を満足するときに、無向グラフの分離性によってすべて表現できることが知られている(J. Pearl, “Probabilistic Reasoning in Intelligent Systems”, 1988)。$$X_A\perp X_B\mid X_C \Longleftrightarrow X_B\perp X_A|X_C\tag{1}$$$$X_A\perp (X_B\cup X_D)\mid X_C \Longrightarrow X_A\perp X_B|X_C, X_A\perp X_D\mid X_C\tag{2}$$ $$X_A\perp (X_C\cup X_D)\mid X_B, X_A\perp_E X_D\mid (X_B\cup X_C) \Longrightarrow X_A\perp (X_B\cup X_D)\mid X_C\tag{3}$$ $$X_A\perp X_B\mid X_C \Longrightarrow X_A\perp X_B\mid (X_C\cup X_D)\tag{4}$$ $$X_A\perp X_B\mid X_C \Longrightarrow X_A\perp X_k \mid X_C\ {\rm or}\ X_k \perp X_B|X_C\tag{5}\ ,\ k\not \in C$$ ただし、各方程式で$A,B,C,D$は、排他的な$V$の部分集合であるとする。このうち、条件付き独立性に関しては(4)(5)以外は、満足されることがわかる。たえとえば(3)は、仮定$$f(x_A,x_B,x_C,x_D)f(x_C,x_D)=f(x_A,x_C,x_D)f(x_B,x_C,x_D) \tag{6}$$ $$f(x_A,x_B,x_C,x_D)f(x_B,x_C)=f(x_A,x_B,x_C)f(x_B,y_C,x_D)\ ,$$から、$f(x_B,x_C)f(x_A,x_C,x_D)=f(x_A,x_B,x_C)f(x_C,x_D)$が得られ、これを周辺化して、$$f(x_C)f(x_A,x_C,x_D)=f(x_A,x_C)f(x_C,x_D)\tag{7}$$が得られる。そして、(6)(7)は$$f(x_A,x_B,x_c,x_D)f(x_C)=f(x_A,x_c)f(x_B,x_C,x_D)$$を意味し、さらに(3)を意味する。また、(4)は命題16より成立する。したがって、(5)が成立することを言えば十分である。まず、$k\in A$または$k\in B$であれば、自明に成立する。そして、正規分布であるので、$k\not\in A\cup B\cup C$のもとで、$X_A\perp X_k \mid X_C$と $X_k \perp X_B|X_C$の両方が成立しないのは、 $X_A\perp X_B|X_C$と矛盾する。したがって、(5)が成立する。

以上より、正規分布の場合、無向グラフの分離性によって、条件付き独立性のすべてが無向グラフで表現できる。

LARS

Lasso では、非ゼロ係数が1個以上ある$\lambda$で最大の値が一意に決まります。2乗誤差を$N$で割らない場合、そのような$\lambda$ は$\langle x^{(j)}, y\rangle$の絶対値の最大値($1\leq j\leq p$)になります。ただし、$x^{(j)}$は$X\in {\mathbb R}^{N\times p}$の$j$列目、$y\in {\mathbb R}^N$であるとします。そのような$\lambda$, $j$を今後$\lambda_0$, $j_0$と書きます。

LARSは、$\lambda\leq \lambda_0$に対して、$\beta(\lambda)$を以下のように定義します: それまでに$\lambda_0,\lambda_1,\ldots,\lambda_{k-1}$, $\beta_0=0,\beta_1,\ldots,\beta_{k-1}$, ${\cal S}=\{j_0,\ldots,j_{k-1}\}$が得られているとして($k\geq 1$)、以下を繰り返します。

1. 最初の$k$成分がゼロ、残り$p-k$成分が0のベクトル$\Delta_{k-1}$を定義
2. $\lambda\leq \lambda_{k-1}$について、 $\beta(\lambda):=\beta_{k-1}+(\lambda_{k-1}-\lambda)\Delta_{k-1}$および$r(\lambda):=y-X\beta(\lambda)$を定義。
3. $\langle x^{(j_k)},r(\lambda_k)\rangle$の絶対値が$\lambda_k$に一致する 最大の$\lambda_k$およびその$j_k$を見出し、$j_k$を$\cal S$に加える。
4. $\beta(\lambda)$, $r(\lambda)$の定義域を$\lambda_k\leq \lambda$に限定し、$\beta_k:=\beta(\lambda_k)$とおく。

ここで、$$\Delta_{k-1}:=\left[
\begin{array}{c}
(X_{\cal S}^TX_{\cal S})^{-1}X_{\cal S}^Tr(\lambda_{k-1})/\lambda_{k-1}\\
0
\end{array}
\right]\ ,
$$
と選べば、各$k=0,1,\ldots,p-1$について、$$\lambda\leq \lambda_k\Longrightarrow \langle x^{(j_k)}, r(\lambda)\rangle=\lambda$$
が成立します。ただし、$X_{\cal S}\in {\mathbb R}^{N\times k}$は、$x^{(j)}$, $j\in {\cal S}$を列に持つ$X$の部分行列とします。