しましま/DMSS2009

The 4th International Workshop on Data-Mining and Statistical Science (DMSS2009) †

このページはしましまがThe 4th International Workshop on Data-Mining and Statistical Science (DMSS2009) に参加してとったメモです．私の主観や勘違いが含まれていたり，私が全く分かってなかったりしていますので，その点を注意してご覧ください．誤りがあれば，指摘してください．

7月7日 †

DMSS: Session 1 †

Efficient Exploration through Active Learning for Value Function Approximation in Reinforcement Learning †

Takayuki Akiyama, Hirotaka Hachiya, and Masashi Sugiyama (Tokyo Institute of Technology)

• 強化学習の枠組みで，現在の政策とは異なる政策の下で収集されたサンプルから学習するため，共変量シフトの重要度重み付けを採用．

Visual Inspection of Precision Instruments by Least-Squares Outlier Detection †

Masafumi Takimoto, Masakazu Matsugu (Canon), and Masashi Sugiyama (Tokyo Institute of Technology)

• 画像処理を用いた製品検査：不良事例は非常に少なく，その率も短期間に変化
• 通常分布からのはずれ値を不良と見なす → テスト密度の通常分布に対する比で判定
  • この比を，線形モデルで記述して，2乗誤差を最小化することで直接推定する
• Gaborフィルタとピラミッド法の組み合わせで画像から特徴抽出

Extracting Phases of Financial Markets †

Teruko Takada (Osaka City University)

• 金融の時系列データからの層転移の検出
• [Breiman+,1977]の適応的カーネル密度推定，fat-tailにも強い
• 系列変化の，分散でリスクを，リターンを平均値で評価

Invited Talk: Recent Topics on BDDs/ZDDs for Data Mining and Knowledge Discovery †

Shin-ichi Minato (Hokkaido University)

• BDD：出力が同じノードを併合，0/1が同じところに行っていたらまとめるという操作で縮約
  • 変数の順序を決めるとBDDは一意に決まるが，その大きさはその順序に依存
  • 0/1 を出力する関数によって，1になる組み合わせ変数によってのアイテム集合を表現
• ZDD (zero-surpress BDD)：縮約のルールが，0/1出力が同じノードになっている場合ではなく，1ノードが直接0を指すときに省略
  • 無関係なノードが自動的に省略，疎なデータに対して有効
• ZDDによる頻出アイテム集合の抽出
  • 各アイテム集合の頻度を2進数で表し，2進数の全てのビットを一つのZDDで表現 → 一定以上の頻度のアイテム集合を見つける ZDD-grouth アルゴリズム
  • 深さ優先型のアルゴリズムで効率化を図ったのが LCM

DMSS: Session 3 †

Dimensionality Reduction for Density Ratio Estimation in High-dimensional Spaces †

Masashi Sugiyama (Tokyo Institute of Technology), Motoaki Kawanabe (Fraunhofer Institute FIRST), and Pui Ling Chui (Tokyo Institute of Technology)

• 密度比を線形モデルで直接推定するときに，次元削減もする
  • 次元削減は，局所性を反映させた局所Fisher判別分析(LFDA)を使う
  • 削減後の次元数決定にLOO交差確認を使う

Sufficient Dimension Reduction via Squared-loss Mutual Information Estimation †

Taiji Suzuki (University of Tokyo) and Masashi Sugiyama (Tokyo Institute of Technology)

• Squared loss mutual information

  Is(Y,Z)＝[1/2] ∫ [ {p_yz(y,z) / py(y)pz(z) } - 1 ]^2 dpy dpz

  • 比になってるところを線形モデルで密度推定
• 次元削減も同時に行う反復法も提案

7月9日 †

DMSS: Session 4 †

Identification of an Exogenous Variable in a Linear non-Gaussian Structural Equation Model †

Shohei Shimizu (Osaka University), Aapo Hyvarinen (University of Helsinki), Yoshinobu Kawahara (Tokyo Institute of Technology), and Takashi Washio (Osaka University)

• 因果分析の仮定：データの生成過程はSEMモデル（因果関係が有向非循環で，変数はガウス分布に従う）
  • 線形モデル+ガウスノイズだと x1→x2 と x2→x1 が両方出てくる場合がある．
  • 非ガウスにしたのが LiNGAM モデルでこの問題に対処
  • 観測変数 x をより前の原因になるように並び替えると対角0の下三角行列 B を使って x＝B x + <ノイズ> の形に書ける
  • 他の変数の影響を受けず，ノイズ項だけを入力とする変数を exogenous という
  • 観測データから，変数の順序とBを求めるのが目標
• ICA：非ガウス入力からもとの信号を求める x＝W^{-1} e
• x＝(I-B)^{-1} e と書き換えると I-B を W とみなしてICAで解ける
  • 求めた W を置換行列 P，スケーリング D を用いて P D (I - B) の形にBが下三角行列の制約を満たすようにする
  • ICAの局所解の問題と，置換行列を求める計算量の問題
