The International Workshop on Data-Mining and Statistical Science (DMSS2007)

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

招待講演:Scale-free network priors in Bayesian inference with applications to bioinformatics

Paul Sheridan, Takeshi Kamimura, Hidetoshi Shimodaira

  • マイクロアレイデータ X:実験数×遺伝子数,要素は反応量の比の対数 log(実験群/対照群)
  • スケールフリーネットワーク:ノードの度数に対して,その頻度が指数的に分布
  • 遺伝子ネットワーク(反応のパターンの類似していれば辺ができるネットワーク)もその生成過程からスケールフリーになる
  • グラフ事前分布 p(G) と,遺伝子からの p(G|X) から p(X|G) を計算
  • SFネットの生成モデル
    • Poison-Barabasi-Albertモデル:ノードを一つずつ追加.新規ノードが既存ノードにリンクを張る確率は,ノードの度数 + 定数に比例
    • Promote growthモデル:ノードとそれに繋がった辺を複製.その後,辺の削除と,追加を行う.
    • Staticモデル:最初にノードは全部あり重みが割り当てられている.その重みを考慮しつつ辺を生成
  • MCMCで,これらのモデルを用いて p(G) や p(G|X) を計算する.

Bayesian data analysis for identification and estimation of the learning effects of pointing tasks

Koki Kyo

  • Hick-Hymanの法則:n種のランプが点灯する刺激に対して,それを人間が選択するのにかかる時間は α + β(1/n)
  • Fittの法則:二つの白黒の矩形を並べて,どちらかを選択場合も,A/W(それらの間の距離 A と,それぞれのものの幅 W)に関して同様の法則が知られる
  • Fittの実験で,実験条件を変えながら,複数の被験者について,複数回実行する拡張

Kullback-Leibler importance estimation procedure for covariate shift adaptation

Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul von Bunau, Motoaki Kawanabe

  • 共変量シフト:訓練とテストデータの分布はサンプリングの都合で違うが,入出力の関数関係は変わらない場合
  • テスト分布/訓練分布 の比で,エラー関数を重み付することで,テストデータに対してよいあてはめができるようにする.
  • さらに重みのきき具合を調整するパラメータを交差確認で決める拡張
  • 重みを,独立に求めたテスト/訓練分布の比ではなく,線形モデルKLダイバージェンスをエラーを測ってあてはめして決める.さらにモデル選択もする.

Prediction of protein-protein interactions and disease genes by machine learning

Thanh Phuong Nguyen, Tu Bao Ho

  • 遺伝病:一つの遺伝子が原因のものと,複数の遺伝子の複合的な影響でおきるもの
  • 複数の遺伝子の影響を,タンパク質の相互作用に基づいて,帰納論理プログラミング(ILP)と半教師あり学習(Semilという手法)で予測する

Mixed factors analysis: Unsupervized statistical discrimination with kernel feature extraction Ryo Yoshida, Tomoyuki Higuchi, Seiya Imoto, Satoru Miyano

招待講演:Statistical learning with graph kernels

Jean-Philippe Vert

  • 個々のグラフをクラスに分類する問題.
  • グラフを特徴量に変換して解くと …… 表現力と次元数の増大のトレードオフが悩ましい
  • グラフカーネル:ラベル付グラフの集合について定義
  • 完全なグラフカーネル:任意の同形でないカーネルを識別できる → 学習できない関数はなくなるが,実際に計算するのは無理 → 十分な表現力は保ちつつ計算も可能なカーネルが必要
  • 部分グラフカーネル:φH(G)=Gの部分グラフでラベルがHのものの数.
    K(G1,G2)=Σ{H∈XX} λH φH(G1) φH(G2)
    (XXは可能なグラフの集合)計算はNP困難.
  • パスグラフカーネル:任意の部分集合ではなく,パスだけを考える.計算はNP困難.
  • ウォーク:パスとにているが,途中で同じノードを通ってもよい
  • ウォークカーネル:SS_n:可能な,長さnのウォーク上のラベル系列の集合.ウォーク w と,ラベル系列 s,重み λw
    φs(G)=Σ{w∈W(G)} λw 1(sがwのラベル系列)
    カーネルは K(G1,G2)=Σ{s∈SS} φs(G1) φs(G2)
  • グラフ:二つのグラフについて,二つの頂点集合の直積の頂点集合をもち,両方のグラフで共に辺があるようなグラフ
    • 同じラベル系列の二つのウォークは,積グラフ上のウォークと全単射の関係
    • この積ブラフを使うと,ウォークカーネルは多項式時間で計算できるようになる.
  • ウォークカーネルの拡張
    • totteringウォーク:一歩進んで,同じところに戻るウォーク → 多くの場合,無視して良い
    • 部分木カーネル
  • Open-source kernels for chemoinformatics: http://chemcpp.sourceforge.net/

