NSCaching: 知識グラフ埋め込みのための単純かつ効率的なネガティブサンプリング

知識グラフ（Knowledge Graph: KG）の埋め込みは、多くの実世界の応用を持つデータマイニング研究における基本的な問題です。この問題は、グラフ内のエンティティとリレーションを低次元ベクトル空間に符号化することを目指しており、その後のアルゴリズムで利用されます。負例サンプリングは、訓練データで観測されていないものから負の三項集合をサンプリングするプロセスであり、KG埋め込みにおいて重要なステップです。最近、生成対抗ネットワーク（Generative Adversarial Network: GAN）が負例サンプリングに導入されました。高スコアを持つ負の三項集合をサンプリングすることで、これらの方法は勾配消失問題を回避し、より良い性能を得ています。しかし、GANを使用すると元のモデルが複雑になり、訓練が困難になるため、強化学習が必要となります。本論文では、高スコアを持つ負の三項集合が重要であるが稀であるという観察に基づき、キャッシュを使って直接それらを追跡することを提案します。ただし、キャッシュからのサンプリングと更新方法は重要な課題です。私たちは効率的でありながら、探索と活用の間で良好なバランスを達成するソリューションを慎重に設計しました。これにより、当手法は以前のGANベースの手法の「精製版」となります。つまり、負の三項集合全体の分布に適合するために追加パラメータに訓練時間を浪費しません。広範な実験結果は、当手法が様々なKG埋め込みモデルで大幅な改善をもたらし、最先端のGANに基づく負例サンプリング手法よりも優れていることを示しています。