HOME / 研究展示 / つながり関係からグループを見つける
研究展示
データと学習の科学
05

つながり関係からグループを見つける

無限の柔軟度を持つ関係データモデル

つながり関係からグループを見つける
どんな研究

ソーシャルネットワーキングサービスにおける利用者の繋がり関係や、商品群に対するユーザの購買履歴など、ネットワーク・グラフを含む関係データは、我々の身近に現れます。本研究では、関係データの中に隠れたグループを見つけることを目的としています。

どこが凄い

関係データからグループを見つける際、グループの数やサイズを人手で適切に設定するのは困難です。そこで、グループの数やサイズを入力データのサイズや性質に応じてデータ駆動的に自動調整してくれる能力を持った関係データ解析手法を提案しました。

めざす未来

関係データの中に潜むグループを見つけ出すことによって、そのデータを特徴づける重要な性質を明らかにすることがあります。より大規模な関係データから適切なグループを見つけ出すことで、より効率的に情報を保管・探索・検索するため技術の発展へ貢献していきます。

つながり関係からグループを見つける
関連文献

[1] M. Nakano, A. Kimura, T. Yamada, N. Ueda, “Baxter Permutation Process,” in Proc. Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.

展示説明ムービー
Q&A
Q.質問/コメント A.回答
Q.質問/コメント

下の質問の続きになります。十字を許した状態の特別な場合、つまりビデオの4:00のような regular grid を見取り図分割は含んでいるとして、その時、regular grid に対応する Baxter permutation はpermutation として何か特別な形をしていますか?

A.回答

ご質問ありがとうございます。私の先の回答が言葉足らずでしたので、補足し回答させて頂きます。
結論から申しますと、順列が直接指し示す(中間)長方形分割がregular gridになる確率は0で、解析結果の長方形分割がregular gridになる場合は正の確率を持つというのがより正確な表現でした。図解したものを添付させて頂きます。

入力:関係データ、出力:確率的な長方形分割の問題設定において、今回の我々の戦略は、長方形分割の確率モデルを作ってそれを入力データにフィッティングさせる方法を用いています。その際、確率モデルとして、
・入力データの行が仮想的な[0,1]上のどこかに一様分布により配置される
・入力データの行が仮想的な[0,1]上のどこかに一様分布により配置される
・[0,1]x[0,1]の長方形分割がBaxter順列上の確率モデルに対応して確率的に生成される
の3要素によって構成されています。この3つ目の要素が中間的な長方形分割でして、この中間的な長方形分割がregular gridになるのは確率が0になっていました。一方で、この3要素を改めて入力データの長方形分割として復元した場合には添付ファイル右側のようにregular gridになる場合がありまして正の確率を持ち得ます。
説明不足により誤解を与えてしまい大変失礼しました。ご質問ありがとうございます。

Q.質問/コメント

非常に技術的な質問です、すみません。ビデオの1:16 あたりの右側の図で、上方やや左側のところ、ここは境界線が十字路になっている状況でしょうか?それとも、ここでの「見取り図分割」の定義には、十字路を避ける、という制約条件がついていますか?

A.回答

ご質問ありがとうございます。見取り図分割と長方形分割には「十字路を避ける」という制約は陽には入ってませんでした。1:16あたりの図では列方向に非常に細い分割が推定されているために、十字路が強制的に回避されているかのようにも見えますが、これはモデルが陽に回避しているのではなく、確率的にそのような十字路の発生する分割パターンが結果から外れているだけでした。

Q.質問/コメント

アルゴリズムの実行の度に解析結果は同じ解を出力するのでしょうか。

A.回答

実行の度に同じ解を出力する保証はありません。提案するアルゴリズムは解析結果を確率的に出力するものであるため、アルゴリズムの実行の度に出力結果も変わる可能性があります。

Q.質問/コメント

展示では2つの要素に関する繋がり関係を表す行列を入力データとして対象にしていますが、3つ以上の要素を三次元以上の配列で表したようなデータに対して適用することは可能でしょうか。

A.回答

はい、原理的には三次元以上の配列データに対しても拡張可能です。ただ、実応用上は計算コストの意味で技術的には簡単でないところがあり、現状では二次元配列である行列を主な対象としています。

ポスター
連絡先

中野 允裕 (Masahiro Nakano) メディア情報研究部 メディア認識研究グループ
Email: cs-openhouse-ml@hco.ntt.co.jp

他の研究展示はこちら