Online learning of approximate maximum margin classifiers with biases

Kosuke Ishibashi, Kohei Hatano, Masayuki Takeda

SVMのオンライン化

  • 既存手法の更新数のオーダ O(R^2/γ^2):γはマージンまで,Rは原点までの距離 → バイアスを導入する改良
  • 定義:(u,b):方向 uと原点からの距離で決まる超平面
  • 一般のオンライン学習:予測したラベルが新しい事例と違うときに超平面を更新
  • ROMMA:超平面のバイアスがなく,予測誤りがパラメータδを超えない場合は,更新をしない → 更新数はO( R^2 / [δ^2 γ^2] )
  • このROMMAにバイアス項を導入して予測精度を上げるROMMAbの提案

招待講演:maximum margin matrix factorization for collaborative ranking

Alexander J. Smola

協調順位付け

  • Netflixの協調フィルタリングのコンテストの問題:全アイテムで均一にエラーを評価 しているが,上位部分を重視すべき
  • 要求:目的関数,少なくとも凸上限を最適化,特徴量なしに推薦,特徴量があるときにそれを考慮する方法,並列化によるスケーラビリティの実現
  • 関連事項
    • 凸上限:順位損失の条件 NDCG@k directly via convex ranking bound
    • 低次元順位行列分解:Srebroらの特徴量行列分解 F=M U: Mはアイテム,Uは利用者
    • 特徴の考慮:F = M U + f_m・w_m + wu fu + f_mu・w_mu (ドットは要素ごとの積の和)
    • Bundle Method Solver:利用者上で並列化可能
  • 問題
    • 評価 Yij∈{1..5},i,jはアイテムと利用者
    • 目標:Fij のスコア a(π)^T b(y) によって順位付けする,順位付け損失 NDCG を最適化
      DCG@k(π,y)=Σi^k [ 2^yi - 1] / log[πi + 1]
      NDCG@k(π,y)=DCG@k(π,y) / DBG@k(argsort(y),y)
      yiはアイテムiの利用者の評価で,πは順列,πi はアイテムiの順位

順位付けの凸上限 (a convex upper bound for ranking)

  • DCG@kの最大化は凸でないことが多い
  • 代わりに,j について単調減少な cj を使い G(π,f)=Σj c_πj fj を,π*= argsort f について最大化する
  • Δ(y,π) 真の値と上限の差
  • 解き方方針のまとめ
    l(y,f)=max_π Δ(y,π) + G(π,f) - G(argsort y, f)
    この最適化は Linear Assignment Problemになる.
    • 累積上限 L(Y,F)=l(Y_i., F_.j)

低次元順位分解 (low rank factorization)

  • L(Y,MU)+λ(1/2)[‖U‖^2 + ‖M‖^2]を最小化するように F を M と U に分解
    • L(Y,MU)+λ(1/2)[‖U‖^2] と L(Y,MU)+λ(1/2)[‖M‖^2]の最適化を交互に反復して解く
  • 特徴の考慮:F = M U + f_m・w_m + wu fu + f_mu・w_mu
    fm,fu,fmuはアイテム,利用者,両者に依存した特徴

Bundle法による凸最適化

  • 目的関数に接する超平面を使う(?)
    Rt[w] = max{j≦t} <at,w>+bt≦Remp[w]
    at=∂w Remp[W_t-1] and bt=R_emp[W_t-1] - <at,w_t-1>
  • 手続き:重みwtの更新と,at & bt の更新を反復する

マーケティングにおけるストリームデータと文字列解析 (Stream data and string analysis in marketing)

Katsutoshi Yada

  • マーケティング:誰が,いつ,どこで,何を,いくらで買うかはかなりよそくできる
  • 場所については未開拓:売り場の場所の影響
  • cross-marchantize:関連商品を並べてうる → 不十分:顧客がそれを売っている場所をに行かなければ売れない
  • カートにRFIDを付けて顧客の行動データを取得:カートには顧客への情報提供画面もある.いれた商品もある程度特定できる.顧客はカードで一意に識別.
  • 九州のスーパーマーケットで2006年9月に実地実験
  • 直線的な行動をするのは珍しく,途中いったりきたりするパターンが多い
  • 1秒以上立ち止まった「立ち寄り」を中心にする
  • 立ち寄った売り場をシンボルで表し,それを時系列順に並べた系列に変換して解析
  • EBONSAI:系列をクラス分類する手法を適用 → 購入量の多い顧客かどうかを識別
  • 解釈可能な行動パターンは珍しい

