metarelation_mining

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision 		Previous revision
metarelation_mining [2021/08/27 16:51]
ymkw created 		metarelation_mining [2021/08/31 18:34] (current)
ymkw
Line 1: Line 1:
-====== メタ関係発見（研究紹介） ====== +====== Metarelation Mining ====== 
-=== 技術概要 === +=== Technology Overview ===
-　「メタ関係発見 (Metarelation Mining)」とは「関係の関係性を見付ける」手法です。ここで系列を区別するための属性があたえられてない、多次元系列における関係を「系列の組」とした場合、「系列の組」間のメタな関係を発見することです。なお、組は順序付けられた集合（リストに似たもの）です。その中で私たちが着目し取り組みを進めているのが、等価なメタ関係の発見を行う「等価性構造（Equivalence Structure：ES）抽出」です。+
  
-> {{ :figure-meta-relation_mining.png?400 |This is the caption}} +Metarelation mining is a process used to find “relations of relations.” We focus on relations between sequences where their roles (attributes) are unknown. In this case, metarelations of interest are relations between such relations. A technique for metarelation mining we focus on is called **equivalence structure (ES) extraction**, which allows for finding analogous metarelations (Fig. 1). 
-> 図：等価性構造抽出の例。#1〜#8の系列（系列）から〈#1, #2, #3〉と〈#8, #7, #5〉という二つの組を取り出し、この二つの組にメタ関係があるかどうかを検証する。この例では、青、赤、黒の３つの部分列が酷似しているため、等価なメタ関係と見なす。+
  
- 等価性構造抽出では、二つ以上の組を比較して、必ずしも同時でない時刻（非同期）において「似た部分列が含まれている」ときに、「等価」というメタ関係を持つ構造が発見されたと考えます。この抽出は「属性が未知である」といった場合でも利用できる特徴を持ちます。「非同期」かつ「属性が未知である」データの例として、ヒトとチンパンジーの脳波の中にある等価な関係を見つけるタスクが考えられます。このようなデータでは一般的に同期していないため、時刻の違いを吸収する必要があります．またここで言う属性が未知であるとは，ヒトとチンパンジーでは各脳波の持つ属性（働きや意味）がどう対応しているのか分からないということです。このようなデータ間で等価性構造を見つけると，脳波の何れの系列同士が対応しているかを見つけることに役立ちます。ここで二つの組が等価であるかどうかの判定は、部分列を比較し、十分に類似しているかを基に行います。これにより、非同期で属性が未知な関係でも関係性を発見できます。 
  
-　ＥＳ抽出の大きな問題点は、その計算量の多さです。すべての系列の数をNとし、組の大きさをKとしたとき、探索する組の数はN個の中からK個を並べる順列になり、その中で部分列の比較も行う必要もあります。我々は直接K順列を計算するのではなく，Kを逐次的に増やす探索手法（ESIS）を提案し、これにより計算時間を削減しました。実用性を高めるために今後一層の計算時間の削減に取り組んでいます。+{{ :fig1.png?600 |}} 
 + 
 + Fig. 1: An illustration of ES extraction. Two three-dimensional sequences specified by tuples <#1, #2, #3> and <#8, #7, #5> are compared to validate if there is a metarelation between the three-dimensional sequences. Because a subsequence of one three-dimensional sequence shown by a blue, a red and a black box closely resembles a subsequence of the other 3d sequence, they are likely to be considered to have an analogous metarelation. 
 + 
 +In ES extraction, an analogous metarelation between two multidimensional sequences is considered found based on the comparisons of their subsequences. The implementation of such comparisons allows for finding relations between asynchronous sequences. Therefore, ES extraction can be applicable to data that are “asynchronous” and “the attribute of each sequence is unknown.” A task using such data can be a task to find metarelations between the brainwaves of a human and those of a chimpanzee. Such data are usually asynchronous, and it is unknown how the brainwaves of a human correspond to those of a chimp, which means that the attribute of each sequence is unknown. Metarelations found in such data can be useful to find correspondence relations between the brainwaves of a human and those of a chimpanzee.  
 + 
 +One difficulty in the ES extraction is that the brute-force search is usually not feasible. Given N sequences, the number of K-tuples is K-permutations of N, which causes a combinatorial explosion. Moreover, comparisons of subsequences are implemented for each comparison of two K-dimensional sequences specified by K-tuples. To reduce the processing time, we recently propose a method called ESIS, in which ESs are obtained increasing K. In the future, we plan to propose a yet faster method.  
 + 
 + 
 +=== Related works ===
  
-=== 参考文献 === 
-メタ関係発見（研究紹介） 
   * Seiya Sato, Hiroshi Yamakawa: Bypassing combinatorial explosions in equivalence structure extraction. Knowledge and Information Systems (2021) https://doi.org/10.1007/s10115-021-01599-9 ( [[https://rdcu.be/ct1TZ | SharedIt]] )    * Seiya Sato, Hiroshi Yamakawa: Bypassing combinatorial explosions in equivalence structure extraction. Knowledge and Information Systems (2021) https://doi.org/10.1007/s10115-021-01599-9 ( [[https://rdcu.be/ct1TZ | SharedIt]] ) 
   * Seiya Satoh, Yoshinobu Takahashi, Hiroshi Yamakawa. Accelerated Equivalence Structure Extraction via Pairwise Incremental Search. KDD 2018.   * Seiya Satoh, Yoshinobu Takahashi, Hiroshi Yamakawa. Accelerated Equivalence Structure Extraction via Pairwise Incremental Search. KDD 2018.
Line 25: Line 29:
   * Hiroshi, Yamakawa. “Hippocampal Formation Mechanism Will Inspire Frame Generation for Building an Artificial General Intelligence’’. In Proc. of the International Conference on Artificial General Intelligence (AGI), 2012. pp.362--371.   * Hiroshi, Yamakawa. “Hippocampal Formation Mechanism Will Inspire Frame Generation for Building an Artificial General Intelligence’’. In Proc. of the International Conference on Artificial General Intelligence (AGI), 2012. pp.362--371.
  
-=== 連絡先 === +=== Contact === 
-佐藤聖也(AIST) ,  山川宏(全脳アーキテクチャ・イニシアティブ)+Seiya Sato (Tokyo Denki University) ,  Hiroshi Yamakawa (The Whole Brain Architecture Initiative)
  
  • metarelation_mining.1630050713.txt.gz
  • Last modified: 2021/08/27 16:51
  • by ymkw