#freeze
* 第9回人工知能学会データマイニングと統計数理研究会 [#k73cfa69]
このページはしましまが[[第9回人工知能学会データマイニングと統計数理研究会>DMSM#DMSM009]] に参加してとったメモです．私の主観や勘違いが含まれていたり，私が全く分かってなかったりしていますので，その点を注意してご覧ください．誤りがあれば，指摘してください．
* 3月 3日 (水) [#c516a03f]
** 招待講演：劣モジュラ最適化 [#ea752c45]
[[京都大学 数理解析研究所 岩田覚 教授>http://www.kurims.kyoto-u.ac.jp/~iwata/]]
講演概要：劣モジュラ関数は，凸関数の離散版に当たる集合関数であり，組合せ最適化を始めとして，情報理論，待ち行列理論，ゲーム理論等，数理工学の様々な分野で頻繁に現れる．ネットワークのカット容量関数，マトロイドの階数関数，多元情報源のエントロピー関数などが劣モジュラ性を有する．本講演では，劣モジュラ関数に関する最適化問題の基礎から最新の成果までを紹介する．
劣モジュラ関数：有限集合 V に対し，関数 f：{Vのべき集合}→{実数}
任意の X, Y⊆V に対し，次式を満たす関数を劣モジュラ関数という
f(X) + f(Y) ≧ f(X∩Y) + f(X∪Y)
劣モジュラ関数の例
- Cut Capacity Function：ネットをカットした部分から出てくる流量
- Matroid Rank Functions：行列 A の列集合 X を選んで作った行列の階数
- エントロピー関数：情報源 V の部分集合 X と Y に対するエントロピー関数
h(X) + h(Y) ≧ h(X∩Y) + h(X∪Y)
- 正定値対象行列：対角上の部分行列 A[X] に対して，f(X)＝log det A[X] とすると，Ky Fan の不等式により劣モジュラ関数に
劣モジュラ性から導かれる性質
- 離散凸性
S⊆T ⇒ f(S∪{u}) - f(S) ≧ f(T∪{u}) - f({u})
同じものを足すとき，大きな集合に対して足す方が，増分が少ない
- V の部分集合を，超立方体の頂点にわりあてる~
頂点では，対応する集合を引数とする劣モジュラ関数 f の値をとる~
この超立方体から，|V|-1個の頂点を順次選ぶことで，n! 個の単体で超立方体を分割~
単体上の関数値を線形補完で決めた関数 ^f は，元の関数 f に劣モジュラ性があると，凸関数になる
劣モジュラ関数 f の最適化
- 劣モジュラ関数を呼び出す回数を多項式回に抑えたい
- 楕円体法で多項式時間でとける：Grötschel, Lováz, Schrijver (1981)
Base Polyhedra
- 劣モジュラ多面体：劣モジュラ関数が境界になるような多面体
- 制約が 2^n の多面体では意味がない
- この多面体の端点は，対象に線形順序を決めれば容易に求まる
劣モジュラ最適化
- 現状は O(n^5〜6) で解ける
- 純粋に組み合わせ的な解法 O(n^8 log^2 n)
- 実用的には Wolfe アルゴリズム
応用問題
- dynamic flow：流量だけでなく，流速も考える．
- 多元情報源符号化：誤りなく符号化できるかを調べるには 2^n 個の制約チェックが必要だが，劣モジュラ関数最適化に帰着できる
- 多重クラス待ち行列：複数の待ち行列のうち，どのキューを次に処理するかを選択できる状況．サービスを一定以上の品質で処理できるかどうかも，指数個の制約がでてきて，劣モジュラ最適化を使える
対称劣モジュラ関数：この性質があるととても効率的
- ネットをカットしたとき，ネットが無向なので，カットした方から出る流量と，残りの補集合の流量が等しい条件
* セッション1 （一般発表） [#n36b401e]
** ラベル信頼度を利用したブースティング手法 [#h52993b0]
○中田康太，櫻井茂明，折原良平（東芝研究開発センター）
- 専門家の高精度ラベルと，非専門家による多量の低精度データがある．どちらがつけたかは分かっている．
- 信頼度は，近傍にあるデータのラベルとの一致度に基づいて行う
** 否定枝を含むshared BDD上で動作するEMアルゴリズム [#j68f612c]
○石畠正和，亀谷由隆，佐藤泰介（東京工業大学），湊真一（北海道大学）
- 確率と論理の融合：確率は依存して出力が決まるが，論理は独立に真偽が決まる．
- 確率的に真偽が決まる確率的命題変数と，論理関数を記述に使う
- 真偽が観測される観測命題から，観測されない基本命題が真になる確率を求める．
- 従来手法：BDD(binary decision diagram)-EMアルゴリズム
-- BDD上で，前向き/後ろ向き確率を計算すると，EMの計算に必要な期待値や事後確率の計算が容易になる
- 観測が同じ変数の多次元になった場合に，否定枝を使ったshared BDDで効率化を図る
** 疎な相関グラフの学習による相関異常の検出 [#aa9aba2f]
○井手剛（日本IBM東京基礎研究所）
- 相関の変動が大きい時系列の集合から，相関のパターンが変わったことを検出する
- まず，定常状態で，変量集合の中から相関の高い疎な構造を見つけ，リファレンスとの違いを見つける
- グラフィカルガウスモデル(GGM)：ガウス分布の精度行列が0になる要素間には辺がないグラフ
- 実際には 0 の要素はないのでどうするか → 共分散構造選択などの方法 → 共分散行列の逆行列がネック
-- L1 正則化を使って，共分散行列から，疎な精度行列を求める
- グラフから異常度を計算する：グラフの表す確率分布のKLダイバージェンスを使う
** 分類器のクラスタリングによる学習対象変化のマイニング [#y1e715b9]
○西田京介，山内康一郎（北海道大学）
- 時系列中で大きな変化と，漸次的な変化の両方に対応できるようにする
- オンライン分類器で学習を始め，大きな変化を検出したら，更新を停止してオフライン分類器とする．
- こうして作られた分類器の加重移動平均の変化により，時系列の変化を見つけ出す
- 分類傾向の類似性により，過去の分類器をクラスタリングすることで，過去の類似したパターンを見つけ出す．
* セッション2 （review発表） [#bfec9727]
** 転移学習のサーベイ [#h11066e2]
○神嶌 敏弘（産業技術総合研究所）
質問
- 標本選択バイアスの分類との対応：分布の一致は見るのは大変では？
- S-T- はやはり難しいのでは？
** GAMとその周辺 [#kd091bbc]
○田中祐輔（大阪電気通信大学），伊庭克拓（東京CRO(株)），竹澤邦夫（農業・食品産業技術総合研究機構），辻谷将明（大阪電気通信大学）
- GAM：一般化加算モデル
平滑化スプライン： (残差平方和) + λ (2次微分のL2ノルム)
- 一般化CVで適切なパラメータを求める
** 消費者行動モデル研究の変遷と大規模データの利活用に向け [#i8deefe6]
○石垣司，本村陽一（産業技術総合研究所）
サービス工学
- サービスの受容者と提供者を''観測''し，それを''分析'して，モデルを再''構成''し，''適用''する
- 大手ではないが成功しているスーパー：オギノ，ヤオコー，まるまつ
-- 共通する要因はない → サービス工学のサイクルは共通している
サービス業：経験と勘など属人的な要因は，経営規模の拡大に対応できない
- 大規模データを用いたモデル化を行う
消費者行動理論
- 心理的プロセスモデル：AIDMA (Attention Interest Desire Memory Action)モデル 広告に対する反応
- 確率モデル：ロジット，プロビット，マルコフ行列モデル，ハフモデル
- 刺激-反応モデル：消費者に対する入力と出力を見て，中身はブラックボックス
- 情報処理モデル：消費者の内的状態を情報処理プロセスによりモデル化 → 変数の意味があいまいで，関係が複雑なので，データからの実証には向かない
それぞれ一長一短があって，予測・制御に向かない
- ベイジアンネットや一般状態空間モデルなど，内部状態をもつモデルが使えるようになった
- こうしたモデルを使って，予測から，制御にまで，適用できるようなループにする必要
* 3月 4日 (水) [#dce3baa0]
* セッション3（一般発表） [#q33a4bd5]
** CF-Suffix Trieを用いた頻出移動パターンマイニング手法 [#z17312d9]
○稲田泰裕，池田大輔，鈴木英之進（九州大学）
- 点の系列があるとき，それらの共通系列パターンを見つける
- 時空間の系列では，シンボルと違って一致の定義が必要：最大半径 θr 以内
-- 点が存在する半径ができるだけ小さくなるように，系列パターンを見つける方法
- Suffix trie の分岐を，BIRCHのCF木で表したものと置き換えた CF-Suffix trie
** 長大な単一系列データにおける頻出飽和系列の高速マイニング [#p881c064]
○村田拓也，岩沼宏冶，鍋島英知（山梨大学）
- Winepi型の系列パターンマイニング
- 系列先頭頻度：各ウィンドウ内の先頭要素を含むようなパターンのみを数える頻度 → この頻度が一定以上のものを抽出
- 頻出系列が膨大なので，頻出右飽和系列のみを保存することで，可逆圧縮
- 頻出飽和系列：パターンにシンボルを足したもので，頻出なパターンがない系列~
→ これだけ記憶していても元の頻出系列パターン集合は復元できない
- 頻出飽和系列：系列の先頭の右側にシンボルを足したパターンのみを拡張系列と考えた，頻出飽和系列 → 可逆圧縮になっている
- あまり圧縮できなかった → シンボルを足すと系列パターンの頻度が変わってしまうため
** 精度保証付きオンライン型高速近似系列マイニング [#u53fbcaa]
○村田順平，岩沼宏治，石原龍一，鍋島英知（山梨大学）
- データストリームからのオンラインマイニング
- 系列長 N に対し，σN 以上の頻出パターンになるものは全て抽出し，かつ，その他のパターンも頻度はεN以上を保証
** 時系列テキストデータからの時間的出現依存関係に基づく重要単語の抽出 [#u8edeb31]
○多田知道，岩沼宏治，鍋島英知（山梨大学）
- 新聞記事の時間系列中から重要な名詞系列パターンを抽出する
- TF-IDayF: IDF が，全ての記事中の文書頻度であるのに対し，単語を含む1日の文書集合数を日数で割った値
- TF-IDayF で重要とされた単語集合に対して系列パターンを抽出する
- さらにウィンドウ内での，単語の共起性も考慮する
* セッション4 （一般発表） [#hc50bfd9]
** サポートベクトル回帰におけるDecremental Algorithmの一般化に関する一考察 [#e9e34a00]
○烏山 昌幸，竹内 一郎（名古屋工業大学），中野 良平（中部大学）
- decremental algorithm：データ点が削除されたときに，効率的にモデルを更新できる．
-- データを1点ずつではなく，まとめて複数個削除できる方法の提案
- サポートベクトル回帰では，削除する点のパラメータを 0 にして，その他のパラメータを更新することで実現
- 点に対応するパラメータαiは許容誤差内では 0，線上では [0,C]，外部では C．
-- 線上の点でのパラメータ値と，許容誤差の領域が変化するので，それらを更新する必要．この更新を一括削除で効率的になるように改良．
** 交差検定法に基づく一般化情報量規準の近似計算 [#lb3c536a]
○力徳正輝（ジャストシステム）
- GIC の近似計算と，正則化つきのlogistic回帰やSVMの関係
-- GIC：統計モデルがデータ分布の凡関数が使えて，尤度以外にも適用可
-- GICの影響関数(凡関数の方向微分)の数値計算を近似的行う
- 微少な変化を，元のデータを重み付きにすることで実現し，パラメータを推定し，パラメータの方向微分を計算する．
** 分配関数のビリーフプロパゲーションによる計算とグラフ多項式 [#u6bc0119]
○渡辺有祐，福水健次（統計数理研究所）
- MRFの分配関数の計算は頂点数に対して指数的に増加するので，loopyな場合の信念伝播で計算する
- この話題に関連した考察
** 社会ネットワークにおける汚染拡散最小化のためのリンク封鎖 [#g327c363]
○木村昌弘（龍谷大学），斉藤和巳（静岡県立大学），元田浩（大阪大学）
- ネットワーク上での拡散を防ぐために，どの辺を除去すべきか？
- 汚染の発生源はどこか不明のとき，汚染を平均的・最悪の場合を最小化する
-- ICモデル：汚染がきたとき，次の時刻でのみ確率 p で近傍ノード伝播させるモデル，その後に伝播させることはない
- Bond percolation法を利用したアルゴリズムの提案
* セッション5 （一般発表） [#a2aa94e6]
** カスケードモデルからの少数ルール群選択による高性能分類器の構築 [#l62761e8]
○大村隆晴，中野優，岡田孝（関西学院大学）
- 階層的に分類を繰り返すカスケードモデル
-- カバーする事例を広げるモデルと，予測精度の良いモデルのどちらを次の階層で採用すべきか？
- 両者の要素を考慮した評価関数の提案
** 分子グラフにおける構造差異の定量的表現 [#vdbb543e]
○大田黒空，高橋由雅（豊橋技術科学大学）
- 分子グラフ：分子を原子の結合をグラフで表し，結合の種類に応じて重み付けしたもの
-- 頂点差異，辺差異，科学構造差異の三つの定量指標を提案
- これらの指標に対する制約でクエリを記述し，合致する化合物を見つける．
** 部分グラフ同型判定のためのグラフスペクトル最適化手法 [#pfeb5d04]
○グェンズィヴィン，大原剛三，鷲尾隆（大阪大学）
- 部分グラフ同型判定：従来の方法 Ullmanの方法，VF2
- グラフスペクトルを使う方法の改良
- 誘導部分グラフ：部分グラフで，部分グラフに含まれる頂点対に，元のグラフで辺があれば，その辺は部分グラフに残っているもの．誘導部分グラフの隣接行列は，もとのグラフの主小行列になる．
- 行列生成ベクトル：隣接行列の辺に一意な数値を割り当てるベクトル
- interlace定理：元の行列の固有値を整列したとき，隣接した固有値の差が，主小行列の固有値のとる範囲になる．
- 行列生成ベクトルをうまく定めることで，効率化をめざす．
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
