差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
メタ関係発見 [2017/12/20 10:25]
ymkw
メタ関係発見 [2019/03/10 07:57]
ymkw
ライン 1: ライン 1:
 ====== メタ関係発見(研究紹介) ====== ====== メタ関係発見(研究紹介) ======
 +=== 技術概要 ===
 + 「メタ関係発見 (Metarelation Mining)」とは「関係の関係性を見付ける」手法です。ここで系列を区別するための属性があたえられてない、多次元系列における関係を「系列の組」とした場合、「系列の組」間のメタな関係を発見することです。なお、組は順序付けられた集合(リストに似たもの)です。その中で私たちが着目し取り組みを進めているのが、等価なメタ関係の発見を行う「等価性構造(Equivalence Structure:ES)抽出」です。
  
- 「メタ関係発見」とは「関係の関係性を見付ける」手法です。ここで系列を区別するための属性があたえられてない、多次元系列における関係を「系列の組」とした場合、「系列の組」間のメタな関係を発見することです。なお、組は順序付けられた集合(リストに似たもの)です。その中で私たちが着目し取り組みを進めているのが、等価なメタ関係の発見を行う「等価性構造(Equivalence Structure:ES)抽出」です。 +{{ :​figure-meta-relation_mining.png?​400 |This is the caption}}
- +
-{{ :​figure-meta-relation_mining.png?​400 |This is the caption}}+
 > 図:等価性構造抽出の例。#​1〜#​8の系列(系列)から〈#​1,​ #2, #​3〉と〈#​8,​ #7, #​5〉という二つの組を取り出し、この二つの組にメタ関係があるかどうかを検証する。この例では、青、赤、黒の3つの部分列が酷似しているため、等価なメタ関係と見なす。 > 図:等価性構造抽出の例。#​1〜#​8の系列(系列)から〈#​1,​ #2, #​3〉と〈#​8,​ #7, #​5〉という二つの組を取り出し、この二つの組にメタ関係があるかどうかを検証する。この例では、青、赤、黒の3つの部分列が酷似しているため、等価なメタ関係と見なす。
  
-   + 等価性構造抽出では、二つ以上の組を比較して、必ずしも同時でない時刻(非同期)において「似た部分列が含まれている」ときに、「等価」というメタ関係を持つ構造が発見されたと考えます。この抽出は「属性が未知である」といった場合でも利用できる特徴を持ちます。「非同期」かつ「属性が未知である」データの例として、ヒトとチンパンジーの脳波の中にある等価な関係を見つけるタスクが考えられます。このようなデータでは一般的に同期していないため、時刻の違いを吸収する必要があります.またここで言う属性が未知であるとは,ヒトとチンパンジーでは各脳波の持つ属性(働きや意味)がどう対応しているのか分からないということです。このようなデータ間で等価性構造を見つけると,脳波の何れの系列同士が対応しているかを見つけることに役立ちます。ここで二つの組が等価であるかどうかの判定は、部分列を比較し、十分に類似しているかを基に行います。これにより、非同期で属性が未知な関係でも関係性を発見できます。
- 等価性構造抽出では、二つ以上の組を比較して、必ずしも同時でない時刻(非同期)において「似た部分列が含まれている」ときに、「等価」というメタ関係を持つ構造が発見されたと考えます。この抽出は「属性が未知である」といった場合でも利用できる特徴を持ちます。「非同期」かつ「属性が未知である」データの例として、ヒトとチンパンジーの脳波の中にある等価な関係を見つけるタスクが考えられます。このようなデータでは一般的に同期していないため、時刻の違いを吸収する必要があります.またここで言う属性が未知であるとは,ヒトとチンパンジーでは各脳波の持つ属性(働きや意味)がどう対応しているのか分からないということです。このようなデータ間で等価性構造を見つけると,脳波の何れの系列同士が対応しているかを見つけることに役立ちます。ここで二つの組が等価であるかどうかの判定は、部分列を比較し、十分に類似しているかを基に行います。これにより、非同期で属性が未知な関係でも関係性を発見できます。+
  
  ES抽出の大きな問題点は、その計算量の多さです。すべての系列の数をNとし、組の大きさをKとしたとき、探索する組の数はN個の中からK個を並べる順列になり、その中で部分列の比較も行う必要もあります。我々は直接K順列を計算するのではなく,Kを逐次的に増やす探索手法(ESIS)を提案し、これにより計算時間を削減しました。実用性を高めるために今後一層の計算時間の削減に取り組んでいます。  ES抽出の大きな問題点は、その計算量の多さです。すべての系列の数をNとし、組の大きさをKとしたとき、探索する組の数はN個の中からK個を並べる順列になり、その中で部分列の比較も行う必要もあります。我々は直接K順列を計算するのではなく,Kを逐次的に増やす探索手法(ESIS)を提案し、これにより計算時間を削減しました。実用性を高めるために今後一層の計算時間の削減に取り組んでいます。
  
 === 参考文献 === === 参考文献 ===
 +  メタ関係発見(研究紹介)
 +  ​
 +  * Seiya Satoh, Yoshinobu Takahashi, Hiroshi Yamakawa. Accelerated Equivalence Structure Extraction via Pairwise Incremental Search. KDD 2018.
 +  * Seiya Satoh, Yoshinobu Takahashi and Hiroshi Yamakawa, “Validation of Equivalence Structure Incremental Search’’,​ Front. Robot. AI, 19 December 2017 | doi: 10.3389/​frobt.2017.00063,​ (https://​goo.gl/​59jR2p)
   * Seiya, Satoh; Hiroshi, Yamakawa. ‘‘Incremental Extraction of High-Dimensional Equivalence Structures’’. In Proc. of the International Joint Conference on Neural Networks (IJCNN), 2017.   * Seiya, Satoh; Hiroshi, Yamakawa. ‘‘Incremental Extraction of High-Dimensional Equivalence Structures’’. In Proc. of the International Joint Conference on Neural Networks (IJCNN), 2017.
   * 佐藤聖也,​ 高橋良暢,​ 山川宏. “等価性構造保持仮定の下での等価性構造抽出における探索数削減’’. 信学技報,​ 2016, vol. 116, no. 381, COMP2016-48,​ pp. 81--86.   * 佐藤聖也,​ 高橋良暢,​ 山川宏. “等価性構造保持仮定の下での等価性構造抽出における探索数削減’’. 信学技報,​ 2016, vol. 116, no. 381, COMP2016-48,​ pp. 81--86.