マルチインスタンス学習による検索方法及びシステム
【課題】マルチインスタンス学習による検索方法及びシステムを開示する。
【解決手段】本願の方法は、正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得し、及びテストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定することを含み、前記重みの絶対的な大きさは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。本発明により、正の訓練パッケージにおけるインスタンスにより提供された情報がより十分に利用され、検索性能が向上される。
【解決手段】本願の方法は、正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得し、及びテストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定することを含み、前記重みの絶対的な大きさは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。本発明により、正の訓練パッケージにおけるインスタンスにより提供された情報がより十分に利用され、検索性能が向上される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に画像処理技術分野に関し、特にマルチインスタンス学習による検索方法及びシステムに関する。
【背景技術】
【０００２】
デジタル画像数の急速な増大につれて、高速で且つ有効な画像検索技術が求められている。その技術は人間の日常生活、例えばデジタル写真管理、オンラインショッピング、リモート教育等に多く適用することができる。
【０００３】
画像検索技術は、主にテキストによる画像検索技術とコンテンツ〔内容〕による画像検索技術とを含む。コンテンツによる画像検索技術は、テキストによる画像検索技術と異なり、画像上の文字描画に基づいてインデックスを生成することなく、画像毎の視覚コンテンツ特徴、例えば色合い、テクスチャ、形状等を自動的に抽出し、そうした視覚コンテンツ特徴に基づいてインデックスを生成する。検索を行う際に、ユーザは代表的な一つ又は複数のサンプル画像を選択してルックアップを構築した後に、検索システムにサンプル画像の視覚コンテンツ特徴と類似する画像を探索させることができる。
【０００４】
領域特徴が人間の視覚感知によく合致し、且つ領域特徴による検索技術で一般的により良い検索性能を得られるため、領域特徴による画像検索はコンテンツによる画像検索の重要な手法の一つになる。領域特徴による検索とは、画像分割技術で画像において意味のある領域を抽出した後に、領域ごとに局所特徴を用いて描画を行い、各領域特徴を統合して画像の特徴描画を取得し、これら特徴に基づいて検索アルゴリズムを設計して検索を行うことである。マルチインスタンス学習は、領域による画像検索に適用されて成功を収めている効率的なアルゴリズムである。
【０００５】
マルチインスタンス学習による画像検索においては、それぞれの画像がパッケージとされ、画像における領域のそれぞれがインスタンスとされる。データセットは種類の標識を有するパッケージにより構成され、それぞれのパッケージには種類の標識を有しない若干のインスタンスが含まれる。マルチインスタンスの基本的な出発点として、少なくとも一つの正のインスタンス（後述）を含むパッケージであれば、当該パッケージが正の訓練〔トレーニング〕パッケージと標識される。その一方、パッケージ中のインスタンスが全て負のものであれば、当該パッケージが負の訓練パッケージと標識される。
【０００６】
負の訓練パッケージは、その中に含まれるインスタンスが必ず負のものである。正の訓練パッケージは、その中に正のインスタンスと負のインスタンスの両方が含まれてもよい。更に、システムはどのインスタンスが正であるか、どのインスタンスが負であるかは知らない。従って、マルチインスタンス学習において、最も重要な問題は、どのように正の訓練パッケージにおけるインスタンスにより提供される情報を用いて検索を行うかということにある。
【０００７】
従来の技術におけるアルゴリズムは、一般的に好適な方法を用いて、正の訓練パッケージに含まれる正のインスタンスを選択することを意図する。この方法は、少なくとも、予め選択すべきインスタンスの数を決定しておく必要があるという欠点がある。例えば、それぞれの正の訓練パッケージから一つの正のインスタンスしか選択できないという制限がある場合に、一つのインスタンスのみが最終的な検索に関係することになるが、実際に正の訓練パッケージに含まれる正のインスタンスが一つだけではないことがよくある。その中の一つのインスタンスのみを用いて検索を行うと、正の訓練パッケージにおけるインスタンスにより提供される情報が十分に利用できず、検索の性能が制限されることになる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施例は、上記の事情に鑑み、正の訓練パッケージにおけるインスタンスにより提供される情報がより十分に利用され、検索性能が向上される、マルチインスタンス学習による検索方法及びシステムを提供する。
【課題を解決するための手段】
【０００９】
本発明の実施例の一つの側面によれば、マルチインスタンス学習による検索方法であって、正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得し、テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定することを含み、前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、方法が提供される。
【００１０】
本発明の実施例の別の側面によれば、マルチインスタンス学習による検索システムであって、正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得するように構成される取得手段と、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成される訓練インスタンス重み生成手段と、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得するように構成されるテストインスタンスソートスコア取得手段と、テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される検索結果特定手段とを備え、前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、システムが提供される。
【００１１】
また、本発明の別の側面によれば、さらに記憶媒体が提供される。前記記憶媒体は、機械読取可能なプログラムコードを含む。前記プログラムコードは、情報処理装置で実行されると、前記情報処理装置に本発明による前記のマルチインスタンス学習による検索方法を実行させる。
【００１２】
また、本発明の別の側面によれば、さらにプログラムが提供される。前記プログラムは機械読取可能なコマンドを含む。前記コマンドは、情報処理装置で実行されると、前記情報処理装置に本発明による前記のマルチインスタンス学習による検索方法を実行させる。
【発明の効果】
【００１３】
本発明の実施例の前記方法によれば、画像検索を行う過程において、正の訓練パッケージにおいる訓練インスタンス毎に重みを生成することができる。当該重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。これにより、最後にテストパッケージにおけるテストインスタンスのそれぞれのソートスコアを算出する際に、正の訓練パッケージにおける訓練インスタンスに対し、それぞれの重みをその初期ラベルとし、最終的に各テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを取得して検索結果を与えることができる。従って、本発明の実施例においては、正の訓練パッケージから限定された数量の正のインスタンスを選択することは意図されず、正の訓練パッケージにおけるインスタンス毎にそれぞれの重みを算出し、当該重みの絶対的な大きさでインスタンスのそれぞれとユーザのルックアップ語義との一致度を表現する。これにより、更に正の訓練パッケージそれぞれにおけるインスタンスのそれぞれの重みに基づいてテストパッケージにおけるテストインスタンスのそれぞれのソートスコアを取得する。これにより、正の訓練パッケージにおける訓練インスタンスのそれぞれにより提供された情報が十分に利用され、検索の性能の向上に寄与する。
【００１４】
以下の明細書において本発明の実施例のその他の側面が提供される。ここで、詳細な説明は、本発明の実施例の好適な実施例を十全に開示するためのものであって、限定するものではない。
【図面の簡単な説明】
【００１５】
以下に、具体的な実施例を用いて、図面を参照しながら本発明の実施例の前記及びその他の目的と利点を更に説明する。図面において、同一又は対応する技術的特徴又は部品は、同一又は対応する符号で示される。
【図１】本発明による実施例により提供される方法を示すフローチャートである。
【図２】本発明による実施例により提供される別の方法を示すフローチャートである。
【図３】本発明による実施例により提供される第１の装置を示す模式図である。
【図４】本発明による実施例により提供される第２の装置を示す模式図である。
【図５】本発明による実施例により提供される第３の装置を示す模式図である。
【図６】本発明による実施例により提供される第４の装置を示す模式図である。
【図７】本発明による実施例により採用される情報処理装置のパーソナルコンピュータの模式的な構造を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下に、図面を参照して本発明の実施例を説明する。
【００１７】
理解を容易にするために、以下に、先ず本発明の実施例に係る幾つかの概念(訓練パッケージ、訓練インスタンス、正の訓練パッケージ、負の訓練パッケージ、正のインスタンス、負のインスタンス、テストパッケージ、テストインスタンスを含む)を紹介する。
【００１８】
まず、マルチインスタンス学習の枠組みにおいては、画像のそれぞれが一つのパッケージと見なされ、画像における領域のそれぞれが一つのインスタンスと見なされる。なお、検索シードであるサンプル画像が複数の領域に分割された後に、領域のそれぞれが訓練インスタンスと呼ばれ、一つのサンプル画像における全ての訓練インスタンスが一つの訓練パッケージを構成する。言い換えれば、一つのサンプル画像が一つの訓練パッケージに対応し、一つの訓練パッケージに複数の訓練インスタンスが含まれる。
【００１９】
なお、訓練インスタンスには正のインスタンスと負のインスタンスとが含まれる。正のインスタンスはユーザのルックアップ語義〔検索意図／検索対象〕を表現可能なもの、負のインスタンスはユーザのルックアップ語義を表現不可なものである。訓練パッケージは正の訓練パッケージと負の訓練パッケージに分けることができる。正の訓練パッケージは少なくとも一つの正のインスタンスを含むものである。負の訓練パッケージに含まれるインスタンスの全ては負のインスタンスである。例えば、ユーザがトラのある画像を検索しようとする場合に、提供されるサンプル画像がトラのある画像である場合もあるが、当該画像において更に幾つかの背景、例えば木、芝生等を含む可能性もある。つまり、当該サンプル画像は、一部の領域のみに本当にトラが表示され、別の一部の領域には木、芝生等が表示される。このように、当該サンプル画像に対して領域分割を行う際に、幾つかの領域にトラのパターンが表示される一方、幾つかの領域には木、芝生等だけが表示されるような場合もある。ユーザのルックアップ語義〔検索意図／検索対象〕は、トラのある画像を探索すべきであるため、当該サンプル画像について、トラのパターンのある領域に対応するインスタンスが正のインスタンスであり、木、芝生等のある領域に対応するインスタンスが負のインスタンスである。当該サンプル画像に対応する訓練パッケージは、正のインスタンスと負のインスタンスの両方を含むため、当該訓練パッケージが正の訓練パッケージである。当該サンプル画像は正のサンプル画像と呼ばれても良い。ユーザが検索しようとするものがトラのある画像であるが、提供されるサンプル画像に含まれるものが全て木、芝生等のパターンである場合に、当該サンプル画像を分割した全てのインスタンスは、ユーザのルックアップ語義〔検索意図／検索対象〕を表現不可なものとなり、負のインスタンスに該当する。それに対して、当該サンプル画像に対応する訓練パッケージも負の訓練パッケージであり、当該サンプル画像は負のサンプル画像と呼ばれても良い。
【００２０】
サンプル画像は、検索を開始する際にユーザにより提供されるものであっても良く、検索中に検索システムの提示でユーザにより選択されるものであっても良い。サンプル画像は複数あっても良い。更に、正のサンプル画像だけではなく、負のサンプル画像も提供されても良い。それと共に、ユーザはシステムにどれが正のサンプル画像であるか、どれが負のサンプル画像であるかを通知すべきである。それに対して、検索システムがサンプル画像に対して領域分割を行った後に、どの訓練パッケージが正のものであるか、どの訓練ペッケージが負のものであるかを了解することもできる。しかし、システムは、正の訓練パッケージにおけるインスタンスを取得した直後には、正の訓練パッケージにおいてどれが正のインスタンスであるか、どれが負のインスタンスであるかを知らず、解析処理をしたうえでインスタンスのレベルの情報を得なければならない。従って、サンプル画像は訓練画像と呼ばれる。即ち、画像検索を行うために、まずサンプル画像におけるインスタンスに基づいて訓練を行って使用可能な情報を取得する必要がある。これにより、更に後続の検索処理を完成させることができる。
【００２１】
検索システムは、画像データベースからユーザのルックアップ語義に該当する画像を選択する。なお、画像データベースには各種の画像が含まれている。これらの画像はテスト画像である。マルチインスタンスによる画像検索においては、テスト画像に領域分割を行う必要もある。分割した領域はテストインスタンスと呼ばれる。それに対して、一つのテスト画像内のテストインスタンスが一つのテストパッケージを構成する。
【００２２】
以下に本発明による実施例に提供される画像検索方法について詳細に説明する。
【００２３】
図１を参照すると、本発明による実施例により提供される、マルチインスタンス学習による検索方法は、以下のようなステップを含む。
【００２４】
Ｓ１０１：訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得する。前記訓練パッケージには正の訓練パッケージが含まれる。
【００２５】
上で説明したように、訓練パッケージはユーザにより提供されるものであっても良い。たとえば、ユーザは、画像検索を開始する際に、一つ又は複数の画像を選択してサンプル画像とすることができる。検索システムがこれらのサンプル画像に対して領域分割を行うことにより、領域のそれぞれが一つの訓練インスタンスに対応し、一つのサンプル画像が一つの訓練パッケージに対応する。本発明の実施例において、訓練パッケージには、少なくとも正の訓練パッケージが含まれる。勿論、訓練パッケージは、より良い検索結果を得るために、正の訓練パッケージだけではなく、負の訓練パッケージを含んでも良い。つまり、ユーザはサンプル画像を提供する時に、正のサンプル画像だけではなく、負のサンプル画像を提供することもできる。
【００２６】
Ｓ１０２：前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成する。当該重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。
【００２７】
本発明の実施例においては、正の訓練パッケージから限定された数量の正のインスタンスを選択することなく、正の訓練パッケージにおける訓練インスタンス毎に重みを生成する。当該重みは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。ここでは、本発明の実施例において、当該重みの絶対的な大きさは、前記のユーザのルックアップ語義を表現可能な度合いを表すことができる。つまり、正の訓練パッケージにおけるあるインスタンスが確かに正のインスタンスであれば、そのパッケージに対して生成される重みは負のインスタンスの重みより大きくなり、且つその重みそのものが正の値である。
【００２８】
Ｓ１０３：訓練パッケージ及びテストパッケージにおける全てのインスタンスに対して、前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて各テストインスタンスのソートスコア〔順位付けに使われるスコア〕を取得する。
【００２９】
正の訓練パッケージにおける訓練インスタンスに対してそれぞれの重みを取得した後に、訓練パッケージ及びテストパッケージにおける全てのインスタンスに対して、全てのインスタンスの間の類似度及び前記正の訓練パッケージにおける各訓練インスタンスの重みに基づいて各テストインスタンスのソートスコアを取得することができる。即ち、正の訓練パッケージにおける各インスタンスの重みは、テストパッケージにおけるテストインスタンスについてソートスコアを算出する過程に応用される。
【００３０】
言い換えれば、一般的な検索方法は、正の訓練パッケージから幾つかの情報を取得した後に、これらの情報を用いてテストパッケージからユーザのルックアップ語義〔検索意図／検索対象〕を表現するパッケージを検索するものである。これらの情報は、例えばインスタンスのソートスコアである。従来の方法においては、ソートスコアは相対的な値であり、インスタンスがユーザのルックアップ語義に合致する度合いを直接に表現することができない。本発明の実施例においては、前記ソートスコアの代わりに、正の訓練パッケージにおける各インスタンスの重みを用いることにより、インスタンスがユーザのルックアップ語義に合致する度合いを直接に表現することができる。
【００３１】
Ｓ１０４：テストパッケージにおける各テストインスタンスのソートスコアに基づいて各テストパッケージのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定する。
【００３２】
各テストインスタンスのソートスコアが取得された後に、テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを特定することができる。例えば、あるテストパッケージについて、該テストパッケージ中の各テストインスタンスのソートスコアを平均した値を当該テストパッケージのソートスコアとすることができる。勿論、一つのテストパッケージにおいて一般的に一つ又は少数のインスタンスのみが正のインスタンスである可能性があるため、前記の平均値を取る方法を採用してテストパッケージのソートスコアを取得すれば、テストパッケージのソートスコアが低くなる恐れがある。テストパッケージのソートスコアの適正性を向上させるために、当該テストパッケージにおける各テストインスタンスのソートスコアの最大値を当該テストパッケージのソートスコアとしても良い。
【００３３】
各テストパッケージのソートスコアを取得した後に、それに基づいてユーザに検索結果を提供することができる。例えば、ソートスコアの順位が上位の予め設けられた数のテストパッケージに対応する画像をユーザに返してもよいし、あるいは、ソートスコアに従って各テストパッケージをソートした後に、当該順序に従ってテストパッケージに対応する画像をユーザに順次提供する等のようにしても良い。
【００３４】
要するに、画像検索を行う過程において、正の訓練パッケージにおける訓練インスタンス毎に重みを生成することができる。当該重みの絶対的な大きさは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。このように、最後にテストパッケージにおける各テストインスタンスのソートスコアを算出する際に、正の訓練パッケージにおける訓練インスタンスに対して、それぞれの重みをその初期ラベルとし、最終的に各テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを取得して検索結果を与えることができる。以上のように、本発明の実施例において、正の訓練パッケージから限定された数量の正のインスタンスを選択することを意図することなく、正の訓練パッケージにおけるインスタンス毎にそれぞれの重みを算出し、当該重みの絶対的な大きさで各インスタンスとユーザのルックアップ語義との一致性を表すことにより、各正の訓練パッケージにおける各インスタンスの重みに基づいてテストパッケージにおける各テストインスタンスのソートスコアを取得する。このように、正の訓練パッケージにおける各訓練インスタンスにより提供される情報が十分に利用されることにより、検索の性能が向上される。
【００３５】
具体的に実現するにあたって、正の訓練パッケージにおける訓練インスタンス毎に前記重みを生成する方法は多種ある。以下に一つの実現手段について詳細に説明する。図２を参照すると、以下のようなステップを含んでも良い。
【００３６】
Ｓ２０１：正の訓練パッケージにおける訓練インスタンスの初期重みを取得する。
【００３７】
なお、正の訓練パッケージにおける訓練インスタンスの初期重みは、予めプロファイルに設定可能である。これにより、プロファイルを読み取る手段により、システムに当該初期重みを取得させることができる。例えば、統一的に１０に設置しても良い(勿論その他の値であっても良いが、一般的に正の値である)。
【００３８】
Ｓ２０２：訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズム（後述）を採用して学習を行って、各訓練インスタンスのソートスコアを取得する。
【００３９】
訓練パッケージ及び訓練インスタンスが取得された後に、グラフによるアルゴリズムを採用して学習を行って各訓練インスタンスのソートスコアを取得することができる。なお、学習中に主に訓練インスタンス同士の類似度に基づいてグラフによる学習を行う。
【００４０】
ここで、グラフによるアルゴリズムに基づいて学習を行うことによって各訓練インスタンスのソートスコアを取得する過程は、従来の技術であり、本発明の要点ではない。従って、ここでは簡単に説明するにとどめる。
【００４１】
以下の方法でグラフによる学習を行うことができる。即ち、まず重み付きグラフを構築する。同グラフにおけるノードは訓練パッケージにおける全ての訓練インスタンスに対応する。つまり、２つの訓練パッケージがあり、訓練パッケージのそれぞれに五つの訓練インスタンスがあることを仮定すれば、構築されたグラフには１０個のノードが存在する。同グラフにおける辺〔エッジ〕の重みが、その辺と接続する２つのノード同士の類似度を表す。次に、グラフによるアルゴリズムを採用して学習を行う。アルゴリズムが終了した時点で、それぞれの訓練インスタンスが一つのソートスコアに対応することができる。
【００４２】
なお、ノード間の類似度を算出する際、各訓練インスタンスから視覚特徴(一般的にベクトルの形式である)をそれぞれ抽出した後に、ベクトル計算の方法で二つずつの間の距離を算出することができる。ここでは、距離が小さいほど、類似度が高くなる。逆に、距離が大きいほど、類似度が低くなる。勿論、実際の応用において、視覚特徴を抽出する以外に、別途に各訓練インスタンスに関する特徴、例えば描画情報等を取得することもできる。また、これらの情報を訓練インスタンス同士の類似度の算出に加味することもできる。
【００４３】
以上に説明したように重み付きグラフを構築することは形象による説明方法である。コンピュータシステムにとっては、当該重み付きグラフに対応するデータはn×nの行列Ｓである。なお、ｎは訓練インスタンスの総数である。つまり、前記の例において、１０個の訓練インスタンスがあれば、当該行列は１０行１０列を有し、i行目のj列目の要素Sijがi個目の訓練インスタンスとj個目の訓練インスタンスとの間の類似度に対応する。また、更に当該行列に対して行による正規化処理を行うこともできる。
【００４４】
グラフによるアルゴリズムは多種の具体的な実現方法がある。例えば、一つの実施形態においては、以下のような方法で行うことができる。即ち、まず全ての訓練インスタンスに初期ラベルを設定する。例えば、訓練パッケージが全て正の訓練パッケージであれば、全ての訓練インスタンスの初期ラベルを１とすることができる。訓練パッケージに正の訓練パッケージと負の訓練パッケージとの両方があれば、正の訓練パッケージにおける全ての訓練インスタンスの初期ラベルを１とし、負の訓練パッケージにおける全ての訓練インスタンスの初期ラベルを−１とすることができる。次に、前に構築された重み付きグラフ上に初期ラベルをグローバルな安定性を有する状態になるまで伝送する。最終的にそれぞれの訓練インスタンスのソートスコアを取得することができる。コンピュータシステムにとっては、以上のような重み付きグラフ上でラベルを伝送する過程は、以下のような反復的な公式に従って達成することができる。
f(t＋1)＝αSf(t)＋(1−α)y (1)
ただし、Ｓは前記の構築されたグラフに対応する正規化行列である。ｙは各訓練インスタンスの初期ラベルからなるラベルベクトルである。例えば、一つの正の訓練パッケージと一つの負の訓練パッケージがあり、訓練パッケージのそれぞれに五つのインスタンスがあるとすれば、ｙは(1,1,1,1,1,−1,−1,−1,−1,−1)Tとなる。α（0＜α＜1）は線形的な組合せ係数である。f(t)もベクトルであり、その中の要素数は訓練インスタンスの数と同じであり、各要素がｔ回目の反復工程後の各訓練インスタンスが対応するラベルの値に対応する。例えば、f(1)は１回目の反復工程後の各訓練インスタンスのラベルからなるベクトルを表す。初期状態において、f(0)は任意の値を取っても良く、一つの具体的な実施形態ではf(0)をｙに等しくすることもできる。
【００４５】
つまり、(１)式を利用して複数回の反復工程を行うことができる。反復的な過程が収束することは、前記重み付きグラフ上で伝送する際にグローバルな安定性を有する状態になることに対応し、その後に対応するf(t)を取得し、その中の各要素の値に基づいて各訓練インスタンスのソートスコアを取得することができる。なお、具体的な実現において、以下の方法で反復的な過程が収束したか否かを判断することができる。即ち、f(t)とf(t−1)とが非常に接近したか否かを判断する(両者の距離を算出して、ある閾値と比較することができる)。この判断の結果が肯定の場合に収束したと判断し、反復的な過程を終了すれば良い。勿論、反復回数等を予め設ける方法で実現しても良く、ここでは詳細な説明を省略する。
【００４６】
なお、前記(１)式を採用して反復処理を行うことは、下記の最小化すべき関数を最小化する必要があるからである。
【数１】
【００４７】
上記の最小化すべき関数は二つの拘束関係からなる。一つ目の拘束関係
【数２】
は重み付きグラフにより得られた平滑性拘束条件（smoothness constraint）である。fi、fjはfの中のi項目及びj項目である。即ち、類似した訓練インスタンスに対応するソートスコアの差異は大きくないことが期待される。二つ目の拘束関係
【数３】
は、初期ラベルによるフィッテング〔適合〕拘束条件（fitting constraint）である。即ち、最終的なソートスコアと初期ラベルとの差異が大きくないことが期待される。ただし、μは2つの項目の重要性のバランスを取るための重みである。(１)式におけるαはμで算出することができる。即ちα＝1／(1＋μ)。このように、上記の関数を最適化することにより、(１)式における反復的な式を得ることができる。言い換えれば、(１)式を用いて反復を行うことにより、最終的なソートスコアに(２)式における拘束条件を満足させることができる。そして、このように算出されたソートスコアの高さは、対応する訓練インスタンスがユーザのルックアップ語義〔検索意図、検索対象〕を表現可能な度合いを表すことができる。即ち、訓練インスタンスのソートスコアが高いほど、ユーザのルックアップ語義を表すことができる。
【００４８】
ここで、具体的に実現する際、訓練インスタンスの数は一般的に大きくないため、(１)式の解析的な解を直接に用いて最終的な結果を取得しても良い。
f*＝(1−α)(I−αS)-1y （3）
ただし、Ｉは単位行列である。
【００４９】
ステップＳ２０３：訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセット（後述）を特定し、各訓練インスタンスについて、正の近隣するインスタンスセットにおける各訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更し、これにより正の訓練パッケージにおける各訓練インスタンスの最終重みを取得する。なお、前記訓練インスタンスの正の近隣するインスタンスセットは、当該訓練インスタンスと予め設けられた類似関係を有する正の訓練パッケージにおける訓練インスタンスにより構成される。
【００５０】
ステップＳ２０２において、各訓練インスタンスのソートスコアを算出して各訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。しかし、本発明を実現するにあたって、当該方法により算出されたソートスコアが一般的に相対性を有する、即ち各訓練インスタンスのソートスコアの相対的な大きさが意義を有することが本発明者により発見された。例えば、前記の方法により得られたソートスコアでは、ある正の訓練パッケージにおける各訓練インスタンスのソートスコアが何れも負の値である可能性がある。なお、あるインスタンスが確かに正のインスタンスであるとすれば、そのインスタンスがソートスコアに表現される際に負のインスタンスのソートスコアよりも確かに高い可能性がある。だが、そのものが負の値であると、その絶対的な大きさはあるべき意義を失ってしまっていた。ところが、実際に正の訓練パッケージであるからには、その中の少なくとも一つの訓練インスタンスが正のインスタンスであり、正のインスタンスのソートスコアは正の値であるだろう。これこそ、後続の検索に寄与することができる。従って、当該負の値を直接に利用して後続の検索過程を行うと、検索結果の有効性を損なう恐れがある(後続の検索過程とは、訓練インスタンスに初期ラベルを付与する必要があることを指し、ステップＳ２０２に得られたソートスコアを直接に利用して値を付与すれば、正の訓練パッケージにおける正のインスタンスの初期ラベルに負の値を付与する恐れがある)。従って、本発明の実施例においては、訓練インスタンスのソートスコアが得られた後に、更なる処理が必要である。
【００５１】
前記の更なる処理を行うために、多種の方法が採用可能である。例えば、簡単には、各訓練インスタンスのソートスコアが算出された後に、正の訓練パッケージにおいて少なくとも一つの訓練インスタンスのソートスコアが正の値となるように、各ソートスコアにあるオフセットを加える。これにより、一つの正の訓練パッケージにおける全ての訓練インスタンスのソートスコアが何れも負の値であることを回避することができる。
【００５２】
あるいは、本発明の実施例において、以下のような方法を採用して前記の処理過程を実現しても良い。即ち、先ず各訓練インスタンスに対して各訓練インスタンスの正の近隣するインスタンスセットをそれぞれ探す。ある訓練インスタンスＬについて、訓練インスタンスＬの正の近隣するインスタンスセットとは、そのセットが正の訓練パッケージにおける訓練インスタンスにより構成され、且つそのセットにおける各インスタンスが当該訓練インスタンスＬとある隣接関係／類似関係を有するものである。具体的な実現においては、どのような隣接関係／類似関係を満足する必要があるかについて予め設定されていても良く、例えば二つの訓練インスタンスの間の類似度がある閾値よりも大きいか否かを簡単に設定することができる。あるいは、本発明の実施例において、ステップＳ２０２で構築された重み付きグラフ中の遷移関係に基づいて算出されても良い。
【００５３】
なお、重み付きグラフ中の遷移関係に基づいて算出する際に、ノードの間の一次又は高次の伝達関係に基づいてノード間の類似関係を特定することができる。ここで、一次の伝達関係は二つの訓練インスタンス間の類似度を指す。二次の伝達関係は、インスタンス１とインスタンス２との間に非常に高い類似度を有し、且つインスタンス２とインスタンス３との間に比較的高い類似度を有する場合に、インスタンス１とインスタンス３との類似度を直接に算出した場合にスコアが低くなっても、インスタンス１とインスタンス３がある類似関係を満足すると考えられることを指す。その他はこれによって類推すれば良い。
【００５４】
ここでは、各訓練インスタンスにそれぞれ正の近隣するインスタンスセットが見つかるわけではない。つまり、ある訓練インスタンスに対し、その正の近隣するインスタンスセットが空であっても良い。
【００５５】
本発明の実施例において、予め正の訓練パッケージにおける各訓練インスタンスの初期重みが知られている。従って、各訓練インスタンスの正の近隣するインスタンスセットが得られた後に、セット内のインスタンスの重みを調整することができる。同一の正の近隣するインスタンスセットにおける各インスタンスについて、具体的に調整を行う際に、多種の調整方針がある。例えば、一つの方針においては、各訓練インスタンスのソートスコアの高さに応じて各訓練インスタンスの調整幅を特定し、例えばソートスコアが最も高い訓練インスタンスの重みは１だけ増大し、二番目に高いものは0.8だけ増大し、三番目に高いものは0.5だけ増大する等のようにしても良い。勿論、その他の調整方針において、ソートスコアの最も高い一つの訓練インスタンスに対して調整を行っても良く、ここでは列挙しない。
【００５６】
ここで、訓練パッケージにおいて正の訓練パッケージと負の訓練パッケージとの両方がある場合に、訓練インスタンスの重みを具体的に調整する際、正の訓練パッケージにおける訓練インスタンスについては、その正の近隣するインスタンスセットにおけるインスタンスの重みを大きくする調整を行い、負の訓練パッケージにおける訓練インスタンスについては、その正の近隣するインスタンスセットにおける重みを小さくする調整を行うことができる。つまり、負の訓練パッケージにおける訓練インスタンスは、絶対に正のインスタンスではないため、正の訓練パッケージにおけるあるインスタンスがそれと類似関係を有すれば、当該正の訓練パッケージにおけるインスタンスが正のインスタンスではない可能性もあるため、その重みを小さくすることが合理的である。
【００５７】
正の訓練パッケージにおける訓練インスタンス(説明を容易にするために、正の訓練パッケージにおけるある訓練インスタンスＡを例とする)について、Ａが正のインスタンスであるか、負のインスタンスであるかについて不明であるが、正のインスタンスである可能性が存在する。従って、正の訓練パッケージにおけるその他のインスタンスがそれと類似関係を有し、即ちこれらのその他のインスタンスが訓練インスタンスＡの正の近隣するインスタンスセットを構成する場合に、訓練インスタンスＡによりその正の近隣するインスタンスセットにおけるインスタンスの重みを大きくすることができる。その結果、二つの可能性が存在する。一つの可能性としては、当該訓練インスタンスＡが確かに正のインスタンスである場合、その正の近隣するインスタンスセットにおけるインスタンスが正のインスタンスである可能性が高いため、その重みを大きくすることが合理的である。もう一つの可能性としては、訓練インスタンスＡが正の訓練パッケージに位置するが、負のインスタンスである場合、その正の近隣するインスタンスセットにおけるインスタンスが正のインスタンスである可能性が低いため、その重みを大きくすることは一見して不合理である。しかし、ここで、全ての訓練インスタンスのそれぞれに各自の正の近隣するインスタンスセット(勿論、セットが空の場合もある)が決定されており、正の訓練パッケージにおける同一の訓練インスタンスが異なる複数の正の近隣するインスタンスセットに位置する可能性がある。従って、前記の二種目の場合において、訓練インスタンスＡの正の近隣するインスタンスセットにおけるインスタンスがある訓練インスタンスＢ又はその他のインスタンスの正の近隣するインスタンスセットに位置し、訓練インスタンスＢ又はその他のインスタンスが負の訓練パッケージにおけるインスタンスである可能性がある。従って、更にその正の近隣するインスタンスセットにおけるインスタンスの重みを小さくする操作を行うことになる。これにより、その前に大きくされた重みを小さくすることができる。つまり、正の訓練パッケージにおける訓練インスタンスは、複数回の重み調整操作が行われる可能性があり、あるものは一貫して大きくされ、あるものは一貫して小さくされ、あるものが一部的に大きくされ且つ一部的に小さくされ、最終的に正の訓練パッケージにおける各訓練インスタンスに各自の重みを有させる。
【００５８】
また、訓練パッケージを構成するものが全て正の訓練パッケージである場合に、訓練インスタンスの重みを調整する際、具体的な調整操作は重みを大きくする操作であっても良い。ここで、この場合に、大きくするという操作のみを行えるが、各訓練インスタンスのソートスコアが異なり、且つ正の近隣するインスタンスセットに訓練インスタンスのそれぞれが位置する場合も異なるため、依然として正の訓練パッケージにおける各訓練インスタンスに異なる最終的重みを有させることもできる。ここで、正の訓練パッケージのみがある場合においても、得られた最終的重みが依然として正の訓練パッケージにおける各訓練インスタンスとユーザのルックアップ語義との一致度を表現可能である。これは、前に記載された「正のインスタンス同士が一般的に類似である」という特徴により決められ、ここでは詳しく説明しない。
【００５９】
以上の方法により、正の訓練パッケージにおける各訓練インスタンスに重みを生成することができる。次に、当該重みを用いて検索を行う際に、以下のようなステップを含んでも良い。
【００６０】
Ｓ２０４：訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを取得する。なお、正の訓練パッケージにおける各訓練インスタンスの初期ラベルは前記最終的重みにより特定されたものである。
【００６１】
正の訓練パッケージにおける各インスタンスの重みが得られた後に、訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、各テストインスタンスのソートスコアを特定するように、グラフによるアルゴリズムに基づいて学習を行うことができる。なお、グラフによるアルゴリズムに基づいて学習を行う際に、ステップ２０２と同様に、先ず重み付きグラフを構築する。当該グラフにおいては、ノードが訓練パッケージ及びテストパッケージにおける全てのインスタンスに対応し、辺の重みがその辺と接続する二つのノード間の類似度を表す。ここで、図によるアルゴリズムに基づいて学習を行う際に、各インスタンスに初期ラベルを設定する必要がある(例えば、ステップＳ２０２において、正の訓練パッケージにおける全てのインスタンスの初期ラベルを１に設定し、負の訓練パッケージにおける全てのインスタンスの初期ラベルを−1に設定することができる)。本発明の実施例において、テストパッケージにおける各インスタンスにソートスコアを算出する必要がある場合に、訓練パッケージにおける正の訓練パッケージについて、ステップＳ２０３に得られた各自の最終的重みに基づいてその中のインスタンスの初期ラベルを特定することができる。
【００６２】
つまり、ステップＳ２０３で正の訓練パッケージにおける各インスタンスに対する重みをそれぞれ算出し、ステップＳ２０４で訓練パッケージ及びテストパッケージにおける全てのインスタンスに基づいてグラフによるアルゴリズムの学習を行う必要がある場合に、算出された重みに基づいて正の訓練パッケージにおける各訓練インスタンスの初期ラベルを特定することができる。例えば、ステップＳ２０３で算出された正の訓練パッケージにおける各訓練インスタンスの重みに対して直接に正規化処理を行った後に、正規化処理された値を正の訓練パッケージにおける各訓練インスタンスの初期ラベルとすることができる。
【００６３】
訓練パッケージに負の訓練パッケージがある場合、負の訓練パッケージにおける各訓練インスタンスの初期ラベルは依然として−１に設定されても良い。ステップＳ２０２と同様に、各インスタンスの初期ラベルを、グローバルな安定性を有する状態になるまで前に構築された重み付きグラフ上に伝送し、最終的に各テストインスタンスのソートスコアを得ることができる。コンピュータシステムにとっては、以上のようにラベルを重み付きグラフ上に伝送する過程は、以下の反復的な公式により完成することができる。
f(t＋1)＝Sf(t) (4)
ここで、Ｓは訓練パッケージ及びテストパッケージにおける全てのインスタンスに基づいて構築されたグラフに対応する正規化行列である。ｆ(ｔ)はベクトルであり、その中の要素数は訓練インスタンスとテストインスタンスとの数の合計値であり、各要素がｔ回目の反復工程後の各インスタンスの対応するラベルの値に対応する。例えば、ｆ(1)は１回目の反復工程後の各インスタンスのラベルからなるベクトルを表す。初期状態において、ｆ(0)は各インスタンスに対応する初期ラベルからなるベクトルであっても良い。反復過程が終了した時に、ｆ(ｔ)における各要素の値を各インスタンスのソートスコアとすることができる。
ここで、(4)式を用いて反復処理を行う際に、一回の反復工程が終了するたびに、ｆ(ｔ)のうちの各訓練インスタンスのラベルに新たな初期値を付与する。つまり、反復の過程において、訓練インスタンスのラベルはそのままで保持される、言い換えると、常に初期ラベルと等しい(ただし、正の訓練パッケージにおける訓練インスタンスのラベルが常にその前に算出された重み又は正規化処理された重みと等しい一方、負の訓練パッケージにおける訓練インスタンスのラベルは常に付与された初期値、例えば−１等と等しい)。勿論、一回の反復工程が終了するたびに、テストインスタンスのラベルが変わることになる。ところが、テストパッケージにおける各テストインスタンスの初期ラベルは任意に設定可能である。これは、最終的な算出結果がテストインスタンスの初期ラベルの値と関係ないからである。
【００６４】
また、ここで、前に説明したのと同様に、反復の方法で最終的なソートスコアを取得することなく、(4)式の解析的な解を直接に用いて最終的な結果を取得しても良い。その結果は、反復によるものと同じである。勿論、テストインスタンスの数が一般的に多くなると、解析的な解は、行列の逆を求める演算に係るため、反復の方法と比べて演算の複雑性が高くなる。また、ステップＳ２０４におけるグラフによる学習について、詳しく説明していない部分については前の説明を参照することができ、ここでは詳しく説明しない。
【００６５】
Ｓ２０５：テストパッケージにおける各テストインスタンスのソートスコアに基づいて各テストパッケージのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定する。
【００６６】
本発明の実施例は、提供されたマルチインスタンス学習による検索方法に対応して、マルチインスタンス学習による検索システムを提供する。図３を参照すると、当該システムは以下のものを備える。
【００６７】
訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得するように構成される取得手段３０１を備える。前記訓練パッケージには正の訓練パッケージが含まれる。
【００６８】
前記正の訓練パッケージにおける訓練インスタンスごとに重みを生成するように構成される訓練インスタンス重み生成手段３０２を備える。当該重みの絶対的な大きさは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。
【００６９】
訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて各テストインスタンスのソートスコアを取得するように構成されるテストインスタンスソートスコア取得手段３０３を備える。
【００７０】
テストパッケージにおける各テストインスタンスのソートスコアに基づいて各テストパッケージのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される検索結果特定手段３０４を備える。
【００７１】
なお、図４を参照すると、正の訓練パッケージにおける訓練インスタンスに重みを具体的に生成するにあたり、訓練インスタンス重み生成手段３０２は以下のものを備えても良い。
【００７２】
正の訓練パッケージにおける訓練インスタンスの初期重みを知るように構成される初期重みラーニングサブ手段３０２１を備える。
【００７３】
訓練インスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各訓練インスタンスのソートスコアを取得するように構成される訓練インスタンスソートスコア取得サブ手段３０２２を備える。
【００７４】
訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセットを特定し、各訓練インスタンスに対して、正の近隣するインスタンスセットにおける各訓練インスタンスのソートスコアに基づいて、正の訓練パッケージにおける各訓練インスタンスの最終的な重みを取得するように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される重み補正サブ手段３０２３を備える。なお、前記訓練インスタンスの正の近隣するインスタンスセットは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスにより構成される。
【００７５】
具体的に実現する際、訓練パッケージに負の訓練パッケージが含まれても良い。これに対して、重み補正サブ手段３０２３は以下のものを備えても良い。
【００７６】
正の訓練パッケージにおける各訓練インスタンスに対し、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくするように構成される重み増大サブ手段を備える。
【００７７】
負の訓練パッケージにおける各訓練インスタンスに対し、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくするように構成される重み減少サブ手段を備える。
【００７８】
具体的には、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアを補正する際、正の近隣するインスタンスセットにおいてソートスコアが最も大きい訓練インスタンスのソートスコアのみを、大きくする補正又は小さくする補正を行っても良い。この時に、重み補正サブ手段３０２３は、具体的に、正の近隣するインスタンスセットにおけるソートスコアが最も大きい訓練インスタンスの重みを変更するように構成することができる。
【００７９】
具体的には、正の近隣するインスタンスセットを決定する際、多種の方法を採用しうる。その一つの方法としては、グラフによるアルゴリズムに基づいて学習を行う過程に構築された重み付きグラフにおける各ノードの一次又は高次の伝達関係に基づいて、訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセットを特定することができる。つまり、図５を参照すると、重み補正サブ手段３０２３は以下のものを備えても良い。
【００８０】
グラフによるアルゴリズムに基づいて学習を行う過程で構築された重み付きグラフにおける各ノードの一次又は高次の伝達関係に基づいて、訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセットを特定するように構成される正の近隣するインスタンスセット特定サブ手段３０２３１を備える。前記重み付きグラフにおいて、ノードは訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みはその辺と接続する2つのノードの間の類似度に対応する。
【００８１】
各訓練インスタンスに対し、正の近隣するインスタンスセットにおける各訓練インスタンスのソートスコアに基づいて、正の訓練パッケージにおける各訓練インスタンスの最終的な重みを得るように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される補正サブ手段３０２３２を備える。
【００８２】
具体的に実現する際に、テストインスタンスソートスコア取得手段３０３は、具体的に、訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを得るように構成することができる。なお、正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる。
【００８３】
テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを特定する際には、多種の方法を採用できる。その一つの方法では、図６を参照すると、検索結果特定手段３０４は以下のものを備えても良い。
【００８４】
テストパッケージにおける各テストインスタンスが対応するソートスコアの最大値を当該テストパッケージのソートスコアとするように構成されるテストパッケージソートスコア特定サブ手段３０４１を備える。
【００８５】
前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される特定サブ手段３０４２を備える。
【００８６】
本発明による実施例により提供される前記システムによれば、画像検索を行う過程において、正の訓練パッケージにおけるそれぞれの訓練インスタンスに重みを生成することができる。当該重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。これにより、最後にテストパッケージにおける各テストインスタンスのソートスコアを算出する時に、正の訓練パッケージにおける訓練インスタンスに対し、それぞれの重みをその初期ラベルとし、最終的に各テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを取得して検索結果を与えることができる。従って、本発明の実施例において、正の訓練パッケージから有限な数量の正のインスタンスを選択することを意図せず、正の訓練パッケージにおける各インスタンスにそれぞれの重みを算出し、当該重みの絶対的な大きさで各インスタンスとユーザのルックアップ語義との一致度を表現する。これにより、更に各正の訓練パッケージにおける各インスタンスの重みに基づいてテストパッケージにおける各テストインスタンスのソートスコアを取得する。これにより、正の訓練パッケージにおける各訓練インスタンスにより提供された情報が十分に利用され、検索の性能の向上に寄与する。
【００８７】
ここで、前記システムの実施例は、前記方法の実施例に基づいて説明されたものである。その中の詳細説明のない部分は、方法の実施例の部分の説明を参照することができ、ここでは詳しく説明しない。
【００８８】
また、前記一連の処理及び装置は、ソフトウェア及び/又はファームウェアにより実現可能である。ソフトウェア及び/又はファームウェアにより実現される場合に、記憶媒体又はネットワークから、専用のハードウェア構成を有するコンピュータ、例えば図７に示された汎用のパーソナルコンピュータ７００へ、当該ソフトウェアを構成するプログラムをインストールする。当該コンピュータは、各種のプログラムがインストールされている場合に、各機能などを実行することができる。
【００８９】
図７において、中央処理装置（CPU）７０１は、読取専用メモリ（ROM）７０２に記憶されたプログラム又は記憶部７０８からランダムアクセスメモリ（RAM）７０３にロードされたプログラムに基づいて各種の処理を実行する。RAM７０３には、必要に応じてCPU７０１が各種の処理等を実行するために必要なデータも記憶される。
【００９０】
CPU７０１、ROM７０２とRAM７０３はバス７０４を介して互いに接続されている。入力／出力インタフェース７０５もバス７０４に接続されている。
【００９１】
キーボード、マウス等を含む入力部７０６と、ディスプレイ、例えばブラウン管（CRT）、液晶ディスプレイ（LCD）等とスピーカ等を含む出力部７０７と、ハードディスク等を含む記憶部７０８と、ネットワークインターフェースカード、例えばLANカード、モデム等を含む通信部７０９とは、入力／出力インタフェース７０５に接続されている。通信部７０９がネットワーク、例えばインターネットを経由して通信処理を実行する。
【００９２】
必要に応じて、入力／出力インタフェース７０５にはドライブ７１０も接続される。磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等のような取り外し可能な媒体７１１が、必要に応じてドライブ７１０に装着可能である。これにより、読み出されたコンピュータプログラムは必要に応じて記憶部７０８にインストールされる。
【００９３】
ソフトウェアで前記一連の処理を実現する場合、ネットワーク、例えばインターネット、又は記憶媒体、例えば取外し可能な媒体７１１からソフトウェアを構成するプログラムをインストールする。
【００９４】
このような記憶媒体は、図７に示された、その中にプログラムが記憶されており、デバイスから離れて配送されてユーザにプログラムを提供する取り外し可能な媒体７１１に限定されないことを、当業者は理解すべきである。取り外し可能な媒体７１１として、例えば、磁気ディスク（フロッピーディスク(登録商標)を含む）、光ディスク（コンパクトディスクリードオンリーメモリ（CD−ROM）やディジタルヴァーサタイルディスク（DVD）を含む）、光磁気ディスク（ミニディスク(MD)（登録商標）含む）及び半導体メモリを含む。または、記憶媒体は、ROM７０２、記憶部７０８に含まれるハードディスクであって、プログラムが記憶されており、且つそれらを含むデバイスと一緒にユーザに配送されるハードディスクなどであっても良い。
【００９５】
また、前記一連の処理のステップを実行する際、そのまま説明された順序に従い、時間順で実行しても良いが、時間順に限定されない。幾つかのステップは並行で、又は互いに個別で実行しても良い。
【００９６】
本発明及びその利点を詳細に説明したが、付属の特許請求の範囲に限定された本発明の要旨と範囲から逸脱しない限り、各種の変更、置換及び変換が可能である。そして、本発明の実施例の用語「含む」、「有する」、又は如何なる他の同等の表現は、非排他的な包含を意図しており、一連の要素を含む過程、方法、物品又は装置がそれらの要素を含むだけではなく、明確に列挙されていない他の要素、又はこのような過程、方法、物品又は装置の固有要素も含むことも許容する。更なる限定のない場合に、語句「一つの…を含む」により限定された要素は、前記要素を含む過程、方法、物品又は装置において更に別の同一の要素が存在することを排除しない。
【００９７】
以上の実施例を含む実施形態について、さらに以下の付記が開示される。
（付記１）マルチインスタンス学習による検索方法であって、
正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、
訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得し、及び
テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定することを含み、
前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、ことを特徴とする方法。
（付記２）前記の、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成することは、
正の訓練パッケージにおける訓練インスタンスの初期重みを知り、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得し、及び
訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定し、訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得するように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することを含み、
前記訓練インスタンスの正の近隣するインスタンスセットは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスにより構成される、ことを特徴とする付記１に記載の方法。
（付記３）前記訓練パッケージに負の訓練パッケージが更に含まれ、前記の、訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
正の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくし、及び
負の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくすることを含む、を特徴とする付記２に記載の方法。
（付記４）前記の、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
正の近隣するインスタンスセットにおけるソートスコアの最も大きい訓練インスタンスの重みを変更することを含む、付記２又は３に記載の方法。
（付記５）前記の、訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定することは、
グラフによるアルゴリズムに基づいて学習を行う過程に構築された重み付きグラフにおけるノードのそれぞれの一次又は複数次の伝達関係に基づいて、訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定することを含み、
前記重み付きグラムにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みがそれと接続する2つのノードの間の類似度に対応する、付記２に記載の方法。
（付記６）前記の、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、全てのインスタンス同士の類似度及び前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みに基づいてテストインスタンスのソートスコアを取得することは、
訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、全てのインスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行ってテストインスタンスのそれぞれのソートスコアを取得することを含み、
正の訓練パッケージにおける訓練インスタンスのそれぞれの初期ラベルはそれぞれの重みにより決められる、付記１に記載の方法。
（付記７）前記の、テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定することは、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとすることを含む、付記１に記載の方法。
（付記８）マルチインスタンス学習による検索システムであって、
正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得するように構成される取得手段と、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成される訓練インスタンス重み生成手段と、
訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得するように構成されるテストインスタンスソートスコア取得手段と、
テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される検索結果特定手段とを備え、
前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、ことを特徴とするシステム。
（付記９）前記訓練インスタンス重み生成手段は、
正の訓練パッケージにおける訓練インスタンスの初期重みを知るように構成される初期重みラーニングサブ手段と、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得するように構成される訓練インスタンスソートスコア取得サブ手段と、
訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定し、訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得するように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される重み補正サブ手段とを備え、
前記訓練インスタンスの正の近隣するインスタンスセットは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスにより構成されることを特徴とする付記８に記載のシステム。
（付記１０）前記訓練パッケージに負の訓練パッケージが更に含まれ、前記重み補正サブ手段は、
正の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくするように構成される重み増大サブ手段と、
負の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくするように構成される重み減少サブ手段と、を備える、ことを特徴とする付記９に記載のシステム。
（付記１１）前記重み補正サブ手段は、正の近隣するインスタンスセットにおけるソートスコアの最も大きい訓練インスタンスの重みを変更するように構成される、ことを特徴とする付記９又は１０に記載のシステム。
（付記１２）前記重み補正サブ手段は、
グラフによるアルゴリズムに基づいて学習を行う過程に構築された重み付きグラフにおけるノードのそれぞれの一次又は複数次の伝達関係に基づいて、訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定するように構成される正の近隣するインスタンスセット特定サブ手段と、
訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得するように、正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される補正サブ手段とを備え、
前記重み付きグラムにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みがそれと接続する2つのノードの間の類似度に対応する、ことを特徴とする、付記９に記載のシステム。
（付記１３）前記テストインスタンスソートスコア取得手段は、具体的に、訓練パッケージ及びテストパッケージにおける全てのインスタンスについて、全てのインスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行ってテストインスタンスのそれぞれのソートスコアを取得するように構成され、
正の訓練パッケージにおける訓練インスタンスのそれぞれの初期ラベルはそれぞれの重みにより決められる、ことを特徴とする、付記８に記載のシステム。
（付記１４）前記検索結果特定手段は、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとするように構成されるテストパッケージソートスコア特定サブ手段と、
前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される特定サブ手段とを備える、ことを特徴とする、付記８に記載のシステム。
【００９８】
（付記１′）複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索方法であって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該方法は、コンピュータが、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得し、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得し、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算し、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定することを含み、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、
ことを特徴とする方法。
（付記２′）前記の、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成することは、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得し、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得し、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得することを含み、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、ことを特徴とする付記１′に記載の方法。
（付記３′）前記一つまたは複数の訓練パッケージに負の訓練パッケージが更に含まれ、前記の、各訓練インスタンスについて前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくし、
前記負の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくすることを含む、
ことを特徴とする付記２′に記載の方法。
（付記４′）前記の、前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアのうち最も大きい訓練インスタンスの重みを変更することを含む、
ことを特徴とする付記２′又は３′に記載の方法。
（付記５′）前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することは、
グラフによるアルゴリズムに基づいて学習を行う過程で構築された重み付きグラフにおけるノードに対応する訓練インスタンス間の一次又は高次の伝達関係に基づく類似度に基づいて、前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することを含み、
前記重み付きグラフにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みが該辺と接続する2つのノードの間の類似度に対応する、
ことを特徴とする付記２′に記載の方法。
（付記６′）前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度及び前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得することは、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを取得することを含み、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする付記１′に記載の方法。
（付記７′）各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算することは、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとすることを含む、
ことを特徴とする付記１′に記載の方法。
（付記８′）複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索システムであって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該システムは、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得するように構成された取得手段と、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成された訓練インスタンス重み生成手段と、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得するように構成されたテストインスタンスソートスコア取得手段と、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算する計算手段と、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定するように構成された検索結果特定手段とを備え、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、ことを特徴とするシステム。
（付記９′）前記訓練インスタンス重み生成手段は、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得するサブ手段と、
訓練インスタンス同士の類似度に基づいて、訓練インスタンスのそれぞれのソートスコアを取得するサブ手段と、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得する重み補正サブ手段とを備え、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、
ことを特徴とする付記８′に記載のシステム。
（付記１０′）前記テストインスタンスソートスコア取得手段は、前記訓練パッケージ及び前記テストパッケージにおける全てのインスタンスについて、全てのインスタンス間の類似度に基づいて、各テストインスタンスのソートスコアを取得するように構成され、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする付記８′に記載のシステム。
【技術分野】
【０００１】
本発明は、一般的に画像処理技術分野に関し、特にマルチインスタンス学習による検索方法及びシステムに関する。
【背景技術】
【０００２】
デジタル画像数の急速な増大につれて、高速で且つ有効な画像検索技術が求められている。その技術は人間の日常生活、例えばデジタル写真管理、オンラインショッピング、リモート教育等に多く適用することができる。
【０００３】
画像検索技術は、主にテキストによる画像検索技術とコンテンツ〔内容〕による画像検索技術とを含む。コンテンツによる画像検索技術は、テキストによる画像検索技術と異なり、画像上の文字描画に基づいてインデックスを生成することなく、画像毎の視覚コンテンツ特徴、例えば色合い、テクスチャ、形状等を自動的に抽出し、そうした視覚コンテンツ特徴に基づいてインデックスを生成する。検索を行う際に、ユーザは代表的な一つ又は複数のサンプル画像を選択してルックアップを構築した後に、検索システムにサンプル画像の視覚コンテンツ特徴と類似する画像を探索させることができる。
【０００４】
領域特徴が人間の視覚感知によく合致し、且つ領域特徴による検索技術で一般的により良い検索性能を得られるため、領域特徴による画像検索はコンテンツによる画像検索の重要な手法の一つになる。領域特徴による検索とは、画像分割技術で画像において意味のある領域を抽出した後に、領域ごとに局所特徴を用いて描画を行い、各領域特徴を統合して画像の特徴描画を取得し、これら特徴に基づいて検索アルゴリズムを設計して検索を行うことである。マルチインスタンス学習は、領域による画像検索に適用されて成功を収めている効率的なアルゴリズムである。
【０００５】
マルチインスタンス学習による画像検索においては、それぞれの画像がパッケージとされ、画像における領域のそれぞれがインスタンスとされる。データセットは種類の標識を有するパッケージにより構成され、それぞれのパッケージには種類の標識を有しない若干のインスタンスが含まれる。マルチインスタンスの基本的な出発点として、少なくとも一つの正のインスタンス（後述）を含むパッケージであれば、当該パッケージが正の訓練〔トレーニング〕パッケージと標識される。その一方、パッケージ中のインスタンスが全て負のものであれば、当該パッケージが負の訓練パッケージと標識される。
【０００６】
負の訓練パッケージは、その中に含まれるインスタンスが必ず負のものである。正の訓練パッケージは、その中に正のインスタンスと負のインスタンスの両方が含まれてもよい。更に、システムはどのインスタンスが正であるか、どのインスタンスが負であるかは知らない。従って、マルチインスタンス学習において、最も重要な問題は、どのように正の訓練パッケージにおけるインスタンスにより提供される情報を用いて検索を行うかということにある。
【０００７】
従来の技術におけるアルゴリズムは、一般的に好適な方法を用いて、正の訓練パッケージに含まれる正のインスタンスを選択することを意図する。この方法は、少なくとも、予め選択すべきインスタンスの数を決定しておく必要があるという欠点がある。例えば、それぞれの正の訓練パッケージから一つの正のインスタンスしか選択できないという制限がある場合に、一つのインスタンスのみが最終的な検索に関係することになるが、実際に正の訓練パッケージに含まれる正のインスタンスが一つだけではないことがよくある。その中の一つのインスタンスのみを用いて検索を行うと、正の訓練パッケージにおけるインスタンスにより提供される情報が十分に利用できず、検索の性能が制限されることになる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施例は、上記の事情に鑑み、正の訓練パッケージにおけるインスタンスにより提供される情報がより十分に利用され、検索性能が向上される、マルチインスタンス学習による検索方法及びシステムを提供する。
【課題を解決するための手段】
【０００９】
本発明の実施例の一つの側面によれば、マルチインスタンス学習による検索方法であって、正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得し、テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定することを含み、前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、方法が提供される。
【００１０】
本発明の実施例の別の側面によれば、マルチインスタンス学習による検索システムであって、正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得するように構成される取得手段と、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成される訓練インスタンス重み生成手段と、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得するように構成されるテストインスタンスソートスコア取得手段と、テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される検索結果特定手段とを備え、前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、システムが提供される。
【００１１】
また、本発明の別の側面によれば、さらに記憶媒体が提供される。前記記憶媒体は、機械読取可能なプログラムコードを含む。前記プログラムコードは、情報処理装置で実行されると、前記情報処理装置に本発明による前記のマルチインスタンス学習による検索方法を実行させる。
【００１２】
また、本発明の別の側面によれば、さらにプログラムが提供される。前記プログラムは機械読取可能なコマンドを含む。前記コマンドは、情報処理装置で実行されると、前記情報処理装置に本発明による前記のマルチインスタンス学習による検索方法を実行させる。
【発明の効果】
【００１３】
本発明の実施例の前記方法によれば、画像検索を行う過程において、正の訓練パッケージにおいる訓練インスタンス毎に重みを生成することができる。当該重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。これにより、最後にテストパッケージにおけるテストインスタンスのそれぞれのソートスコアを算出する際に、正の訓練パッケージにおける訓練インスタンスに対し、それぞれの重みをその初期ラベルとし、最終的に各テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを取得して検索結果を与えることができる。従って、本発明の実施例においては、正の訓練パッケージから限定された数量の正のインスタンスを選択することは意図されず、正の訓練パッケージにおけるインスタンス毎にそれぞれの重みを算出し、当該重みの絶対的な大きさでインスタンスのそれぞれとユーザのルックアップ語義との一致度を表現する。これにより、更に正の訓練パッケージそれぞれにおけるインスタンスのそれぞれの重みに基づいてテストパッケージにおけるテストインスタンスのそれぞれのソートスコアを取得する。これにより、正の訓練パッケージにおける訓練インスタンスのそれぞれにより提供された情報が十分に利用され、検索の性能の向上に寄与する。
【００１４】
以下の明細書において本発明の実施例のその他の側面が提供される。ここで、詳細な説明は、本発明の実施例の好適な実施例を十全に開示するためのものであって、限定するものではない。
【図面の簡単な説明】
【００１５】
以下に、具体的な実施例を用いて、図面を参照しながら本発明の実施例の前記及びその他の目的と利点を更に説明する。図面において、同一又は対応する技術的特徴又は部品は、同一又は対応する符号で示される。
【図１】本発明による実施例により提供される方法を示すフローチャートである。
【図２】本発明による実施例により提供される別の方法を示すフローチャートである。
【図３】本発明による実施例により提供される第１の装置を示す模式図である。
【図４】本発明による実施例により提供される第２の装置を示す模式図である。
【図５】本発明による実施例により提供される第３の装置を示す模式図である。
【図６】本発明による実施例により提供される第４の装置を示す模式図である。
【図７】本発明による実施例により採用される情報処理装置のパーソナルコンピュータの模式的な構造を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下に、図面を参照して本発明の実施例を説明する。
【００１７】
理解を容易にするために、以下に、先ず本発明の実施例に係る幾つかの概念(訓練パッケージ、訓練インスタンス、正の訓練パッケージ、負の訓練パッケージ、正のインスタンス、負のインスタンス、テストパッケージ、テストインスタンスを含む)を紹介する。
【００１８】
まず、マルチインスタンス学習の枠組みにおいては、画像のそれぞれが一つのパッケージと見なされ、画像における領域のそれぞれが一つのインスタンスと見なされる。なお、検索シードであるサンプル画像が複数の領域に分割された後に、領域のそれぞれが訓練インスタンスと呼ばれ、一つのサンプル画像における全ての訓練インスタンスが一つの訓練パッケージを構成する。言い換えれば、一つのサンプル画像が一つの訓練パッケージに対応し、一つの訓練パッケージに複数の訓練インスタンスが含まれる。
【００１９】
なお、訓練インスタンスには正のインスタンスと負のインスタンスとが含まれる。正のインスタンスはユーザのルックアップ語義〔検索意図／検索対象〕を表現可能なもの、負のインスタンスはユーザのルックアップ語義を表現不可なものである。訓練パッケージは正の訓練パッケージと負の訓練パッケージに分けることができる。正の訓練パッケージは少なくとも一つの正のインスタンスを含むものである。負の訓練パッケージに含まれるインスタンスの全ては負のインスタンスである。例えば、ユーザがトラのある画像を検索しようとする場合に、提供されるサンプル画像がトラのある画像である場合もあるが、当該画像において更に幾つかの背景、例えば木、芝生等を含む可能性もある。つまり、当該サンプル画像は、一部の領域のみに本当にトラが表示され、別の一部の領域には木、芝生等が表示される。このように、当該サンプル画像に対して領域分割を行う際に、幾つかの領域にトラのパターンが表示される一方、幾つかの領域には木、芝生等だけが表示されるような場合もある。ユーザのルックアップ語義〔検索意図／検索対象〕は、トラのある画像を探索すべきであるため、当該サンプル画像について、トラのパターンのある領域に対応するインスタンスが正のインスタンスであり、木、芝生等のある領域に対応するインスタンスが負のインスタンスである。当該サンプル画像に対応する訓練パッケージは、正のインスタンスと負のインスタンスの両方を含むため、当該訓練パッケージが正の訓練パッケージである。当該サンプル画像は正のサンプル画像と呼ばれても良い。ユーザが検索しようとするものがトラのある画像であるが、提供されるサンプル画像に含まれるものが全て木、芝生等のパターンである場合に、当該サンプル画像を分割した全てのインスタンスは、ユーザのルックアップ語義〔検索意図／検索対象〕を表現不可なものとなり、負のインスタンスに該当する。それに対して、当該サンプル画像に対応する訓練パッケージも負の訓練パッケージであり、当該サンプル画像は負のサンプル画像と呼ばれても良い。
【００２０】
サンプル画像は、検索を開始する際にユーザにより提供されるものであっても良く、検索中に検索システムの提示でユーザにより選択されるものであっても良い。サンプル画像は複数あっても良い。更に、正のサンプル画像だけではなく、負のサンプル画像も提供されても良い。それと共に、ユーザはシステムにどれが正のサンプル画像であるか、どれが負のサンプル画像であるかを通知すべきである。それに対して、検索システムがサンプル画像に対して領域分割を行った後に、どの訓練パッケージが正のものであるか、どの訓練ペッケージが負のものであるかを了解することもできる。しかし、システムは、正の訓練パッケージにおけるインスタンスを取得した直後には、正の訓練パッケージにおいてどれが正のインスタンスであるか、どれが負のインスタンスであるかを知らず、解析処理をしたうえでインスタンスのレベルの情報を得なければならない。従って、サンプル画像は訓練画像と呼ばれる。即ち、画像検索を行うために、まずサンプル画像におけるインスタンスに基づいて訓練を行って使用可能な情報を取得する必要がある。これにより、更に後続の検索処理を完成させることができる。
【００２１】
検索システムは、画像データベースからユーザのルックアップ語義に該当する画像を選択する。なお、画像データベースには各種の画像が含まれている。これらの画像はテスト画像である。マルチインスタンスによる画像検索においては、テスト画像に領域分割を行う必要もある。分割した領域はテストインスタンスと呼ばれる。それに対して、一つのテスト画像内のテストインスタンスが一つのテストパッケージを構成する。
【００２２】
以下に本発明による実施例に提供される画像検索方法について詳細に説明する。
【００２３】
図１を参照すると、本発明による実施例により提供される、マルチインスタンス学習による検索方法は、以下のようなステップを含む。
【００２４】
Ｓ１０１：訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得する。前記訓練パッケージには正の訓練パッケージが含まれる。
【００２５】
上で説明したように、訓練パッケージはユーザにより提供されるものであっても良い。たとえば、ユーザは、画像検索を開始する際に、一つ又は複数の画像を選択してサンプル画像とすることができる。検索システムがこれらのサンプル画像に対して領域分割を行うことにより、領域のそれぞれが一つの訓練インスタンスに対応し、一つのサンプル画像が一つの訓練パッケージに対応する。本発明の実施例において、訓練パッケージには、少なくとも正の訓練パッケージが含まれる。勿論、訓練パッケージは、より良い検索結果を得るために、正の訓練パッケージだけではなく、負の訓練パッケージを含んでも良い。つまり、ユーザはサンプル画像を提供する時に、正のサンプル画像だけではなく、負のサンプル画像を提供することもできる。
【００２６】
Ｓ１０２：前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成する。当該重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。
【００２７】
本発明の実施例においては、正の訓練パッケージから限定された数量の正のインスタンスを選択することなく、正の訓練パッケージにおける訓練インスタンス毎に重みを生成する。当該重みは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。ここでは、本発明の実施例において、当該重みの絶対的な大きさは、前記のユーザのルックアップ語義を表現可能な度合いを表すことができる。つまり、正の訓練パッケージにおけるあるインスタンスが確かに正のインスタンスであれば、そのパッケージに対して生成される重みは負のインスタンスの重みより大きくなり、且つその重みそのものが正の値である。
【００２８】
Ｓ１０３：訓練パッケージ及びテストパッケージにおける全てのインスタンスに対して、前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて各テストインスタンスのソートスコア〔順位付けに使われるスコア〕を取得する。
【００２９】
正の訓練パッケージにおける訓練インスタンスに対してそれぞれの重みを取得した後に、訓練パッケージ及びテストパッケージにおける全てのインスタンスに対して、全てのインスタンスの間の類似度及び前記正の訓練パッケージにおける各訓練インスタンスの重みに基づいて各テストインスタンスのソートスコアを取得することができる。即ち、正の訓練パッケージにおける各インスタンスの重みは、テストパッケージにおけるテストインスタンスについてソートスコアを算出する過程に応用される。
【００３０】
言い換えれば、一般的な検索方法は、正の訓練パッケージから幾つかの情報を取得した後に、これらの情報を用いてテストパッケージからユーザのルックアップ語義〔検索意図／検索対象〕を表現するパッケージを検索するものである。これらの情報は、例えばインスタンスのソートスコアである。従来の方法においては、ソートスコアは相対的な値であり、インスタンスがユーザのルックアップ語義に合致する度合いを直接に表現することができない。本発明の実施例においては、前記ソートスコアの代わりに、正の訓練パッケージにおける各インスタンスの重みを用いることにより、インスタンスがユーザのルックアップ語義に合致する度合いを直接に表現することができる。
【００３１】
Ｓ１０４：テストパッケージにおける各テストインスタンスのソートスコアに基づいて各テストパッケージのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定する。
【００３２】
各テストインスタンスのソートスコアが取得された後に、テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを特定することができる。例えば、あるテストパッケージについて、該テストパッケージ中の各テストインスタンスのソートスコアを平均した値を当該テストパッケージのソートスコアとすることができる。勿論、一つのテストパッケージにおいて一般的に一つ又は少数のインスタンスのみが正のインスタンスである可能性があるため、前記の平均値を取る方法を採用してテストパッケージのソートスコアを取得すれば、テストパッケージのソートスコアが低くなる恐れがある。テストパッケージのソートスコアの適正性を向上させるために、当該テストパッケージにおける各テストインスタンスのソートスコアの最大値を当該テストパッケージのソートスコアとしても良い。
【００３３】
各テストパッケージのソートスコアを取得した後に、それに基づいてユーザに検索結果を提供することができる。例えば、ソートスコアの順位が上位の予め設けられた数のテストパッケージに対応する画像をユーザに返してもよいし、あるいは、ソートスコアに従って各テストパッケージをソートした後に、当該順序に従ってテストパッケージに対応する画像をユーザに順次提供する等のようにしても良い。
【００３４】
要するに、画像検索を行う過程において、正の訓練パッケージにおける訓練インスタンス毎に重みを生成することができる。当該重みの絶対的な大きさは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。このように、最後にテストパッケージにおける各テストインスタンスのソートスコアを算出する際に、正の訓練パッケージにおける訓練インスタンスに対して、それぞれの重みをその初期ラベルとし、最終的に各テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを取得して検索結果を与えることができる。以上のように、本発明の実施例において、正の訓練パッケージから限定された数量の正のインスタンスを選択することを意図することなく、正の訓練パッケージにおけるインスタンス毎にそれぞれの重みを算出し、当該重みの絶対的な大きさで各インスタンスとユーザのルックアップ語義との一致性を表すことにより、各正の訓練パッケージにおける各インスタンスの重みに基づいてテストパッケージにおける各テストインスタンスのソートスコアを取得する。このように、正の訓練パッケージにおける各訓練インスタンスにより提供される情報が十分に利用されることにより、検索の性能が向上される。
【００３５】
具体的に実現するにあたって、正の訓練パッケージにおける訓練インスタンス毎に前記重みを生成する方法は多種ある。以下に一つの実現手段について詳細に説明する。図２を参照すると、以下のようなステップを含んでも良い。
【００３６】
Ｓ２０１：正の訓練パッケージにおける訓練インスタンスの初期重みを取得する。
【００３７】
なお、正の訓練パッケージにおける訓練インスタンスの初期重みは、予めプロファイルに設定可能である。これにより、プロファイルを読み取る手段により、システムに当該初期重みを取得させることができる。例えば、統一的に１０に設置しても良い(勿論その他の値であっても良いが、一般的に正の値である)。
【００３８】
Ｓ２０２：訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズム（後述）を採用して学習を行って、各訓練インスタンスのソートスコアを取得する。
【００３９】
訓練パッケージ及び訓練インスタンスが取得された後に、グラフによるアルゴリズムを採用して学習を行って各訓練インスタンスのソートスコアを取得することができる。なお、学習中に主に訓練インスタンス同士の類似度に基づいてグラフによる学習を行う。
【００４０】
ここで、グラフによるアルゴリズムに基づいて学習を行うことによって各訓練インスタンスのソートスコアを取得する過程は、従来の技術であり、本発明の要点ではない。従って、ここでは簡単に説明するにとどめる。
【００４１】
以下の方法でグラフによる学習を行うことができる。即ち、まず重み付きグラフを構築する。同グラフにおけるノードは訓練パッケージにおける全ての訓練インスタンスに対応する。つまり、２つの訓練パッケージがあり、訓練パッケージのそれぞれに五つの訓練インスタンスがあることを仮定すれば、構築されたグラフには１０個のノードが存在する。同グラフにおける辺〔エッジ〕の重みが、その辺と接続する２つのノード同士の類似度を表す。次に、グラフによるアルゴリズムを採用して学習を行う。アルゴリズムが終了した時点で、それぞれの訓練インスタンスが一つのソートスコアに対応することができる。
【００４２】
なお、ノード間の類似度を算出する際、各訓練インスタンスから視覚特徴(一般的にベクトルの形式である)をそれぞれ抽出した後に、ベクトル計算の方法で二つずつの間の距離を算出することができる。ここでは、距離が小さいほど、類似度が高くなる。逆に、距離が大きいほど、類似度が低くなる。勿論、実際の応用において、視覚特徴を抽出する以外に、別途に各訓練インスタンスに関する特徴、例えば描画情報等を取得することもできる。また、これらの情報を訓練インスタンス同士の類似度の算出に加味することもできる。
【００４３】
以上に説明したように重み付きグラフを構築することは形象による説明方法である。コンピュータシステムにとっては、当該重み付きグラフに対応するデータはn×nの行列Ｓである。なお、ｎは訓練インスタンスの総数である。つまり、前記の例において、１０個の訓練インスタンスがあれば、当該行列は１０行１０列を有し、i行目のj列目の要素Sijがi個目の訓練インスタンスとj個目の訓練インスタンスとの間の類似度に対応する。また、更に当該行列に対して行による正規化処理を行うこともできる。
【００４４】
グラフによるアルゴリズムは多種の具体的な実現方法がある。例えば、一つの実施形態においては、以下のような方法で行うことができる。即ち、まず全ての訓練インスタンスに初期ラベルを設定する。例えば、訓練パッケージが全て正の訓練パッケージであれば、全ての訓練インスタンスの初期ラベルを１とすることができる。訓練パッケージに正の訓練パッケージと負の訓練パッケージとの両方があれば、正の訓練パッケージにおける全ての訓練インスタンスの初期ラベルを１とし、負の訓練パッケージにおける全ての訓練インスタンスの初期ラベルを−１とすることができる。次に、前に構築された重み付きグラフ上に初期ラベルをグローバルな安定性を有する状態になるまで伝送する。最終的にそれぞれの訓練インスタンスのソートスコアを取得することができる。コンピュータシステムにとっては、以上のような重み付きグラフ上でラベルを伝送する過程は、以下のような反復的な公式に従って達成することができる。
f(t＋1)＝αSf(t)＋(1−α)y (1)
ただし、Ｓは前記の構築されたグラフに対応する正規化行列である。ｙは各訓練インスタンスの初期ラベルからなるラベルベクトルである。例えば、一つの正の訓練パッケージと一つの負の訓練パッケージがあり、訓練パッケージのそれぞれに五つのインスタンスがあるとすれば、ｙは(1,1,1,1,1,−1,−1,−1,−1,−1)Tとなる。α（0＜α＜1）は線形的な組合せ係数である。f(t)もベクトルであり、その中の要素数は訓練インスタンスの数と同じであり、各要素がｔ回目の反復工程後の各訓練インスタンスが対応するラベルの値に対応する。例えば、f(1)は１回目の反復工程後の各訓練インスタンスのラベルからなるベクトルを表す。初期状態において、f(0)は任意の値を取っても良く、一つの具体的な実施形態ではf(0)をｙに等しくすることもできる。
【００４５】
つまり、(１)式を利用して複数回の反復工程を行うことができる。反復的な過程が収束することは、前記重み付きグラフ上で伝送する際にグローバルな安定性を有する状態になることに対応し、その後に対応するf(t)を取得し、その中の各要素の値に基づいて各訓練インスタンスのソートスコアを取得することができる。なお、具体的な実現において、以下の方法で反復的な過程が収束したか否かを判断することができる。即ち、f(t)とf(t−1)とが非常に接近したか否かを判断する(両者の距離を算出して、ある閾値と比較することができる)。この判断の結果が肯定の場合に収束したと判断し、反復的な過程を終了すれば良い。勿論、反復回数等を予め設ける方法で実現しても良く、ここでは詳細な説明を省略する。
【００４６】
なお、前記(１)式を採用して反復処理を行うことは、下記の最小化すべき関数を最小化する必要があるからである。
【数１】
【００４７】
上記の最小化すべき関数は二つの拘束関係からなる。一つ目の拘束関係
【数２】
は重み付きグラフにより得られた平滑性拘束条件（smoothness constraint）である。fi、fjはfの中のi項目及びj項目である。即ち、類似した訓練インスタンスに対応するソートスコアの差異は大きくないことが期待される。二つ目の拘束関係
【数３】
は、初期ラベルによるフィッテング〔適合〕拘束条件（fitting constraint）である。即ち、最終的なソートスコアと初期ラベルとの差異が大きくないことが期待される。ただし、μは2つの項目の重要性のバランスを取るための重みである。(１)式におけるαはμで算出することができる。即ちα＝1／(1＋μ)。このように、上記の関数を最適化することにより、(１)式における反復的な式を得ることができる。言い換えれば、(１)式を用いて反復を行うことにより、最終的なソートスコアに(２)式における拘束条件を満足させることができる。そして、このように算出されたソートスコアの高さは、対応する訓練インスタンスがユーザのルックアップ語義〔検索意図、検索対象〕を表現可能な度合いを表すことができる。即ち、訓練インスタンスのソートスコアが高いほど、ユーザのルックアップ語義を表すことができる。
【００４８】
ここで、具体的に実現する際、訓練インスタンスの数は一般的に大きくないため、(１)式の解析的な解を直接に用いて最終的な結果を取得しても良い。
f*＝(1−α)(I−αS)-1y （3）
ただし、Ｉは単位行列である。
【００４９】
ステップＳ２０３：訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセット（後述）を特定し、各訓練インスタンスについて、正の近隣するインスタンスセットにおける各訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更し、これにより正の訓練パッケージにおける各訓練インスタンスの最終重みを取得する。なお、前記訓練インスタンスの正の近隣するインスタンスセットは、当該訓練インスタンスと予め設けられた類似関係を有する正の訓練パッケージにおける訓練インスタンスにより構成される。
【００５０】
ステップＳ２０２において、各訓練インスタンスのソートスコアを算出して各訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。しかし、本発明を実現するにあたって、当該方法により算出されたソートスコアが一般的に相対性を有する、即ち各訓練インスタンスのソートスコアの相対的な大きさが意義を有することが本発明者により発見された。例えば、前記の方法により得られたソートスコアでは、ある正の訓練パッケージにおける各訓練インスタンスのソートスコアが何れも負の値である可能性がある。なお、あるインスタンスが確かに正のインスタンスであるとすれば、そのインスタンスがソートスコアに表現される際に負のインスタンスのソートスコアよりも確かに高い可能性がある。だが、そのものが負の値であると、その絶対的な大きさはあるべき意義を失ってしまっていた。ところが、実際に正の訓練パッケージであるからには、その中の少なくとも一つの訓練インスタンスが正のインスタンスであり、正のインスタンスのソートスコアは正の値であるだろう。これこそ、後続の検索に寄与することができる。従って、当該負の値を直接に利用して後続の検索過程を行うと、検索結果の有効性を損なう恐れがある(後続の検索過程とは、訓練インスタンスに初期ラベルを付与する必要があることを指し、ステップＳ２０２に得られたソートスコアを直接に利用して値を付与すれば、正の訓練パッケージにおける正のインスタンスの初期ラベルに負の値を付与する恐れがある)。従って、本発明の実施例においては、訓練インスタンスのソートスコアが得られた後に、更なる処理が必要である。
【００５１】
前記の更なる処理を行うために、多種の方法が採用可能である。例えば、簡単には、各訓練インスタンスのソートスコアが算出された後に、正の訓練パッケージにおいて少なくとも一つの訓練インスタンスのソートスコアが正の値となるように、各ソートスコアにあるオフセットを加える。これにより、一つの正の訓練パッケージにおける全ての訓練インスタンスのソートスコアが何れも負の値であることを回避することができる。
【００５２】
あるいは、本発明の実施例において、以下のような方法を採用して前記の処理過程を実現しても良い。即ち、先ず各訓練インスタンスに対して各訓練インスタンスの正の近隣するインスタンスセットをそれぞれ探す。ある訓練インスタンスＬについて、訓練インスタンスＬの正の近隣するインスタンスセットとは、そのセットが正の訓練パッケージにおける訓練インスタンスにより構成され、且つそのセットにおける各インスタンスが当該訓練インスタンスＬとある隣接関係／類似関係を有するものである。具体的な実現においては、どのような隣接関係／類似関係を満足する必要があるかについて予め設定されていても良く、例えば二つの訓練インスタンスの間の類似度がある閾値よりも大きいか否かを簡単に設定することができる。あるいは、本発明の実施例において、ステップＳ２０２で構築された重み付きグラフ中の遷移関係に基づいて算出されても良い。
【００５３】
なお、重み付きグラフ中の遷移関係に基づいて算出する際に、ノードの間の一次又は高次の伝達関係に基づいてノード間の類似関係を特定することができる。ここで、一次の伝達関係は二つの訓練インスタンス間の類似度を指す。二次の伝達関係は、インスタンス１とインスタンス２との間に非常に高い類似度を有し、且つインスタンス２とインスタンス３との間に比較的高い類似度を有する場合に、インスタンス１とインスタンス３との類似度を直接に算出した場合にスコアが低くなっても、インスタンス１とインスタンス３がある類似関係を満足すると考えられることを指す。その他はこれによって類推すれば良い。
【００５４】
ここでは、各訓練インスタンスにそれぞれ正の近隣するインスタンスセットが見つかるわけではない。つまり、ある訓練インスタンスに対し、その正の近隣するインスタンスセットが空であっても良い。
【００５５】
本発明の実施例において、予め正の訓練パッケージにおける各訓練インスタンスの初期重みが知られている。従って、各訓練インスタンスの正の近隣するインスタンスセットが得られた後に、セット内のインスタンスの重みを調整することができる。同一の正の近隣するインスタンスセットにおける各インスタンスについて、具体的に調整を行う際に、多種の調整方針がある。例えば、一つの方針においては、各訓練インスタンスのソートスコアの高さに応じて各訓練インスタンスの調整幅を特定し、例えばソートスコアが最も高い訓練インスタンスの重みは１だけ増大し、二番目に高いものは0.8だけ増大し、三番目に高いものは0.5だけ増大する等のようにしても良い。勿論、その他の調整方針において、ソートスコアの最も高い一つの訓練インスタンスに対して調整を行っても良く、ここでは列挙しない。
【００５６】
ここで、訓練パッケージにおいて正の訓練パッケージと負の訓練パッケージとの両方がある場合に、訓練インスタンスの重みを具体的に調整する際、正の訓練パッケージにおける訓練インスタンスについては、その正の近隣するインスタンスセットにおけるインスタンスの重みを大きくする調整を行い、負の訓練パッケージにおける訓練インスタンスについては、その正の近隣するインスタンスセットにおける重みを小さくする調整を行うことができる。つまり、負の訓練パッケージにおける訓練インスタンスは、絶対に正のインスタンスではないため、正の訓練パッケージにおけるあるインスタンスがそれと類似関係を有すれば、当該正の訓練パッケージにおけるインスタンスが正のインスタンスではない可能性もあるため、その重みを小さくすることが合理的である。
【００５７】
正の訓練パッケージにおける訓練インスタンス(説明を容易にするために、正の訓練パッケージにおけるある訓練インスタンスＡを例とする)について、Ａが正のインスタンスであるか、負のインスタンスであるかについて不明であるが、正のインスタンスである可能性が存在する。従って、正の訓練パッケージにおけるその他のインスタンスがそれと類似関係を有し、即ちこれらのその他のインスタンスが訓練インスタンスＡの正の近隣するインスタンスセットを構成する場合に、訓練インスタンスＡによりその正の近隣するインスタンスセットにおけるインスタンスの重みを大きくすることができる。その結果、二つの可能性が存在する。一つの可能性としては、当該訓練インスタンスＡが確かに正のインスタンスである場合、その正の近隣するインスタンスセットにおけるインスタンスが正のインスタンスである可能性が高いため、その重みを大きくすることが合理的である。もう一つの可能性としては、訓練インスタンスＡが正の訓練パッケージに位置するが、負のインスタンスである場合、その正の近隣するインスタンスセットにおけるインスタンスが正のインスタンスである可能性が低いため、その重みを大きくすることは一見して不合理である。しかし、ここで、全ての訓練インスタンスのそれぞれに各自の正の近隣するインスタンスセット(勿論、セットが空の場合もある)が決定されており、正の訓練パッケージにおける同一の訓練インスタンスが異なる複数の正の近隣するインスタンスセットに位置する可能性がある。従って、前記の二種目の場合において、訓練インスタンスＡの正の近隣するインスタンスセットにおけるインスタンスがある訓練インスタンスＢ又はその他のインスタンスの正の近隣するインスタンスセットに位置し、訓練インスタンスＢ又はその他のインスタンスが負の訓練パッケージにおけるインスタンスである可能性がある。従って、更にその正の近隣するインスタンスセットにおけるインスタンスの重みを小さくする操作を行うことになる。これにより、その前に大きくされた重みを小さくすることができる。つまり、正の訓練パッケージにおける訓練インスタンスは、複数回の重み調整操作が行われる可能性があり、あるものは一貫して大きくされ、あるものは一貫して小さくされ、あるものが一部的に大きくされ且つ一部的に小さくされ、最終的に正の訓練パッケージにおける各訓練インスタンスに各自の重みを有させる。
【００５８】
また、訓練パッケージを構成するものが全て正の訓練パッケージである場合に、訓練インスタンスの重みを調整する際、具体的な調整操作は重みを大きくする操作であっても良い。ここで、この場合に、大きくするという操作のみを行えるが、各訓練インスタンスのソートスコアが異なり、且つ正の近隣するインスタンスセットに訓練インスタンスのそれぞれが位置する場合も異なるため、依然として正の訓練パッケージにおける各訓練インスタンスに異なる最終的重みを有させることもできる。ここで、正の訓練パッケージのみがある場合においても、得られた最終的重みが依然として正の訓練パッケージにおける各訓練インスタンスとユーザのルックアップ語義との一致度を表現可能である。これは、前に記載された「正のインスタンス同士が一般的に類似である」という特徴により決められ、ここでは詳しく説明しない。
【００５９】
以上の方法により、正の訓練パッケージにおける各訓練インスタンスに重みを生成することができる。次に、当該重みを用いて検索を行う際に、以下のようなステップを含んでも良い。
【００６０】
Ｓ２０４：訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを取得する。なお、正の訓練パッケージにおける各訓練インスタンスの初期ラベルは前記最終的重みにより特定されたものである。
【００６１】
正の訓練パッケージにおける各インスタンスの重みが得られた後に、訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、各テストインスタンスのソートスコアを特定するように、グラフによるアルゴリズムに基づいて学習を行うことができる。なお、グラフによるアルゴリズムに基づいて学習を行う際に、ステップ２０２と同様に、先ず重み付きグラフを構築する。当該グラフにおいては、ノードが訓練パッケージ及びテストパッケージにおける全てのインスタンスに対応し、辺の重みがその辺と接続する二つのノード間の類似度を表す。ここで、図によるアルゴリズムに基づいて学習を行う際に、各インスタンスに初期ラベルを設定する必要がある(例えば、ステップＳ２０２において、正の訓練パッケージにおける全てのインスタンスの初期ラベルを１に設定し、負の訓練パッケージにおける全てのインスタンスの初期ラベルを−1に設定することができる)。本発明の実施例において、テストパッケージにおける各インスタンスにソートスコアを算出する必要がある場合に、訓練パッケージにおける正の訓練パッケージについて、ステップＳ２０３に得られた各自の最終的重みに基づいてその中のインスタンスの初期ラベルを特定することができる。
【００６２】
つまり、ステップＳ２０３で正の訓練パッケージにおける各インスタンスに対する重みをそれぞれ算出し、ステップＳ２０４で訓練パッケージ及びテストパッケージにおける全てのインスタンスに基づいてグラフによるアルゴリズムの学習を行う必要がある場合に、算出された重みに基づいて正の訓練パッケージにおける各訓練インスタンスの初期ラベルを特定することができる。例えば、ステップＳ２０３で算出された正の訓練パッケージにおける各訓練インスタンスの重みに対して直接に正規化処理を行った後に、正規化処理された値を正の訓練パッケージにおける各訓練インスタンスの初期ラベルとすることができる。
【００６３】
訓練パッケージに負の訓練パッケージがある場合、負の訓練パッケージにおける各訓練インスタンスの初期ラベルは依然として−１に設定されても良い。ステップＳ２０２と同様に、各インスタンスの初期ラベルを、グローバルな安定性を有する状態になるまで前に構築された重み付きグラフ上に伝送し、最終的に各テストインスタンスのソートスコアを得ることができる。コンピュータシステムにとっては、以上のようにラベルを重み付きグラフ上に伝送する過程は、以下の反復的な公式により完成することができる。
f(t＋1)＝Sf(t) (4)
ここで、Ｓは訓練パッケージ及びテストパッケージにおける全てのインスタンスに基づいて構築されたグラフに対応する正規化行列である。ｆ(ｔ)はベクトルであり、その中の要素数は訓練インスタンスとテストインスタンスとの数の合計値であり、各要素がｔ回目の反復工程後の各インスタンスの対応するラベルの値に対応する。例えば、ｆ(1)は１回目の反復工程後の各インスタンスのラベルからなるベクトルを表す。初期状態において、ｆ(0)は各インスタンスに対応する初期ラベルからなるベクトルであっても良い。反復過程が終了した時に、ｆ(ｔ)における各要素の値を各インスタンスのソートスコアとすることができる。
ここで、(4)式を用いて反復処理を行う際に、一回の反復工程が終了するたびに、ｆ(ｔ)のうちの各訓練インスタンスのラベルに新たな初期値を付与する。つまり、反復の過程において、訓練インスタンスのラベルはそのままで保持される、言い換えると、常に初期ラベルと等しい(ただし、正の訓練パッケージにおける訓練インスタンスのラベルが常にその前に算出された重み又は正規化処理された重みと等しい一方、負の訓練パッケージにおける訓練インスタンスのラベルは常に付与された初期値、例えば−１等と等しい)。勿論、一回の反復工程が終了するたびに、テストインスタンスのラベルが変わることになる。ところが、テストパッケージにおける各テストインスタンスの初期ラベルは任意に設定可能である。これは、最終的な算出結果がテストインスタンスの初期ラベルの値と関係ないからである。
【００６４】
また、ここで、前に説明したのと同様に、反復の方法で最終的なソートスコアを取得することなく、(4)式の解析的な解を直接に用いて最終的な結果を取得しても良い。その結果は、反復によるものと同じである。勿論、テストインスタンスの数が一般的に多くなると、解析的な解は、行列の逆を求める演算に係るため、反復の方法と比べて演算の複雑性が高くなる。また、ステップＳ２０４におけるグラフによる学習について、詳しく説明していない部分については前の説明を参照することができ、ここでは詳しく説明しない。
【００６５】
Ｓ２０５：テストパッケージにおける各テストインスタンスのソートスコアに基づいて各テストパッケージのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定する。
【００６６】
本発明の実施例は、提供されたマルチインスタンス学習による検索方法に対応して、マルチインスタンス学習による検索システムを提供する。図３を参照すると、当該システムは以下のものを備える。
【００６７】
訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得するように構成される取得手段３０１を備える。前記訓練パッケージには正の訓練パッケージが含まれる。
【００６８】
前記正の訓練パッケージにおける訓練インスタンスごとに重みを生成するように構成される訓練インスタンス重み生成手段３０２を備える。当該重みの絶対的な大きさは対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。
【００６９】
訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて各テストインスタンスのソートスコアを取得するように構成されるテストインスタンスソートスコア取得手段３０３を備える。
【００７０】
テストパッケージにおける各テストインスタンスのソートスコアに基づいて各テストパッケージのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される検索結果特定手段３０４を備える。
【００７１】
なお、図４を参照すると、正の訓練パッケージにおける訓練インスタンスに重みを具体的に生成するにあたり、訓練インスタンス重み生成手段３０２は以下のものを備えても良い。
【００７２】
正の訓練パッケージにおける訓練インスタンスの初期重みを知るように構成される初期重みラーニングサブ手段３０２１を備える。
【００７３】
訓練インスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各訓練インスタンスのソートスコアを取得するように構成される訓練インスタンスソートスコア取得サブ手段３０２２を備える。
【００７４】
訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセットを特定し、各訓練インスタンスに対して、正の近隣するインスタンスセットにおける各訓練インスタンスのソートスコアに基づいて、正の訓練パッケージにおける各訓練インスタンスの最終的な重みを取得するように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される重み補正サブ手段３０２３を備える。なお、前記訓練インスタンスの正の近隣するインスタンスセットは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスにより構成される。
【００７５】
具体的に実現する際、訓練パッケージに負の訓練パッケージが含まれても良い。これに対して、重み補正サブ手段３０２３は以下のものを備えても良い。
【００７６】
正の訓練パッケージにおける各訓練インスタンスに対し、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくするように構成される重み増大サブ手段を備える。
【００７７】
負の訓練パッケージにおける各訓練インスタンスに対し、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくするように構成される重み減少サブ手段を備える。
【００７８】
具体的には、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアを補正する際、正の近隣するインスタンスセットにおいてソートスコアが最も大きい訓練インスタンスのソートスコアのみを、大きくする補正又は小さくする補正を行っても良い。この時に、重み補正サブ手段３０２３は、具体的に、正の近隣するインスタンスセットにおけるソートスコアが最も大きい訓練インスタンスの重みを変更するように構成することができる。
【００７９】
具体的には、正の近隣するインスタンスセットを決定する際、多種の方法を採用しうる。その一つの方法としては、グラフによるアルゴリズムに基づいて学習を行う過程に構築された重み付きグラフにおける各ノードの一次又は高次の伝達関係に基づいて、訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセットを特定することができる。つまり、図５を参照すると、重み補正サブ手段３０２３は以下のものを備えても良い。
【００８０】
グラフによるアルゴリズムに基づいて学習を行う過程で構築された重み付きグラフにおける各ノードの一次又は高次の伝達関係に基づいて、訓練パッケージにおける各訓練インスタンスの正の近隣するインスタンスセットを特定するように構成される正の近隣するインスタンスセット特定サブ手段３０２３１を備える。前記重み付きグラフにおいて、ノードは訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みはその辺と接続する2つのノードの間の類似度に対応する。
【００８１】
各訓練インスタンスに対し、正の近隣するインスタンスセットにおける各訓練インスタンスのソートスコアに基づいて、正の訓練パッケージにおける各訓練インスタンスの最終的な重みを得るように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される補正サブ手段３０２３２を備える。
【００８２】
具体的に実現する際に、テストインスタンスソートスコア取得手段３０３は、具体的に、訓練パッケージ及びテストパッケージにおける全てのインスタンスに対し、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを得るように構成することができる。なお、正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる。
【００８３】
テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを特定する際には、多種の方法を採用できる。その一つの方法では、図６を参照すると、検索結果特定手段３０４は以下のものを備えても良い。
【００８４】
テストパッケージにおける各テストインスタンスが対応するソートスコアの最大値を当該テストパッケージのソートスコアとするように構成されるテストパッケージソートスコア特定サブ手段３０４１を備える。
【００８５】
前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される特定サブ手段３０４２を備える。
【００８６】
本発明による実施例により提供される前記システムによれば、画像検索を行う過程において、正の訓練パッケージにおけるそれぞれの訓練インスタンスに重みを生成することができる。当該重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す。これにより、最後にテストパッケージにおける各テストインスタンスのソートスコアを算出する時に、正の訓練パッケージにおける訓練インスタンスに対し、それぞれの重みをその初期ラベルとし、最終的に各テストインスタンスのソートスコアに基づいてテストパッケージのソートスコアを取得して検索結果を与えることができる。従って、本発明の実施例において、正の訓練パッケージから有限な数量の正のインスタンスを選択することを意図せず、正の訓練パッケージにおける各インスタンスにそれぞれの重みを算出し、当該重みの絶対的な大きさで各インスタンスとユーザのルックアップ語義との一致度を表現する。これにより、更に各正の訓練パッケージにおける各インスタンスの重みに基づいてテストパッケージにおける各テストインスタンスのソートスコアを取得する。これにより、正の訓練パッケージにおける各訓練インスタンスにより提供された情報が十分に利用され、検索の性能の向上に寄与する。
【００８７】
ここで、前記システムの実施例は、前記方法の実施例に基づいて説明されたものである。その中の詳細説明のない部分は、方法の実施例の部分の説明を参照することができ、ここでは詳しく説明しない。
【００８８】
また、前記一連の処理及び装置は、ソフトウェア及び/又はファームウェアにより実現可能である。ソフトウェア及び/又はファームウェアにより実現される場合に、記憶媒体又はネットワークから、専用のハードウェア構成を有するコンピュータ、例えば図７に示された汎用のパーソナルコンピュータ７００へ、当該ソフトウェアを構成するプログラムをインストールする。当該コンピュータは、各種のプログラムがインストールされている場合に、各機能などを実行することができる。
【００８９】
図７において、中央処理装置（CPU）７０１は、読取専用メモリ（ROM）７０２に記憶されたプログラム又は記憶部７０８からランダムアクセスメモリ（RAM）７０３にロードされたプログラムに基づいて各種の処理を実行する。RAM７０３には、必要に応じてCPU７０１が各種の処理等を実行するために必要なデータも記憶される。
【００９０】
CPU７０１、ROM７０２とRAM７０３はバス７０４を介して互いに接続されている。入力／出力インタフェース７０５もバス７０４に接続されている。
【００９１】
キーボード、マウス等を含む入力部７０６と、ディスプレイ、例えばブラウン管（CRT）、液晶ディスプレイ（LCD）等とスピーカ等を含む出力部７０７と、ハードディスク等を含む記憶部７０８と、ネットワークインターフェースカード、例えばLANカード、モデム等を含む通信部７０９とは、入力／出力インタフェース７０５に接続されている。通信部７０９がネットワーク、例えばインターネットを経由して通信処理を実行する。
【００９２】
必要に応じて、入力／出力インタフェース７０５にはドライブ７１０も接続される。磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等のような取り外し可能な媒体７１１が、必要に応じてドライブ７１０に装着可能である。これにより、読み出されたコンピュータプログラムは必要に応じて記憶部７０８にインストールされる。
【００９３】
ソフトウェアで前記一連の処理を実現する場合、ネットワーク、例えばインターネット、又は記憶媒体、例えば取外し可能な媒体７１１からソフトウェアを構成するプログラムをインストールする。
【００９４】
このような記憶媒体は、図７に示された、その中にプログラムが記憶されており、デバイスから離れて配送されてユーザにプログラムを提供する取り外し可能な媒体７１１に限定されないことを、当業者は理解すべきである。取り外し可能な媒体７１１として、例えば、磁気ディスク（フロッピーディスク(登録商標)を含む）、光ディスク（コンパクトディスクリードオンリーメモリ（CD−ROM）やディジタルヴァーサタイルディスク（DVD）を含む）、光磁気ディスク（ミニディスク(MD)（登録商標）含む）及び半導体メモリを含む。または、記憶媒体は、ROM７０２、記憶部７０８に含まれるハードディスクであって、プログラムが記憶されており、且つそれらを含むデバイスと一緒にユーザに配送されるハードディスクなどであっても良い。
【００９５】
また、前記一連の処理のステップを実行する際、そのまま説明された順序に従い、時間順で実行しても良いが、時間順に限定されない。幾つかのステップは並行で、又は互いに個別で実行しても良い。
【００９６】
本発明及びその利点を詳細に説明したが、付属の特許請求の範囲に限定された本発明の要旨と範囲から逸脱しない限り、各種の変更、置換及び変換が可能である。そして、本発明の実施例の用語「含む」、「有する」、又は如何なる他の同等の表現は、非排他的な包含を意図しており、一連の要素を含む過程、方法、物品又は装置がそれらの要素を含むだけではなく、明確に列挙されていない他の要素、又はこのような過程、方法、物品又は装置の固有要素も含むことも許容する。更なる限定のない場合に、語句「一つの…を含む」により限定された要素は、前記要素を含む過程、方法、物品又は装置において更に別の同一の要素が存在することを排除しない。
【００９７】
以上の実施例を含む実施形態について、さらに以下の付記が開示される。
（付記１）マルチインスタンス学習による検索方法であって、
正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得し、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、
訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得し、及び
テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定することを含み、
前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、ことを特徴とする方法。
（付記２）前記の、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成することは、
正の訓練パッケージにおける訓練インスタンスの初期重みを知り、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得し、及び
訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定し、訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得するように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することを含み、
前記訓練インスタンスの正の近隣するインスタンスセットは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスにより構成される、ことを特徴とする付記１に記載の方法。
（付記３）前記訓練パッケージに負の訓練パッケージが更に含まれ、前記の、訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
正の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくし、及び
負の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくすることを含む、を特徴とする付記２に記載の方法。
（付記４）前記の、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
正の近隣するインスタンスセットにおけるソートスコアの最も大きい訓練インスタンスの重みを変更することを含む、付記２又は３に記載の方法。
（付記５）前記の、訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定することは、
グラフによるアルゴリズムに基づいて学習を行う過程に構築された重み付きグラフにおけるノードのそれぞれの一次又は複数次の伝達関係に基づいて、訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定することを含み、
前記重み付きグラムにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みがそれと接続する2つのノードの間の類似度に対応する、付記２に記載の方法。
（付記６）前記の、訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、全てのインスタンス同士の類似度及び前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みに基づいてテストインスタンスのソートスコアを取得することは、
訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、全てのインスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行ってテストインスタンスのそれぞれのソートスコアを取得することを含み、
正の訓練パッケージにおける訓練インスタンスのそれぞれの初期ラベルはそれぞれの重みにより決められる、付記１に記載の方法。
（付記７）前記の、テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞれのソートスコアを特定することは、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとすることを含む、付記１に記載の方法。
（付記８）マルチインスタンス学習による検索システムであって、
正の訓練パッケージを含む訓練パッケージ及び訓練パッケージにおける訓練インスタンスを取得するように構成される取得手段と、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成される訓練インスタンス重み生成手段と、
訓練パッケージ及びテストパッケージにおけるインスタンスの全てについて、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの重みを用いてテストインスタンスのそれぞれのソートスコアを取得するように構成されるテストインスタンスソートスコア取得手段と、
テストパッケージにおけるテストインスタンスのそれぞれのソートスコアに基づいてテストパッケージのそれぞのソートスコアを特定し、前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される検索結果特定手段とを備え、
前記重みの絶対的な大きさは、対応する訓練インスタンスがユーザのルックアップ語義を表現可能な度合いを表す、ことを特徴とするシステム。
（付記９）前記訓練インスタンス重み生成手段は、
正の訓練パッケージにおける訓練インスタンスの初期重みを知るように構成される初期重みラーニングサブ手段と、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得するように構成される訓練インスタンスソートスコア取得サブ手段と、
訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定し、訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得するように正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される重み補正サブ手段とを備え、
前記訓練インスタンスの正の近隣するインスタンスセットは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスにより構成されることを特徴とする付記８に記載のシステム。
（付記１０）前記訓練パッケージに負の訓練パッケージが更に含まれ、前記重み補正サブ手段は、
正の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくするように構成される重み増大サブ手段と、
負の訓練パッケージにおける訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくするように構成される重み減少サブ手段と、を備える、ことを特徴とする付記９に記載のシステム。
（付記１１）前記重み補正サブ手段は、正の近隣するインスタンスセットにおけるソートスコアの最も大きい訓練インスタンスの重みを変更するように構成される、ことを特徴とする付記９又は１０に記載のシステム。
（付記１２）前記重み補正サブ手段は、
グラフによるアルゴリズムに基づいて学習を行う過程に構築された重み付きグラフにおけるノードのそれぞれの一次又は複数次の伝達関係に基づいて、訓練パッケージにおける訓練インスタンスのそれぞれの正の近隣するインスタンスセットを特定するように構成される正の近隣するインスタンスセット特定サブ手段と、
訓練インスタンス毎に、正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得するように、正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更するように構成される補正サブ手段とを備え、
前記重み付きグラムにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みがそれと接続する2つのノードの間の類似度に対応する、ことを特徴とする、付記９に記載のシステム。
（付記１３）前記テストインスタンスソートスコア取得手段は、具体的に、訓練パッケージ及びテストパッケージにおける全てのインスタンスについて、全てのインスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行ってテストインスタンスのそれぞれのソートスコアを取得するように構成され、
正の訓練パッケージにおける訓練インスタンスのそれぞれの初期ラベルはそれぞれの重みにより決められる、ことを特徴とする、付記８に記載のシステム。
（付記１４）前記検索結果特定手段は、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとするように構成されるテストパッケージソートスコア特定サブ手段と、
前記テストパッケージのソートスコアに基づいて検索結果を特定するように構成される特定サブ手段とを備える、ことを特徴とする、付記８に記載のシステム。
【００９８】
（付記１′）複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索方法であって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該方法は、コンピュータが、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得し、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得し、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算し、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定することを含み、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、
ことを特徴とする方法。
（付記２′）前記の、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成することは、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得し、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得し、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得することを含み、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、ことを特徴とする付記１′に記載の方法。
（付記３′）前記一つまたは複数の訓練パッケージに負の訓練パッケージが更に含まれ、前記の、各訓練インスタンスについて前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくし、
前記負の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくすることを含む、
ことを特徴とする付記２′に記載の方法。
（付記４′）前記の、前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアのうち最も大きい訓練インスタンスの重みを変更することを含む、
ことを特徴とする付記２′又は３′に記載の方法。
（付記５′）前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することは、
グラフによるアルゴリズムに基づいて学習を行う過程で構築された重み付きグラフにおけるノードに対応する訓練インスタンス間の一次又は高次の伝達関係に基づく類似度に基づいて、前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することを含み、
前記重み付きグラフにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みが該辺と接続する2つのノードの間の類似度に対応する、
ことを特徴とする付記２′に記載の方法。
（付記６′）前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度及び前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得することは、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを取得することを含み、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする付記１′に記載の方法。
（付記７′）各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算することは、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとすることを含む、
ことを特徴とする付記１′に記載の方法。
（付記８′）複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索システムであって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該システムは、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得するように構成された取得手段と、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成された訓練インスタンス重み生成手段と、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得するように構成されたテストインスタンスソートスコア取得手段と、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算する計算手段と、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定するように構成された検索結果特定手段とを備え、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、ことを特徴とするシステム。
（付記９′）前記訓練インスタンス重み生成手段は、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得するサブ手段と、
訓練インスタンス同士の類似度に基づいて、訓練インスタンスのそれぞれのソートスコアを取得するサブ手段と、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得する重み補正サブ手段とを備え、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、
ことを特徴とする付記８′に記載のシステム。
（付記１０′）前記テストインスタンスソートスコア取得手段は、前記訓練パッケージ及び前記テストパッケージにおける全てのインスタンスについて、全てのインスタンス間の類似度に基づいて、各テストインスタンスのソートスコアを取得するように構成され、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする付記８′に記載のシステム。
【特許請求の範囲】
【請求項１】
複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索方法であって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該方法は、コンピュータが、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得し、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得し、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算し、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定することを含み、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、
ことを特徴とする方法。
【請求項２】
前記の、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成することは、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得し、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得し、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得することを含み、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、ことを特徴とする請求項１に記載の方法。
【請求項３】
前記一つまたは複数の訓練パッケージに負の訓練パッケージが更に含まれ、前記の、各訓練インスタンスについて前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくし、
前記負の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくすることを含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記の、前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアのうち最も大きい訓練インスタンスの重みを変更することを含む、
ことを特徴とする請求項２又は３に記載の方法。
【請求項５】
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することは、
グラフによるアルゴリズムに基づいて学習を行う過程で構築された重み付きグラフにおけるノードに対応する訓練インスタンス間の一次又は高次の伝達関係に基づく類似度に基づいて、前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することを含み、
前記重み付きグラフにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みが該辺と接続する2つのノードの間の類似度に対応する、
ことを特徴とする請求項２に記載の方法。
【請求項６】
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度及び前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得することは、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを取得することを含み、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする請求項１に記載の方法。
【請求項７】
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算することは、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとすることを含む、
ことを特徴とする請求項１に記載の方法。
【請求項８】
複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索システムであって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該システムは、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得するように構成された取得手段と、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成された訓練インスタンス重み生成手段と、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得するように構成されたテストインスタンスソートスコア取得手段と、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算する計算手段と、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定するように構成された検索結果特定手段とを備え、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、ことを特徴とするシステム。
【請求項９】
前記訓練インスタンス重み生成手段は、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得するサブ手段と、
訓練インスタンス同士の類似度に基づいて、訓練インスタンスのそれぞれのソートスコアを取得するサブ手段と、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得する重み補正サブ手段とを備え、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、
ことを特徴とする請求項８に記載のシステム。
【請求項１０】
前記テストインスタンスソートスコア取得手段は、前記訓練パッケージ及び前記テストパッケージにおける全てのインスタンスについて、全てのインスタンス間の類似度に基づいて、各テストインスタンスのソートスコアを取得するように構成され、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする請求項８に記載のシステム。
【請求項１】
複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索方法であって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該方法は、コンピュータが、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得し、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成し、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得し、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算し、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定することを含み、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、
ことを特徴とする方法。
【請求項２】
前記の、前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成することは、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得し、
訓練インスタンス同士の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って訓練インスタンスのそれぞれのソートスコアを取得し、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得することを含み、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、ことを特徴とする請求項１に記載の方法。
【請求項３】
前記一つまたは複数の訓練パッケージに負の訓練パッケージが更に含まれ、前記の、各訓練インスタンスについて前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを大きくし、
前記負の訓練パッケージにおける各訓練インスタンスについて、正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて、正の近隣するインスタンスセットにおける訓練インスタンスの重みを小さくすることを含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記の、前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアに基づいて前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更することは、
前記正の近隣するインスタンスセットにおける訓練インスタンスのソートスコアのうち最も大きい訓練インスタンスの重みを変更することを含む、
ことを特徴とする請求項２又は３に記載の方法。
【請求項５】
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することは、
グラフによるアルゴリズムに基づいて学習を行う過程で構築された重み付きグラフにおけるノードに対応する訓練インスタンス間の一次又は高次の伝達関係に基づく類似度に基づいて、前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定することを含み、
前記重み付きグラフにおいて、ノードが訓練パッケージにおける全ての訓練インスタンスに対応し、辺の重みが該辺と接続する2つのノードの間の類似度に対応する、
ことを特徴とする請求項２に記載の方法。
【請求項６】
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度及び前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得することは、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、全てのインスタンス間の類似度に基づいて、グラフによるアルゴリズムを採用して学習を行って各テストインスタンスのソートスコアを取得することを含み、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする請求項１に記載の方法。
【請求項７】
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算することは、
テストパッケージにおけるテストインスタンスのそれぞれに対応するソートスコアの最大値を当該テストパッケージのソートスコアとすることを含む、
ことを特徴とする請求項１に記載の方法。
【請求項８】
複数のテストパッケージを記憶している記憶装置から一つまたは複数の訓練パッケージに基づいて一つまたは複数のテストパッケージを検索する、マルチインスタンス学習による検索システムであって、各訓練パッケージは訓練インスタンスを含み、各テストパッケージはテストインスタンスを含み、当該システムは、
正の訓練パッケージを含む一つまたは複数の訓練パッケージを入力インターフェースを介して取得するように構成された取得手段と、
前記正の訓練パッケージにおける訓練インスタンス毎に重みを生成するように構成された訓練インスタンス重み生成手段と、
前記訓練パッケージ及び前記テストパッケージにおけるインスタンスの全てについて、インスタンス間の類似度および前記前記正の訓練パッケージにおける各訓練インスタンスの重みを用いて、各テストインスタンスのソートスコアを取得するように構成されたテストインスタンスソートスコア取得手段と、
各テストパッケージに含まれるテストインスタンスのそれぞれのソートスコアに基づいて各テストパッケージのソートスコアを計算する計算手段と、
前記記憶装置に記憶されている各テストパッケージのソートスコアに基づいて一つまたは複数のテストパッケージを検索結果として特定するように構成された検索結果特定手段とを備え、
前記訓練インスタンスについての重みの絶対的な大きさは、対応する訓練インスタンスがユーザの検索意図を表現可能な度合いを表す、ことを特徴とするシステム。
【請求項９】
前記訓練インスタンス重み生成手段は、
前記正の訓練パッケージにおける訓練インスタンスの初期重みを記憶装置から取得するサブ手段と、
訓練インスタンス同士の類似度に基づいて、訓練インスタンスのそれぞれのソートスコアを取得するサブ手段と、
前記訓練パッケージにおける各訓練インスタンスについて正の近隣するインスタンスセットを特定し、前記正の近隣するインスタンスセットにおける訓練インスタンスのそれぞれのソートスコアに基づいて、前記正の近隣するインスタンスセットにおける訓練インスタンスの重みを変更して、前記正の訓練パッケージにおける訓練インスタンスのそれぞれの最終的な重みを取得する重み補正サブ手段とを備え、
前記訓練インスタンスの正の近隣するインスタンスセットとは、正の訓練パッケージのうち、当該訓練インスタンスと予め設けられた類似関係を有する訓練インスタンスの集合である、
ことを特徴とする請求項８に記載のシステム。
【請求項１０】
前記テストインスタンスソートスコア取得手段は、前記訓練パッケージ及び前記テストパッケージにおける全てのインスタンスについて、全てのインスタンス間の類似度に基づいて、各テストインスタンスのソートスコアを取得するように構成され、
前記正の訓練パッケージにおける各訓練インスタンスの初期ラベルはそれぞれの重みにより決められる、
ことを特徴とする請求項８に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１３−４０９３（Ｐ２０１３−４０９３Ａ）
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願番号】特願２０１２−１３２９１５（Ｐ２０１２−１３２９１５）
【出願日】平成２４年６月１２日（２０１２．６．１２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願日】平成２４年６月１２日（２０１２．６．１２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]