Dwango AI Lab
Technical Report

Research Introduction: Metarelation Mining

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).

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 the length K of tuples. In the future, we plan to propose a yet faster method.



Seiya Satoh (AIST) seiya.satoh@aist.go.jp
Hiroshi Yamakawa (DWANGO) hiroshi_yamakawa@dwango.co.jp

2017/9/8 (Y/M/D)