Metarelation Mining

　“Metarelation Mining” is a technique for “finding relations within relations. It is a technique for finding meta-relationships between “pairs of series.” A “pair” is a relationship between multidimensional series that have no distinguishing attributes. A pair is an ordered set (similar to a list). What we are focusing on and working on is Equivalence Structure (ES) extraction, which finds equivalent meta-relations.

Figure: Example of equivalence structure extraction. From the series of #1 to #8 (series), we extract two pairs, 〈#1, #2, #3〉 and 〈#8, #7, #5〉, and verify whether there is a meta-relationship between these two pairs. In this example, the three subsequences (blue, red, and black) are very similar, so we consider them to be equivalent meta-relations.

In equivalence structure extraction, when two or more pairs are compared and “contain similar subsequences” at times that are not necessarily simultaneous (asynchronous), a structure with a meta-relationship called “equivalence” is considered to have been discovered. This extraction has a feature that can be used even in cases where the attributes are unknown. An example of “asynchronous” and “unknown attribute” data is the task of finding equivalent relations in human and chimpanzee brain waves. Since such data is generally not synchronized, it is necessary to absorb the differences in time. Also, unknown attributes here means that we do not know how the attributes (functions and meanings) of each brain wave correspond to each other in humans and chimpanzees. Finding an equivalence structure between such data can help us find out which series of EEGs correspond to each other. Here, the determination of whether two pairs are equivalent is based on comparing the subsequences and whether they are similar enough. This allows us to discover relationships even when the relationships are asynchronous and the attributes are unknown.

Translated with www.DeepL.com/Translator (free version)

　The major problem with ES extraction is its large computational complexity. If the number of all series is N and the size of a pair is K, the number of pairs to be searched is K permutations out of N. Furthermore, it is necessary to compare sub-sequences among them. We proposed a search method (ESIS) that sequentially increases the number of K permutations, instead of directly calculating K permutations, to reduce the computation time. We are currently working on further reducing the computation time in order to improve the practicality.

• 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 ( SharedIt )
• 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.
• 佐藤聖也, 高橋良暢, 山川宏. “等価性構造保持仮定の下での等価性構造抽出における探索数削減’’. 信学技報, 2016, vol. 116, no. 381, COMP2016-48, pp. 81–86.
• 高橋良暢, 佐藤聖也, 山川宏. “等価性構造抽出技術の定式化’’. 第4回汎用人工知能研究会, SIG-AGI-004-03, 2016.
• 潮旭, 高橋良暢, 佐藤聖也, 山川宏. “等価性構造探索を効率化するための局所生起分布の性質調査’’. 信学技報, 2016, vol. 116, no. 300, 第19回情報論的学習理論ワークショップ(IBISML2016) T1-6, pp33–36.
• 佐藤聖也, 山川宏. “高速化に向けた等価性構造の特徴解析’’. 第3回汎用人工知能研究会, SIG-AGI-003-01, 2016.
• Hiroshi, Yamakawa, “Brain-inspired equivalence structure extraction technique for generating frames’’. Society for NeuroScience 2013, 2013.
• 山川宏. “局所多次元時系列の関係表現としての性質の実験的検討’’. 第27回人工知能学会全国大会, 2013.
• 山川宏. “反転分布に対称性を仮定した関係縮約’’, 第26回人工知能学会全国大会, 2012.
• 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.

佐藤聖也(AIST) , 山川宏(全脳アーキテクチャ・イニシアティブ)