すべてがMFになる
すべてがFになる,映像化するみたいですね.犀川創平も西之園萌絵も配役がイメージと違って一部で話題になっていました.さて,最近テンソル分解を使った論文をよく見かけるのですが,いまだにきちんと整理できずにいます.テンソルかわいいよ,テンソル.
そこで,まずは行列分解(matrix factorization, matrix decomposition)を整理してみようと思います.行列の分解手法というと線形代数的な観点からは簡単に思いつくだけでも
- 固有値分解
- LU分解
- コレスキー分解
などがありますが,これらは分解前の行列と分解後の行列が一致する(たとえばA=LU)方法です.一方で,機械学習やデータマイニング界隈(特にレコメンデーション等)で出てくる行列分解というのは,大規模データや関係性データの中から低ランクの構造を抽出することや次元圧縮を目的としています.なので,正確に言うならば,行列分解というよりは低ランク行列近似と呼ぶ方が正しいように思います.
これらの低ランク行列近似の方法論は暗に低ランク性を仮定しているということがポイントです.ということで,
- 特異値分解(Singular Value Decomposition; SVD)
- 主成分分析(PCA)
- CUR分解 or CMD(Compact Matrix Decomposition)
- 非負値行列因子分解(Non-negative Matrix Factorization; NMF)
あたりを簡単にまとめてみたいと思います.ちなみに行列分解の専門家ではないので,間違いがあればご指摘ください.
特異値分解(SVD)
特異値分解は以下の式の解として得られる行列Yによる近似です.(Fはフロベニウスノルム)
その結果として,行列Xは
のように分解(近似)できます.Σは特異値を上から順にk個とって対角行列にしたものです.SVDは多くの分野で使われているものの,行列のサイズが大きくなったときには計算コストが大きくなります.
主成分分析
主成分分析は古典的な多変量解析手法ですが,やっていることはSVDと同じです.主成分分析における主成分と因子負荷量はSVDで分解した行列を用いると以下のように表すことができます.
そのため,左特異ベクトルと特異値の積が各主成分になっていて,右特異ベクトルがそれぞれの因子負荷量になっているという関係なのですね.
CUR分解 or CMD
2009年のid:mamorukさんのエントリではCUR分解と呼ばれています.(簡単に調べてみたけど)特に日本語での呼び名はないっぽいです.
CURやCMDのモチベーションはSVDによる分解では,大規模だがスパースな行列Xをに分解したときに,やが密行列になってしまうという問題を防ぎたいというものです.もちろんこれが問題かどうかはタスク依存だと思いますが,解釈しやすさなどを考えるとやが疎行列になると嬉しい訳です.また,元行列がスパース行列なので,そのスパース性を失うのももったいないというモチベーションがあります.
そこで,SVDでは密行列だったやに対し,元のスパース行列からサンプリングしてやをつくり,行列近似を行うというのがCUR分解のイメージです.
提案論文では一様分布からサンプリングをしていて,その後もう少し賢いサンプリング法(CMD)が考えられています.サンプリングするだけでいいの!というのは驚きですが,元行列がスパースな場合,よくよく考えてみるとPCA(SVD)がやっているorthogonal projectionとサンプリングがほぼほぼ変わらないというのは直感的には真であると思います.
NMF
非負値行列因子分解(NMF)も結構いろんなところで見かける行列分解手法で,非負行列Xが与えられたときに,のように二つの行列の積に分解します.その名の通り,分解した行列U, Vがそれぞれ非負のため,解釈しやすい,現象論的に負の値を取らない現象を表現できる,ということがウリです.
主成分分析(やSVD)では独立性が仮定されていたのに対し,NMFでは非負性を用いることで,独立性を仮定することなく行列分解を可能としています.
近似の評価尺度としては,XとUVのフロベニウスノルムの最小化,
一般化KLダイバージェンスの最小化
などが利用されるようです.
以前,持橋先生の資料でLDAで得られたトピック行列と混合比行列は正規化するとNMFと同じことをしているという内容があったように記憶しています.
まとめ
というわけで,非常に簡単ですが,SVD, CUR, NMFあたりを大雑把にまとめてみました.詳細は各手法の理論背景,計算方法,実装等を眺めるのが良いと思いますが,簡単なプレビューとしてお役に立てばと思います.
PFIの比戸さんが昨年まとめられているKDD2013のbest paperのmatrix sketchは行列分解ではないですが,ある巨大な行列を小さな行列に圧縮するという方法でたぶん似たような考えの方法ではないかと思います(未読).行列分解や次元削減の界隈は圧縮センシング等のスパース性を設計原理としたモデリングにも通ずる発想ですよね.というわけで,そろそろテンソル理解したい.誰かおせーて.
参考
- 昨年のMachine Learning Advent Calendarでysks3nさんがmatrix factorizationについての解説エントリを書かれています.
- NMFについてはid:naoyaさんのNMFに関する2009年の解説エントリやid:a_bickyさんのNMFに関する2010年の解説エントリがわかりやすいです.
- id:mamorukさんも紹介していたCURに関するCIKM 2008のチュートリアル
- LIBSVMやLIBLINEARで有名なNational Taiwan UniversityのProf.Chih-Jen LinのグループがLIBMFという行列分解のライブラリをつくってるみたい.まだ動かしてないので未確認.
- 追記:ブコメでid:reposeさんが教えて頂いたのですが,University of KonstanzのDr.RendleによるlibFMというライブラリもあるそうです.こっちはFactorization machinesという彼らのICDM2010のpaperでの提案手法が元になっています.
Learning Latent Variable Gaussian Graphical Models (ICML2014)読んだ
MLaPPアドベントカレンダー12日目という下書きが下書きエントリにずっと入っていてそろそろ腐敗し始めているため,きまずくてブログが更新できない昨今です.MLaPPアドベントカレンダーは2年越しの計画という言い訳を思いついているので,今年の年末にがんばりたいですね….
さて,学生さんへの紹介用にICML2014のLearning Latent Variable Gaussian Graphical Modelsの説明スライドをつくったので,ブログにのっけておきます.細かい話は一切書いてないですが,そこらへんは論文を読んでください.
Learning Latent Variable Gaussian Graphical Models from harapon
ICML2014で面白そうだと思った論文は
- Joint Inference of Multiple Label Types in Large Networks
- Learning Modular Structures from Network Data and Node Variables
- Efficient Dimensionality Reduction for High-Dimensional Network Estimation
- Von Mises-Fisher Clustering Models
- Bayesian Nonparametric Multilevel Clustering with Group-Level Contexts
- Hierarchical Dirichlet Scaling Process
- Fast Computation of Wasserstein Barycenters
- Learning Latent Variable Gaussian Graphical Models
- Affinity Weighted Embedding
- Rectangular Tiling Process
- Rank-One Matrix Pursuit for Matrix Completion
- Multiresolution Matrix Factorization
- Understanding the Limiting Factors of Topic Modeling via Posterior Contraction Analysis (best paper)
- On Modelling Non-linear Topical Dependencies
- Admixture of Poisson MRFs:A Topic Model with Word Dependencies
あたりです.自分の興味の偏りがわかりますね:-)
MLaPP アドベントカレンダー11日目:Ch.11 Mixture models and the EM algorithm
この章は混合モデルとEMアルゴリズムについて.前半の混合モデルについてはちゃんと読めたけど,EMについてはそんなに詳しく読めていないし,知っているところも多かったのでだいぶ飛ばしてしまった.混合モデル周辺はこれまでそんなに触ったことがないので,実装して挙動はきちんと確かめたいと思います.
Latent variable models
-
- グラフィカルモデルは2変数間の依存関係をエッジで表現するので高次元
- 別のアプローチとして観測変数は共通の隠れ要因から生まれているので相関があるという考え方
- これがLatent variable model
- このモデルは潜在変数のないモデルよりフィットが難しいが2つの理由で重要な利点がある
- (1)直接的に相関を表すモデルより少ないパラメータ数(Fig 11.1)
- (2)LVMにおける隠れ変数はデータ圧縮表現のボトルネックとして作用
Mixture models
-
- 最もシンプルな場合:が離散潜在変数を表す
- これらに対して離散的な事前分布を用いる
- 尤度は
- ここで: k番目のbase distribution
- これらのモデルはK個のbase distributionを混ぜるのでmixture modelとして知られる
- これはの凸結合である
- Mixture of Gaussians
- 最も広く使われる混合モデルはmixture of Gaussians, Gaussian mixture model
- このモデルではbase distributionはの多変量正規分布
- Mixture of multinoullis
- 多くの種類のデータに関する密度モデルを定義するために混合モデルを使う
- たとえばD次元のビットベクトルでデータが構成されているとき
- 適切なクラス条件付き密度波ベルヌーイ積である
- モデルをよりパワフルにするために潜在変数を導入
- 構成分布は因数分解できるが,混合分布はそうではない
- このように単一のベルヌーイ積モデルと異なり,変数間の相関を捉えられる
- Using mixture models for clustering
- 混合モデルの2つのアプリケーション
- Mixtures of experts
- 分類や回帰には識別モデルも使えるが,入力空間の異なる部分に対して3つの異なる回帰モデルを適用するのが望ましい場合がある
- このようなモデルはmixture od experts (MoE)と呼ばれる(Jordan and Jacob, 1994)
- 基本アイデア:各サブモデルは入力空間のある部分において"expert"として考える
- はgating functionを呼ばれる
- 入力値に応じてどのexpertsを用いるかを決める
- このモデルのfitについてはSec 11.4.3で議論
- expertとして任意のモデルが組み込めることは明らか
Parameter estimation for mixture moels
- Unidentifiability
- Computing a MAP estimate is non-convex
The EM algorithm
EMはそれなりに知っているので流し読み程度で.
Model selection for latent variable models
Fitting models with missing data
コメント
だいたい章の最初は読んでるけど後半は読めてない気がする.2週目に期待.あと寿司たべたい.
MLaPP アドベントカレンダー10日目:Ch.10 Directed graphical models
ということで10日目ですが,そろそろ力尽きそうな感じでDirected graphical modelです.この章のポイントがどこにあるのか,ざっと読んだだけでは理解しきれていません.当たり前のことが書いてあるような,重要なことが書いてあるような….細かい部分については2週目に持ち越しですかね….とりあえず11日目に繋ぐことだけを意識!(本末転倒とも言う)
Introduction
-
- 同時確率分布をどうコンパクトに表現するか?
- Chain rule
- K個の状態があるときののテーブルで表現できる
- このTをstochastic matrixという
- 同様にの三次元テーブルをconditional probability tables (CPTS)という
- 各CPTの代わりにもっと節約的な方法としてconditional probability distribution (CPS)がある
- Conditional independence
- 大きな同時確率分布を効率的に表現するためにCIを仮定する
- これは(一次)マルコフ仮定といい,チェインルールを用いると
- これをマルコフ連鎖といい,は状態推移行列という
- Graphical models
- CIを仮定することで同時確率分布を表現できる
- グラフのノードが確率変数,エッジ(がない部分)がCIを表す
- Graph terminology
- グラフ表現時の用語説明
- Directed graphical model
- DGMはDAG(directed acyclic graph)で表現されるモデル
- Bayesian networkという名で知られる(ただしここでのBayesianに本質的な意味はない)
- これらはbelief networkとも呼ばれるし,causal networkとも呼ばれる
- DAGの特徴はこの前に親が来るという順序でノードが並んでいること
- これはトポロジカルオーダーと呼ばれる
- この順序のもとではノードは直前の親にのみ依存するというordered Markov propertyが定義できる
Examples
- Naive Bayes classifer
- Markov and hidden Markov model
- Medical diagnosis
- Genetic linkage analysis
- Directed Gaussian graphical model
Inference
-
- 同時確率の主な利用法は確率的推論
- 推論問題は既知としてがわかっていて
- 観測変数x_v, 隠れ変数x_hとして
Learning
-
- 学習はデータが与えられたときのパラメータのMAP推定
- Plate notation
- Learning from complete data
- Learning with missing and/or latent variables
Conditional independence properties of DGMs
- d-separation and the Bayes Ball algorithm (global Markov properties)
- Other Markov properties of DGMs
- Markov blanket and full conditionals
Influence (decision) diagrams
コメント
ただの目次の羅列やんけというのはやめましょう…凹みます.
MLaPP アドベントカレンダー9日目:Ch.9 Generalized linear models and the exponential family
本日は指数型分布族に関する章で,指数型分布族とはなんぞ その3のような感じです(その1, その2).任意の指数型分布族のメンバーは生成分類器をつくるためのクラス条件付き確率密度として簡単に用いることができます.また,反応変数yが指数型分布族分布となるような識別モデルとして,一般化線形モデル(Generalized linear models; GLM)と呼ばれるモデルクラスを考えることができます.
The exponential family
-
- 指数型分布族が重要な理由
- ある正則性条件の下で指数型分布族は有限サイズの十分統計量をもつ唯一の分布族.これはデータを情報損失なくある固定されたサイズに要約できることを意味し,online learningで特に重要
- 指数型分布族は共役事前分布をもつ唯一の分布族
- 指数型分布族はuser-chosen constraintに従う仮定が最小となる分布族(see Sec 9.2.6)
- 指数型分布族はGLMのコア(see Sec 9.3)
- 指数型分布族は変分推論のコア(see Sec 21.2)
- 指数型分布族が重要な理由
- Definition
- : natural parameter or canonical parameter
- : sufficient statistics
- : partition function
- : log partition function or cumulant function
- : scaling constant (たいてい1)
- もしならnatural exponential family
- 指数型分布族は一般的に次のように書ける
- はパラメータをcanonical parameter へ写像する関数
- もし ならcurved exponential familyと呼ばれ,パラメータ数よりも多い十分統計量を持つ
- ならモデルはcanonical formと呼ばれる
- Log partition function
- 指数型分布族の重要な性質はlog partition functionの微分が十分統計量のキュムラントを生成するのに使えること
- そのため,はキュムラント関数と呼ばれることもある
- MLE for the exponential family
- 指数型分布族の尤度は
- Pitman-Koopman-Darmois theorem
- ある正則性条件の下で指数型分布族は有限の十分統計量をもつ唯一の分布族である
- canonical exponential family modelの最尤推定値の計算法
- N個のiid data point
- 対数尤度は
- ここではに対して凸なのではについて線形であり,対数尤度は凸
- これを最大化するためにlog partition functionの微分は十分統計量ベクトルの期待値であることを用いて
- 十分統計量の経験平均はモデルの理論的期待十分統計量と一致しなければならないので
- はを満たす
- これはmoment matchingと呼ばれる
- Bayes for the exponential family
- Maximum entropy derivation of the exponential family
Generalized linear models (GLMs)
-
- 線形回帰やロジスティック回帰はGLMの一つの例(McCullagh and Nelder 1989)
- これらは出力密度がexponential familyであり,その平均パラメータがロジスティック関数のような非線形関数を通して,入力の線形結合で表されるモデル
- Basics
- GLM理解のために次のモデルを考える
- : dispersion parameter
- : natural parameter
- : partition function
- : normalized constant
- たとえばロジスティック回帰でははlog-odd ratio
- mean parameterからnatural parameterに変換するために関数を用いる.つまり,
- この関数は指数型分布族の分布の形状から1つに決まる
- これは逆写像であり,
- Sec 9.2.3でやったように,平均はpartition functionの微分で与えられるので
- まず,inputの線形関数を定義する
- 分布の平均はこの線形結合の可逆単調関数
- この関数はmean functionとして知られており
- mean functionの逆関数g()はlink functionと呼ばれる
- たとえばロジスティック回帰では
- link functionの特にシンプルなものはをもちいるものでこれはcanonical link functionと呼ばれる
- モデルは
- Sec 9.2.3の結果を用いると,response variabkeの平均,分散は
-
- 線形回帰
- binomial regression
- poisson regression
- 線形回帰
- リンク関数
Name | Formula |
---|---|
Logistic | |
Probit | |
Log-log | |
Complementary log-log |
Probit regression
-
- ロジスティック回帰の代わりにとなる標準正規分布を用いる
- ロジスティック回帰と似ているが柔軟なモデルがつくれるなど,いくつかの利点がある
- ML/MAP estimation using gradient-based optimization
- Latent variable interpretation
- Random utility model (McFadden 1974, Train 2009)が引用されており,研究分野の地続き感が感じられ感慨深い
- Ordinal probit regression
- Multinomial probit models
Multi-task learning
-
- あるグループにはデータが大量にあるが,別のグループではそうではないときに,
- それぞれモデルをつくってfitさせるのは難しいのでモデルパラメータをグループ間で共通にしてしまう考え方
- ML分野では
- multi-task learning (Caruana 1998)
- transfer learnint (Raina et al. 2005)
- learning to learn (Thrun and Pratt 1997)
- 統計学では
- hierarchical Bayesian models (Bakker and Heskes 2003)~
- などと呼ばれる
- Hierarchical Bayes for multi-task learning
- Application to personalized email spam filtering
- Application to domain adaptation
Generalized linear mixed models
- Example: semi-parametric GLMMs for modical data
- Comuputational issues
Learning to rank
- The pointwise approach
- The pairwise approach
- The listwise approach
- Loss functions for ranking
コメント
そろそろ詰みそう.今週はスケジュール的にきついー.
MLaPP アドベントカレンダー8日目:Ch.8 Logistic regression
ロジスティック回帰の章まできました.このあたりは自分は結構よく知っていることもあり(読む時間もないし…),まとめ方は雑になってます.多くの本では,ロジスティック回帰の説明がなされている章で大抵ロジスティック回帰そのものよりも非線形最適化の話に注力されていることが多いのですが,この本も例外ではなく,ロジスティック回帰のパラメータ推定のための方法論に多くの内容が割かれています.この手のモデルのパラメータ推定をしようとしていてHessianがお亡くなりになった経験がある方は多いと思うのですが,その手の詳しい人は特に読む必要はない印象です.むしろ次の章の一般化線形モデルの章の方が多くのモデルの関係性が記述されているので,そちらの方が見通しがよくなると思います.
Introduction
-
- この章は識別モデルのアプローチ
- 生成モデルと比較して直接的にをモデル化
Model specification
Model fitting
- MLE
- Steepest descent
- Newton's method
- second order optimization methodの筆頭
- Quasi-Newton methods
- Hの計算コスト超高い
- 各ステップの勾配ベクトルから情報を集めてHessianを近似
- 最も一般的なのはBFGS法
- BFGSはHessianの"diagonal plus low-rank"近似
- メモリを食うのでlimited memory BFGS (L-BFGS)もあるよ
- Multi-class logistic regression
- maximum entropy classifierやconditional logit modelとも(いわゆるロジット)
- Bayesian logistic regression
Online learning and stochastic optimization
- Online learning and regret minimization
- Stochastic optimization and risk minimization
- The LMS algorithm
- The perceptron algorithm
- A Bayesian view
Generative vs discriminative classifier
-
- GDAの事後分布はロジスティック回帰と同じ形をしている
- しかし,GDAによる仮定はロジスティック回帰よりも強い
- これらのモデル間の違いは訓練の仕方にある
- 識別モデルではたいていconditional log likelihood を最大化
- 生成モデルではjoint log likelihood を最大化
- これらは一般的に異なる結果になる
- GDAによる正規分布の仮定が正しいなら,ロジスティック回帰よりも少ないデータで良い性能を出すが,逆も然り (Ng and Jordan 2002)
- Pros and cons of each approach
-
- Easy to fit
- 生成分類器の方が簡単.ロジスティック回帰は凸最適化問題を解く必要あり
- Fit classes separately?
- 生成分類器では各クラスの条件付き確率密度を独立に推定.そのためクラスを増やしても再計算が必要ない.識別モデルではすべてのパラメータが相互依存しているので,クラスを増やしたら再計算
- Handle missing features easily?
- 生成分類器ではSec 8.6.2の方法でシンプルに扱える.識別モデルでは良い方法がない
- Can handle unlabeled training data?
- これはsemi-supervised learning(半教師あり学習)で関心のあるトピック.生成モデルでは取り扱いやすいが識別モデルでは難しい
- Symmetric in inputs and outputs?
- 生成モデルを逆向きに走らせるとp(x|y)を計算できる.識別モデルは入力データを生成できない.
- Can handle feature preprocessing?
- 識別モデルの大きな利点は任意の形で入力を前処理できる.たとえばxの代わりにを用いるなど.生成モデルではこういうことは難しい
- Well-calibrated probabilities?
- naive Bayesのような生成モデルは強い独立性を仮定しているため,しばしばキャリブレートが難しい.識別モデルはうまくやりやすい
- 重要なのはあなたの”道具箱”に両方入れておくこと
- Easy to fit
-
Model | Classif/regr | Gen/Discr | Param/Non | Section |
---|---|---|---|---|
Discriminant analysis | Classif | Gen | Param | Sec 4.2.2, 4.2.4 |
Naive Bayes classifer | Classif | Gen | Param | Sec 3.5, 3.5.1.2 |
Tree-augmented Naive Bayes classifer | Classif | Gen | Param | Sec 10.2.1 |
Linear regression | Regr | Discrim | Param | Sec 1.4.5, 7.3, 7.6 |
Logistic regression | Classif | Discrim | Param | Sec 1.4.6, 8.3.4, 8.4.3, 21.8.1.1 |
Sparse linear/logistic regression | Both | Discrim | Param | Ch 13 |
Mixture of experts | Both | Discrim | Param | Sec 11.2.4 |
Multiayer perceptron (MLP)/ Neural network | Both | Discrim | Param | Ch 16 |
Conditional random field (CRF) | Classif | Discrim | Param | Sec 19.6 |
K nearest neighbor classifier | Classif | Gen | Non | Sec 14.2, 14.7.3 |
(Infinite) Mixture Discriminant analysis | Classif | Gen | Non | Sec 14.7.3 |
Classification and regression trees (CART) | Both | Discrim | Non | Sec 16.2 |
Boosted model | Both | Discrim | Non | Sec 16.4 |
Sparse kernelized lin/log reg (SKLR) | Both | Discrim | Non | Sec 14.3.2 |
Relevance vector machine (RVM) | Both | Discrim | Non | Sec 14.3.2 |
Support vector machine (SVM) | Both | Discrim | Non | Sec 14.5 |
Gaussian processes (GP) | Both | Discrim | Non | Ch 15 |
Smoothing splines | Regr | Discrim | Non | Sec 15.4.6 |
- Dealing with missing data
- Fisher's linear discriminant analysis (FLDA)
MLaPP アドベントカレンダー7日目:Ch.7 Linear regression
なんとか7日目を迎えることができました.1週間というのは長いものです.しかし,これでまだ1/4の章.しかも簡単な部類の章ばかりなので,MLaPPこわい.ということで線形回帰の章です.
Model specification
Maximum likelihood estimation (least squares)
-
- 一般にMLEを計算することでパラメータを推定する
- 訓練データはi.i.d.と仮定しているので対数尤度は
- 対数尤度最大化は負の対数尤度最小化であり,
- ここで,RSSはresidual sum of squaresを意味し,
- これをNで割るとmean squared error (MSE)となるので,これを最小にするため最小二乗誤差を呼ばれる
Robust linear regression
-
- 以上のように,のガウス分布を用いて回帰モデルの誤差を表現するのが一般的
- そのときMLEは二乗誤差
- しかし,データに外れ値があるとき,フィッティングが悪くなる
- その理由として二乗誤差は二次式のペナルティなので,回帰直線から離れた点は近い点よりも大きな影響を与えるからである
- 外れ値に対するロバスト性を達成する方法としてガウス分布の代わりに裾の広い分布(たとえばラプラス分布)を用いる
- ラプラス分布を用いると尤度は
- 簡単のためbを固定するとの代わりにを用いている
- NLLは
- これは非線形目的関数なので最適化は結構難しいため,split variable trickを用いる
- s.t.
- これはLPで解ける
- 別の方法としてHuber loss関数を最小化(Huber 1964)
- これはより誤差が小さいときと等価であり,大きいときはと等価
- このロス関数のメリットはどこでも微分可能
Ridge regression
- Basic idea
- は事前分布の強さ
- MAP推定問題は
- 第一項はMLE,第二項は二乗ノルムのペナルティ項
- これがリッジ回帰 or penalized least squaresと呼ばれる
- Numerically stable computation
- のリッジ回帰はの回帰より統計的性質が良いだけでなく,数値計算上も良い性質がある
- Connection with PCA
- リッジ回帰とPCAの興味深い関係
- PCAの章を読んでから戻ってこよう
- Regularization effects of big data
Bayesian linear regression
コメント
日常業務でピキピキしながらも隙間時間と夜中にMLaPPを読む日々.多くの業種でもそうだと思いますが,年末〜年度末はいろいろ嫌なことがおおいものです….