カスケードモデルによる特徴的ルール導出:一般化と高速化 (Fast computation of generalized characteristic rules in the cascade model)

Yu Nakano, Takashi Okada

  • カスケードモデル:複数の相関ルールをまとめてラティスにする
  • 相関を Apriori ではなく,FP-Growth で抽出するようにした

遺伝子発現データからの接尾辞木に基づく疑似バイクラスタ抽出 (Extracting pseudo-biclusters from gene expression data based on suffix array)

Tetsuro Namba, Makoto Haraguchi, Yoshiaki Okubo

  • ホヤの発生段階:14時期の時系列のマイクロアレイデータ
  • 部分区間での挙動が類似した遺伝子をまとめたクラスタを作る
  • 反応量を離散化しシンボルで表す.一定期間のシンボル変化が同じ遺伝子群を抽出.
  • suffix treeの辺には,まさにこの情報が現れている

A game theoretical analysis of combining classifiers for multi-class classification problems

Yuichi Shiraishi, Kenji Fukumizu, Shiro Ikeda

2値識別器で多値識別を行う

  • 二つのクラスを識別する1対1と,あるクラスとそれ以外に分ける1対他が代表的
  • J個の識別結果をまとめる方法
  • ECOC (error correcting output code):そのクラスに最も適切なクラス識別結果ベクトルと,実際に出てきた識別結果ベクトルの距離をハミング距離で測って分類
  • ハミング距離を考える代わりに,予測結果と正しい答えの間も学習して決めた → 実験したらあまり結果はからわなかった
  • ECOCとこの学習による決定には何らかの関係がある → ゲーム理論に基づく解析
  • ゲーム理論で捉えると
    • 予測結果ベクトルに基づいて,意思決定者は,出力符号を決める確率分布を選択する
    • 環境側は,あるクラスである確率 Pr(y=i)と,予測結果の分布がどうなるかという条件付確率 Pr(f=u|y=i)=p_iu のパラメータを決める.ここで後者の確率はハミング距離が小さいと確率は大きくなる制約がある
    • minimaxになることが示せる条件や符号化の方法を示した

Multi-entity-topic models with who-entities and where-entities

Hitohiro Shiozaki, Koji Eguchi, Takenao Ohkawa

  • 文書と語が関係する状況の解析→トピックモデル(例:latent Dirichlet allocation (LDA))
  • さらにnamed-entityを扱えるようにする
    • SwitchLDA: topic内でのentityの割合を表す拡張
    • 提案手法:W2SwitchLDSは,誰とどこを表す2種類のentityを同時に扱えるように拡張

Fast PSD matrix estimation by column reductions

Hiroshi Kuwajima, Takashi Washio

Merging particle filterにおける重みの設定について (On weight setting for the merging particle filter)

Shin'ya Nakano, Genta Ueno, Kazuyuki Nakamura, Tomoyuki Higuchi

  • データ同化:シミュレーションモデルに,観測結果を取り込んでよりよいモデルにする
  • データが与えられたときに逐次的にモデルを修正する逐次データ同化には,アンサンブルカルマンフィルタや粒子フィルタが使われる
  • merging particle filter粒子フィルタで,N個のサンプルする代わりに,n×N個とりだし,n個の粒子をまとめて N個の粒子に戻す形で次世代のサンプルを作る

目的変数が範囲で与えられる回帰問題に対するEM法

Hisashi Kashima, Kazutaka Yamasaki, Hiroto Saigo, Akihiro Inokuchi

  • 回帰問題で,従属変数の訓練データが,値そのものではなく,下限と上限の組で与えられる.
  • アルゴリズム:次のステップを繰り返す
    • 現在の予測分布での,与えられた範囲での期待値を求める
    • この期待値を代表値として,モデルを更新する
  • 与えられた範囲にデータが入る確率を考え,積分ができないので,下界で置き換えた目的関数を考える.これについて最尤推定EMアルゴリズムで実行したものになっていることが示せる.

トップ   編集 凍結解除 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:15 (2494d)