しましま/DMSS2008

International Workshop on Data-Mining and Statistical Science (DMSS2008) †

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

September 25 †

Feasibility of Graph Sequence Mining based on Admissibility Constraints †

Akihiro Inokuchi and Takashi Washio (Osaka University, Japan)

• グラフの系列からのマイニング：系列中で，頂点・辺の増減や，頂点・辺のラベル変更が生じる．系列で隣接するグラフの変化は小さく，各グラフは疎．
• グラフの編集距離を考える．編集操作：頂点・辺×削除・追加・ラベル変更の6種
  • 系列中で隣接するグラフを，これらの編集操作の系列で補間．
  • 補間に使った操作をグループごとにまとめて，編集操作のグループの系列にすると，アイテムの系列のように扱える．
• この補間した編集操作系列の包含関係を定義．
  • PrefixSpan を利用して，系列パターンマイニング

Mining Maximal Tree Patterns with Subtree Constraint †

Nguyen Viet Anh, Koichiro Doi, and Akihiro Yamamoto (Kyoto University, Japan)

• 利用者が指定した部分木の制約を満たす頻出する極大木パターンを列挙する問題
  • 木は順序なし，ラベルあり．木の集合から，パターンを含むものの割合を頻度とする．
• 共通最小木を見つける代わりに，制約を満たす上位木を使う
  • 部分木を含む上位木のルートを見つけ，圧縮表現を作り，頻出するルートを探す
  • 見つけたルートに，データ中にある子ノードを加えたgrobal木を作る
  • grobal木から順に頻出でないノードを刈ることで，頻出極大木が生成できる．

On Feasibility of Graph Spectrum-based Frequent Sub-graph Mining †

Kouzou Ohara, Takashi Washio, and Duy Vinh Nguyen (Osaka University, Japan)

• チェックにNPかかる同型なグラフを同じと見なすのではなく，O(n^2)で計算できるグラフスペクトルが同じグラフを同じと考える co-spectrarity
  • グラフスペクトル：グラフのラプラス行列，incidenceグラフ(辺と頂点の二部グラフ)，lineグラフ(辺を要素とし，隣接性は共通頂点)などの固有値
  • 複数のグラフスペクトルの一致を見ることで，グラフの同型性に近づける
    • 線形グラフとlineグラフの組み合わせが良い
• この考えで，gSpan のような頻出部分グラフマイニングを行う

Discovery of Closed Hyperclique Patterns in a Sequence of Graphs †

Tomonobu Ozaki and Takenao Ohkawa (Kobe University, Japan)

• グラフの系列からのパターン抽出．hypercliqueでclosedなパターンを対象
• hyperclique
  • 通常の確信度ではなく，h-確信度が定義されている
  • 系列中で，支持度，とh-確信度が共に一定以上になる部分グラフを見つける

New Directions in Statistical Graph Mining (Invited) †

Koji Tsuda (Max Planck Institute for Biological Cybernetics, Germany)

• 生物学でのグラフ：DNA系列，RNA，化合物，テキスト
• 構造化: 分類や次元削減などの統計的手法をグラフに適用できるようにする
• パターンマイニング：部分集合，部分木，部分グラフなどの部分構造で表されるパターン
  • DB中での頻度，重み付頻度，評価関数の上位k
• 単純な構造化: 頻度マイニングでベクトルに変換したのち，通常の統計的手法を適用
  • 変換で情報を損失，パターン数が多すぎ，メモリの問題
• 漸次的な方法：統計的手法には反復的なものが多いので，反復中で徐々にパターンを見つけ，新たな特徴量として追加する．
  • gBoost
• カーネルの利用
• 構造化の世代：1G:AdaBoost, 2G:L1正則化+column generation, 3G:Krylov subspace methods → 以後3Gの手法

グラフマイニング

• 高頻度の部分グラフ抽出：gSpan (DFSコード)
• 識別：クラスごとに，頻度に大きな差のあるパターンを見つける
  • QSAR (quantitative structure activity relationship) 複数の化合物からactionを導く
• PLS (partial least squares regression)
  • 計画行列 X，Response y，重み行列 W，潜在要素 T=W X ：重みも決める反復的な回帰
  • パターン数が多いと途中で非常に高次元なベクトルになる