• 外部因子のみに依存する exogenous 変数を順番に見つけていくアルゴリズムの提案
  • 線形回帰したときの残差と，回帰の目的変数の独立性から，ノイズのみに依存するexogenous 変数を見つけ出す．

Maximum Likelihood Estimation for Failed-Link Detection in Communication Networks †

Shohei Hido (Kyoto University, IBM Research) and Yutaka Takahashi (Kyoto University)

• 通信ネットワーク中のリンクに故障がある．ネットワークのリンクには冗長性があったり，端末の追加／削除があったり，トポロジーが変化する．トポロジーは観測できない．このとき，どこが切れたか見つける．
• probe パケットで，ターミナル間の経路の遅延時間が分かる．以前の遅延データと比べて故障箇所を見つけ出す．
  • 最速経路が，以前より遅くなっていたら故障が考えられる．
  • 遅延時間の揺らぎをガウス分布にして，MAP推定をする

Gaussian Mixture Models and VC Dimensions †

Yohji Akama (Tohoku University)

• データ面と平面の間の距離の2乗和で測るPCAの損失や，d次元データに対する多次元ガウス分布を損失
- 損失関数を一つのしきい値で切ることで，二つのクラスに分けたときのVC次元を考える
• PCAのVC次元は，ガウス分布のVC次元の下限を決めることなどから，ガウス分布のVC次元のオーダーを求める
• さらに，N要素の混合ガウス分布はそのN倍が下限となると主張

Invited Talk: 小売マーケティング分野でのデータマイニング †

Katsutoshi Yada (Kansai University)

10年前

• 相関ルール：野菜ジュースは健康志向の高い人が飲む → 野菜と野菜ジュースを並べておく関連販売(corss-marchandise) → 実験群が有意によかった
• DBはRDB，データ収集は受動的 → 発見科学とアクティブマイニングのプロジェクトで変える

5〜6年前

• アクティブマイニング：能動的データ収集，顧客中心
• 購買商品の系列をグラフで表し，グラフマイニングを適用
• ビール販売のケーススタディ：野菜や鮮魚売り場でクールケースをおいてビールを販売 → 販促をしたのでビールの販売量は当然増えるが，それに加え，鮮魚，野菜も販売は増加，しかし，精肉では変化はなかった
• 遺伝子分析手法を系列データに適用
  • 回数券クーポン：ビールのブランドロイヤリティには3回連続購入が必要で，ビールの1週間の購入周期を利用し，1ヶ月有効な回数券クーポンを作成．
  • カップラーメン市場で新製品のしめる割合は大きく，数ヶ月後に生き残る商品は少ない．

現状

• データ数の大規模化(小規模地方ストアでも100GB/年，0.5Gレコード，最低2年分は分析する必要)
• 時系列（POS，クリックストリーム，センサーデータ）
• 高次元データ（広告を見た，センサー情報）

系列データ

• RFIDでショッピングカートの移動を追跡
  • 移動と停滞を繰り返す
  • 単純な軌跡の顧客は希で，いったり来たりの往復を繰り返す顧客が通常
  • 購入量の多い顧客と，少ない顧客での，行動系列パターンの違い
    • 前者の方が寄り道が多い

• TVや広告などの広告の刺激は重要

• MUSASHI: http://musashi.sourceforge.jp
• DMLab: http://www2.ipcku.kansai-u.ac.jp/~yada/DSI/english/index.html

DMSS: Session 6 †

Monolithic and Partial Compilation Methods for Probabilistic Inference of Bayesian Networks using ZBDDs †

Daisuke Tokoro, Kiyoharu Hamaguchi, Toshinobu Kashiwabara (Osaka University), and Shin-ichi Minato (Hokkaido University)

• ベイジアンネットをZDDで表現する
  • 各変数が有効かどうかを示す指示変数と，BNのCPT中の値でBNを表現する multi linear function を利用するのがカギ

Pattern Discovery from a Single Graph with Quantitative Itemsets †

Yuuki Miyoshi, Tomonobu Ozaki, and Takenao Ohkawa (Kobe University)

• ノードが定量的な特徴で記述された大きなグラフあ一つある．この中から，頻出する部分グラフパターンを見つける
• QFMinerとgSpanの組み合わせ

Mining Frequent Patterns from Linear Graphs †

Yasuo Tabei, Daisuke Okanohara (University of Tokyo), and Koji Tsuda (National Institute of Advanced Industrial Science and Technology)

• グラフの集合から，これらのグラフに頻出する部分グラフパターンを見つける
  • ノードに順序がある線形グラフを扱う．非連結になってもOK．
• LGM (Linear Graph Miner)：深さ優先で頻出パターンを列挙する
  • 遺伝子の三次元構造データや，係り受け解析を使ったsentiment分類に適用