研究室‎ > ‎卒業生のみなさまへ‎ > ‎真嘉比 愛‎ > ‎文献紹介‎ > ‎NLP2012‎ > ‎

ネットワークと機械学習

 著者 鹿島 久嗣
 タイトル ネットワークと機械学習 〜標準タスクと基本モデル〜
 学会 言語処理学会 第18回 年次大会 チュートリアル T-c
 ページ pp. 53 - 65
 日付 2012.3.13
 URL http://www.geocities.jp/kashi_pong/publication/NLP12_network_kashima.pdf ※発表資料最新版
 http://goo.gl/H1O7Q ※発表スライド

ネットワーク構造をもつデータ
 = グラフ(木,配列)によって表現されるデータ

ネットワーク構造を持ったデータを扱う機械学習問題を,
 {内部,外部}ネットワーク × {ノード,リンク}推論
 ※ネットワーク構造の種類 × 解析のフォーカス
の4通りに分類
  • 内部ネットワーク:注目するデータ単位の内側にあるネットワーク
    • 文書分類:文書に注目すると文書は内部に配列構造をもったデータ
    • 構文解析:文に注目すると,文は内部に木構造をもったデータ
    • 活性予測:化合物に注目すると,化合物は内部にグラフ構造をもったデータ
  • 外部ネットワーク:注目するデータ単位の外側にあるネットワーク
    • 友人推薦:人に注目すると,ソーシャルネットワークは外部にグラフ構造をもったデータ
    • 系統樹推定:遺伝子に注目すると,系統樹は外部に木構造をもったデータ
    • 推薦システム:顧客と承認に注目すると,購買データは外部に2部グラフ構造をもったデータ
  • 個々のデータの性質に興味がある(ノード推論)
  • データ内外の関係について興味がある(リンク推論)

内部ネットワークを持つデータの解析:
 個々のデータにフォーカス → それぞれのデータのもつ性質に興味がある:
  グラフ分類問題,グラフクラスタリング
  線形識別モデル
   パタンマイニング法(重要なパタンのみについて考える)
    → 重要とは?……頻度や(目標の出力との)相関
   カーネル法(類似度ベースのモデル)
    → カーネル関数をどう設計するかが肝(「共通部品をどのくらい持っているか」を類似度の指標にする)
 データ内外の関係にフォーカス → パタン発見や構造予測:
  構造予測問題の難しいところ:モデルの出力候補が指数的に多い
   条件付き確率場(CRF),構造化パーセプトロン,構造化SVM
   入力と出力の組に対する予測とすることで,線形識別モデルに帰着

外部ネットワークを持つデータの解析:
 ノード分類問題 ↓ 両者はトレードオフ!
  「隣同士は似ている」をもとにノード分類問題を解く
   → 最適化問題として定式化
  「隣同士は似ている」とは限らない場合のモデル
   → マルコフネットワーク(より一般的なモデル)
 リンク予測
  つながり推薦や購買予測など
  リンク指標(2つのノード間のリンクの張られやすさ)
   → 2つのノードが共通にもつ隣接ノードの数
   → 友達の多い人はより友達を持っている
  ペアワイズ予測(2つのノードに対して素性ベクトルが与えられているとする.このときの組み合わせ素性を定義して考える)
   → リンク指標をparameterizeしたものとして考えられる.
     パラメータが多い……パラメータに制約,次元圧縮
     ランク制約は凸集合を与えない
      → 最適化問題を解く場合には嬉しくない
      → トレースノルム制約を使う場合が多い(凸集合を与える) ※多くの特異値が0になる(特異値のL1ノルム制約)
  マルコフネットワークはリンク予測にも適応可能
 潜在変数モデル
  前2つは局所的なノードに着目した手法 → もう少し大局的な情報を見る
  協調フィルタリングから潜在変数モデルに
   協調フィルタリング:
    初期の手法(GroupLens):自分と似た顧客のデータを用いて予測
    → 行列がフルランクではない
  確率的ブロックモデル
   離散的な潜在状態へ割り当て
    → 潜在状態の組み合わせに応じた確率を考える
   ・・・拡張
    混合メンバシップモデル
     リンクごとに潜在状態を生成
 ※今データマイニングの分野等で人気!!
 テンソル:多ノードの関係の表現(行列の多次元拡張)
  CP分解:コアテンソルが対角
   ランク・・・対角テンソルのサイズ
  Tucker分解:各モードの次元が異なる
   ランク・・・コアテンソルのサイズ
  → ソーシャルネットワーク分析,タグ推薦,Webリンク解析

Comments