• グラフPCA：計画行列 X，グラム行列 A＝X X^T
• Lanczosアルゴリズム：T = Q^T A Q なる正規直交行列 Q を見つけ，T の固有ベクトル R から Q R で，A の固有ベクトルが計算できる原理．
  • 数値計算的には反復解法で，初期値の選び方は重要
• 構造化：Lanczos 法では，X の要素にアクセスする式は一つだけ．そこで，特徴量のなかから高頻度のパターンをまとめる(?)
• gPCA: 主成分によってパターンはいくつかの要素にまとめられる．各要素はグラフの異なる要素を表す．そのため，解釈が容易．

• iboost: http://www.kyb.mpg.de/bs/people/hiroto/iboost
• gboost: http://www.kyb.mpg.de/bs/people/nowozin/gboost
• pboost: http://www.kyb.mpg.de/bs/people/nowozin/pboost

Constrained Motif Discovery †

Yasser Mohammad and Toyoaki Nishida (Kyoto University, Japan)

• モチーフ発見：長さLの反復パターン発見．
  • 事前知識を反映した制約を導入．別の系列例で記述(?)
  • 基本CATアルゴリズム：部分系列を抽出し，近いペアを見つけ出す．
• 変化点検出
  • singular spectrum 変換して，PCAを使い，大きな変化を抽出 → さらに調整するパラメータ数を減らす

Using Product-of-Student-t for Label Propagation on Multiple Networks †

Tsuyoshi Kato (Ochanomizu University & AIST CBRC, Japan), Hisashi Kashima (IBM Research, Japan), and Masashi Sugiyama (Tokyo Institute of Technology, Japan)

• ラベル伝播アプローチ：ラベル伝播によって，未知のノードのラベルを予測する手法
• protain-protain interaction ネットが複数の与えられる．ノードには対応がある．
  • 未知のノードのラベルを予測したい．
  • ネットの重み付結合を考える
  • 既知のラベルの一致，隣接するノードの一致，安定化の三つの項をもつ目的関数を最適にするようにラベル付け

Privacy-preserving Data Mining and Machine Learning (Invited) †

Jun Sakuma (Tokyo Institute of Technology, Japan)

プライバシー保護データマイニング(PPDM)の基本概念

• PPDM
  • 各利用者が個人データ集合 XA XB を保持
  • データを共有することなく XA∪XB 上でマイニングして，その結果を共有
  • 例：個々の病院の患者のデータを公開せずに，疫学的な知見をえたい
• trusted third party：参加者のデータをまとめて扱って，処理する人
  • TTPなし + 普通のLANでPPDMはできるか？
• secure multiparty computation
  • Yao のプロトコル：互いの財産を明かさずに，どちらが多く持っているかを調べる
• PPDMの二つのアプローチ：ランダム化[Agrawal SIGMOD2000] と暗号化 [Lindel CRYPTO2000]
• SMC: 計算量が多い欠点，ランダム化：厳密な計算はできない+安全性は統計的，Crypto：計算量は中間的

分散環境でのプライバシー保護

• 外部にデータを出すときに，本当のデータと，それと区別のつかないシミュレータからのデータを出す．

secure function evaluation

• (yA, yB)←f(xA,xB)．それぞれの答えを，それぞれの利用者に返す
• homorphic public-key cryptosystem
  • 暗号化後のメッセージの積は，暗号化前のメッセージの和の暗号化に
  • m0を暗号化したもののm1乗は，m0とm1の積を暗号化したもの

PPDM for k-means

• 利用者のデータを店舗が預かり，店舗間では秘密を保つ server-centric
• サーバを使わず，ユーザ間の通信でのみ行う user-centric
• user-centric実現のため，P2Pネットワークを使う
  • 中心位置の更新は大域的な計算が必要．割り当ての変更は局所的な計算が可能
    • 大域的平均は，互いにとなりとの平均値を計算していくと計算できる
    • 中心位置を配って，各人が割り当てを判定

プライバシー保護強化学習

• 環境は共有，各利用者はそれぞれ，報酬を受ける．利用者間でも情報共有をするが，互いのデータは明かさない

Feature Extraction with Geometric Algebra for Semi-Supervised Learning of Time-Series Spatial Vector †

Minh Tuan Pham, Kanta Tachibana, Tomohiro Yoshikawa, and Takeshi Furuhashi (Nagoya University, Japan)

