Hatena::ブログ(Diary)

Fire and Motion

2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |

2014-09-06

すべてがMFになる

すべてがFになる,映像化するみたいですね.犀川創平も西之園萌絵も配役がイメージと違って一部で話題になっていました.さて,最近テンソル分解を使った論文をよく見かけるのですが,いまだにきちんと整理できずにいます.テンソルかわいいよ,テンソル

f:id:harapon1012:20140906183806j:image

そこで,まずは行列分解(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は

f:id:harapon1012:20140906195719j:image:w450

のように分解(近似)できます.Σは特異値を上から順にk個とって対角行列にしたものです.SVDは多くの分野で使われているものの,行列のサイズが大きくなったときには計算コストが大きくなります.

主成分分析

主成分分析は古典的な多変量解析手法ですが,やっていることはSVDと同じです.主成分分析における主成分と因子負荷量はSVDで分解した行列を用いると以下のように表すことができます.

f:id:harapon1012:20140906201345j:image:w450

そのため,左特異ベクトルと特異値の積が各主成分になっていて,右特異ベクトルがそれぞれの因子負荷量になっているという関係なのですね.

CUR分解 or CMD

2009年のid:mamorukさんのエントリではCUR分解と呼ばれています.(簡単に調べてみたけど)特に日本語での呼び名はないっぽいです.

CURやCMDのモチベーションはSVDによる分解では,大規模だがスパースな行列Xをに分解したときに,が密行列になってしまうという問題を防ぎたいというものです.もちろんこれが問題かどうかはタスク依存だと思いますが,解釈しやすさなどを考えるとが疎行列になると嬉しい訳です.また,元行列がスパース行列なので,そのスパース性を失うのももったいないというモチベーションがあります.

そこで,SVDでは密行列だったに対し,元のスパース行列からサンプリングしてをつくり,行列近似を行うというのがCUR分解のイメージです.

f:id:harapon1012:20140906230042j:image:w450

提案論文では一様分布からサンプリングをしていて,その後もう少し賢いサンプリング法(CMD)が考えられています.サンプリングするだけでいいの!というのは驚きですが,元行列がスパースな場合,よくよく考えてみるとPCA(SVD)がやっているorthogonal projectionとサンプリングがほぼほぼ変わらないというのは直感的には真であると思います.

NMF

非負値行列因子分解(NMF)も結構いろんなところで見かける行列分解手法で,非負行列Xが与えられたときに,のように二つの行列の積に分解します.その名の通り,分解した行列U, Vがそれぞれ非負のため,解釈しやすい,現象論的に負の値を取らない現象を表現できる,ということがウリです.

f:id:harapon1012:20140906231035j:image:w450

主成分分析(やSVD)では独立性が仮定されていたのに対し,NMFでは非負性を用いることで,独立性を仮定することなく行列分解を可能としています.

近似の評価尺度としては,XとUVのフロベニウスノルムの最小化,

一般化KLダイバージェンスの最小化

などが利用されるようです.

以前,持橋先生の資料でLDAで得られたトピック行列と混合比行列は正規化するとNMFと同じことをしているという内容があったように記憶しています.

まとめ

というわけで,非常に簡単ですが,SVD, CUR, NMFあたりを大雑把にまとめてみました.詳細は各手法の理論背景,計算方法,実装等を眺めるのが良いと思いますが,簡単なプレビューとしてお役に立てばと思います.

PFIの比戸さんが昨年まとめられているKDD2013のbest paperのmatrix sketchは行列分解ではないですが,ある巨大な行列を小さな行列に圧縮するという方法でたぶん似たような考えの方法ではないかと思います(未読).行列分解や次元削減の界隈は圧縮センシング等のスパース性を設計原理としたモデリングにも通ずる発想ですよね.というわけで,そろそろテンソル理解したい.誰かおせーて.

参考

2014-07-02

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

あたりです.自分の興味の偏りがわかりますね:-)

2013-12-11

MLaPP アドベントカレンダー11日目:Ch.11 Mixture models and the EM algorithm

この章は混合モデルとEMアルゴリズムについて.前半の混合モデルについてはちゃんと読めたけど,EMについてはそんなに詳しく読めていないし,知っているところも多かったのでだいぶ飛ばしてしまった.混合モデル周辺はこれまでそんなに触ったことがないので,実装して挙動はきちんと確かめたいと思います.

Latent variable models

    • グラフィカルモデルは2変数間の依存関係をエッジで表現するので高次元
    • 別のアプローチとして観測変数は共通の隠れ要因から生まれているので相関があるという考え方
    • これがLatent variable model
    • このモデルは潜在変数のないモデルよりフィットが難しいが2つの理由で重要な利点がある

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つのアプリケーション
      • black-box density model
        • 各クラス条件付き確率を混合分布にすることでデータ圧縮,異常値検知,生成分類器などに有用
      • clustering
        • 基本アイデアはシンプル.まず混合分布にfitさせる.次にを計算
        • これは点iがクラスターkに属する事後確率を表す
        • クラスターkの点iに対するresonsibilityとして式(11.6)で計算
        • このプロセスはsoft clusteringと呼ばれ,生成分類器で用いられる計算と同じ
        • を用いてクラスター割当の不確実性も表現できる
        • これが小さければ,MAP推定を用いてhard clusteringを計算するのが合理的
  • 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週目に期待.あと寿司たべたい.

2013-12-10

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

  • 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

コメント

ただの目次の羅列やんけというのはやめましょう…凹みます.

2013-12-09

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)

  • 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
    • リンク関数
NameFormula
Logistic
Probit
Log-log
Complementary log-log
  • ML and MAP estimation
    • GLMの良い性質の一つとしてロジスティック回帰と同じ方法で推定が行える
    • 特にlog likelihoodが次の形をしているとき
    • チェインルールを用いて勾配ベクトルを計算可能
    • もしcanonical linkを用いると
    • non-canonical linkであっても実際のHessianの代わりにHessianの期待値(フィッシャー情報行列)を用いることができる
    • これをFisher scoring methodという

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

コメント

そろそろ詰みそう.今週はスケジュール的にきついー.