| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-03-18 10:00 大規模関係データからのフルランクでない共クラスタ構造発見のための効率的なテンソルスペクトル分解手法の提案 ○梅谷英生・大濵 郁（パナソニック）  IBISML2015-99 |
|
| 抄録 | （和） | 関係データのクラスタリングモデルである確率的ブロックモデル（Stochastic Block Model: SBM）の推定方法としては，変分法やマルコフ連鎖モンテカルロ法など，繰り返し計算によるアルゴリズムが知られている．しかしながら，これらの手法は，データサイズに依存して学習が収束するまでに必要な繰り返し計算の回数が増加するため，大規模なデータへの適用が困難であるという課題があった．近年，Anandkumarらによって，テンソルスペクトル分解を用いたSBMの多項式時間学習アルゴリズムが提案された．しかしながら，Anandkumarらの手法は，入力データを3階のテンソルに変形する必要があるため，計算に必要なメモリ量と計算量がそれぞれ$O(N^3)$になる．また，Anandkumarらの手法では，クラスタ間の接続行列にフルランクを仮定しているため，フルランクでない接続行列を仮定すべきデータを扱うことができない．本研究では，既存のテンソルスペクトル分解と同等の計算を，3階のテンソルを明示的に生成することなく，$O(N^2)$のメモリ量・計算量で学習する手法を提案する．さらに，フルランクでない接続行列を扱うために，フルランク性を仮定して得られた解から，フルランクでない構造を仮定した場合の解を推定する方法を提案する．人工データ及び実データを用いた実験により，提案手法が計算速度と予測性能の観点で優れていることを示す． |
| （英） | The Stochastic Block Model (SBM) is a well-known relational model for discovering co-cluster structure from relational data. The variational methods and Markov chain Monte Carlo methods are well-known approach to perform posterior inference for the SBM. However, it is difficult to apply these methods for large-scale data because the sufficient number of iterative calculation increase as the data size grow. Recently, Anandkumar et al. have proposed a tensor spectral method that is a polynomial-time algorithm to infer the SBM. However, their method requires $O(N^3)$ memory size and computational time. Moreover, their method assumes that the underlying cluster structure is full-rank. These limitations can not be acceptable in many real-world situations. To overcome these problems, we propose a new spectral algorithm to infer the SBM. Our method requires $O(N^2)$ memory size and computational time. Moreover, our method does not require any assumptions for the rank of cluster structure. Finally, experiments conducted using synthetic and real-world datasets confirm that our proposed method significantly outperforms the conventional method in quality of clustering results and computational time. |
|
| キーワード | （和） | 確率的ブロックモデル / スペクトル分解 / コミュニティ検出 / / / / / |
| （英） | Stochastic Block Model / spectral methods / community detection / / / / / | |
| 文献情報 | 信学技報, vol. 115, no. 511, IBISML2015-99, pp. 39-46, 2016年3月. | |
| 資料番号 | IBISML2015-99 | |
| 発行日 | 2016-03-10 (IBISML) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IBISML2015-99 |
|
| 研究会情報 | |
| 研究会 | IBISML |
| 開催期間 | 2016-03-17 - 2016-03-18 |
| 開催地（和） | 統計数理研究所 |
| 開催地（英） | Institute of Statistical Mathematics |
| テーマ（和） | 統計数理, 機械学習, データマイニング, 一般 |
| テーマ（英） | Statistical Mathematics, Machine Learning, Data Mining, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IBISML |
| 会議コード | 2016-03-IBISML |
| 本文の言語 | 日本語 |
| タイトル（和） | 大規模関係データからのフルランクでない共クラスタ構造発見のための効率的なテンソルスペクトル分解手法の提案 |
| サブタイトル（和） | |
| タイトル（英） | An Efficient Tensor Spectral Algorithm for Learning Rank Deficient Co-cluster Structure from Large Scale Relational Data |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 確率的ブロックモデル / Stochastic Block Model |
| キーワード(2)（和/英） | スペクトル分解 / spectral methods |
| キーワード(3)（和/英） | コミュニティ検出 / community detection |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 梅谷 英生 / Hideo Umetani / ウメタニ ヒデオ |
| 第1著者 所属（和/英） | パナソニック株式会社 (略称： パナソニック) Panasonic Corporation (略称： Panasonic Co., Ltd) |
| 第2著者 氏名（和/英/ヨミ） | 大濵 郁 / Iku Ohama / オオハマ イク |
| 第2著者 所属（和/英） | パナソニック株式会社 (略称： パナソニック) Panasonic Corporation (略称： Panasonic Co., Ltd) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-03-18 10:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IBISML |
| 資料番号 | IBISML2015-99 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | no.511 |
| ページ範囲 | pp.39-46 |
| ページ数 | 8 |
| 発行日 | 2016-03-10 (IBISML) |
[研究会発表申込システムのトップページに戻る]