• 特徴の幾何的特徴を保持した特徴抽出をするのに geometric algebraを使う，四元数を利用

Feature Similarity: Geometrical Modeling and Discriminative Kernel Learning †

Canh Hao Nguyen and Tu Bao Ho (Japan Advanced Institute of Science and Technology, Japan)

• 直交ベクトルの線形和の内積で定義されるカーネル

September 26 †

Mining and Visualizing Local Dependence among Financial Data †

Teruko Takada (Osaka City University, Japan)

• 相互情報量： 点(x,y) についての p(x,y)/p(x)p(y) の p(x,y) についての期待値
  • カーネル密度推定やホワイトニングの導入
  • 密度推定で，分母 p(x)p(y) と p(x,y) の推定で，分母はshuffleし，分子はせずに推定することで，推定手法をそろえる．
• 相互情報量を全領域で平均をとるのではなく，グリッドに区切った各領域ごとに計算する．
• 二つの変量の依存性を可視化する

Algorithm for Computing Skyline ObjectSet on Numerical Databases †

Md. Anisuzzaman, Taufik Djatna, and Yasuhiko Morimoto (Hiroshima University, Japan)

• skyline: その点の値より小さな値を，全ての軸で，とりうるような他の点が，データ集合中に存在しない点の集合
  • 意志決定のとき選択候補となりうる点の集合になる
• 凸包を使ったアルゴリズムの提案

Forecast of Criminal Character by Text Mining of Suspicious Person Behavior Report †

Ariya Fujita (National Institute for Environmental Studies, Japan) and Shigeru Shimada (Advanced Institute of Industrial Technology, Japan)

• 犯罪の傾向を検出するのにテキストマイニングを利用
  • 警察署のWeb上のレポートが解析対象
  • BOWモデルで高頻度の語を検出したり，k-meansでクラスタリングしたり，地図上に表示したりする

Theoretical Explanation of the Boosting Algorithms (Invited) †

Liwei Wang (Peking University, China)

• Bosting: 容易に利用でき，過学習しにくいといわれている．

AdaBoost

• 指数損失を最小化

  Σ exp[ -yi f(xi) ]
  f(x)＝Σ αi xi，Σαi＝1

• マージン：y f(x), y∈{-1,+1}
  • 最小マージン： 訓練事例中で最小のマージン
  • margin distributed bound (Schapireら 1998)
    汎化誤差が，マージンがしきい値以下になる確率を含む値で抑えられる

arc-gv

• Brimanによる．マージン最大化をより直接的に行うアンサンブル学習

• 公正な比較をこころみたら，arc-gv より boostingが良かった．
• マージン最大化の考えに反する？

最近の結果

• マージンは学習器の複雑度にも影響される

Attribute Selection for Databases that Contain Correlations by Using Two-Dimensional Rules †

Taufik Djatna and Yasuhiko Morimoto (Hiroshima University, Japan)

• 情報量ゲインや平均二乗誤差の小さな，2次元平面上の領域を見つける
  • x-monotoneといった特徴がある領域を考えることで，効率的に探索

Feature Selection for Temporal Data Mining †

Basabi Chakraborty (Iwate Prefectural University, Japan)

• 多次元の時系列での特徴選択
• ある特徴2系列間の類似度を測る cross translation error
  • 近傍のベクトルへの変化をみる(?)
• 類似している特徴を再帰的に消していく

Semi-Supervised Speaker Identification under Covariate Shift †

Makoto Yamada and Masashi Sugiyama (Tokyo Institute of Technology, Japan)

• 音声による話者認識を半教師あり学習で行う
• sequence kernel [1] を用いたカーネルロジスティック回帰で識別
• 共変量シフトを使い，ロジスティック回帰での事例の重みを変える
  • 重みはラベルなしデータから推定した密度を使う(?)

Personalized Tag Predition Boosted by BaggTaming: A Case Study of the Hatena Bookmark †

Toshihiro Kamishima, Masahiro Hamasaki, and Shotaro Akaho (AIST, Japan)

自分の発表：質問

• 野生+飼育 の両方を併せたデータで学習すると→もっと悪い
• 転移できるのは同じ基準でタグ付けした人がいるから
• boosting：これから比較したい
• 他の帰納転移：混合モデルは悪かった