(57)【要約】【課題】データポイントへのラベル付与を高速かつ精度よくおこなう。【解決手段】スコア計算部１１は、データポイントおよびデータポイント間の類似度からなるグラフと、計算対象のラベル集合とを入力とし、ラベルごとに各ノードにおけるスコアの下限値と上限値を計算する。そして、ラベル選択部１２は、スコア計算部１１により計算されたスコアの下限値と、上限値を入力とし、計算対象のラベルを出力する。スコア計算部１１およびラベル選択部１２は、計算対象のラベルの集合が空集合φとなるまで、繰り返し計算回数を示すカウンタｔをインクリメントして上記処理を繰り返すことで、繰り返し計算の中で再帰的に各ノードのスコアの下限値と上限値を推定し、ラベル未付与のデータポイントへラベル付与をおこなうために不要なスコアの計算を除外する。【選択図】図１７
2015232781.tif 000002
【特許請求の範囲】
【請求項１】
記憶部と協働して処理を実行する制御部を有するラベリング装置であって、
前記制御部は、
データポイントと、初期ラベル集合との入力を受け付け、
各前記データポイントに対する計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値について、０回目の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値を、前記計算対象のラベル集合を前記初期ラベル集合として計算し、ｔ回目（ｔは自然数）の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値を（ｔ−１）回目の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値に基づき再帰的に計算する処理と、
再帰的に計算した前記ｔ回目の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値に対して、所定条件を満たす前記ｔ回目の計算対象のラベル集合が含むラベルを（ｔ＋１）回の計算対象のラベル集合へ追加し、前記所定条件を満たさない前記ｔ回目の計算対象のラベル集合が含むラベルを前記（ｔ＋１）回の計算対象のラベル集合への追加対象から除外する処理と
の各処理を前記ｔ回目の計算対象のラベル集合もしくは前記（ｔ＋１）回の計算対象のラベル集合が空集合となるまでｔについて再帰的に繰り返す
ことを特徴とするラベリング装置。
【請求項２】
さらに、
前記制御部は、
各前記データポイントに対して、前記ｔ回目の計算対象のラベル集合が空集合となった際の前記（ｔ−１）回目の計算対象のラベル集合が含むラベルのうち、もしくは、前記（ｔ＋１）回目の計算対象のラベル集合が空集合となった際の前記ｔ回目の計算対象のラベル集合が含むラベルのうち、前記下限値に最大値を与えるラベルを、当該データポイントに付与するラベルと決定する
ことを特徴とする請求項１に記載のラベリング装置。
【請求項３】
ラベリング装置が実行するラベリング方法であって、
前記ラベリング装置が、
データポイントと、初期ラベル集合との入力を受け付け、
各前記データポイントに対する計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値について、０回目の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値を、前記計算対象のラベル集合を前記初期ラベル集合として計算し、ｔ回目（ｔは自然数）の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値を（ｔ−１）回目の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値に基づき再帰的に計算する処理と、
再帰的に計算した前記ｔ回目の計算対象のラベル集合が含むラベルごとの前記所定スコアの下限値および上限値に対して、所定条件を満たす前記ｔ回目の計算対象のラベル集合が含むラベルを（ｔ＋１）回の計算対象のラベル集合へ追加し、前記所定条件を満たさない前記ｔ回目の計算対象のラベル集合が含むラベルを前記（ｔ＋１）回の計算対象のラベル集合への追加対象から除外する処理と
の各処理を前記ｔ回目の計算対象のラベル集合もしくは前記（ｔ＋１）回の計算対象のラベル集合が空集合となるまでｔについて再帰的に繰り返す
こと含むことを特徴とするラベリング方法。
【請求項４】
さらに、
前記ラベリング装置が、
各前記データポイントに対して、前記ｔ回目の計算対象のラベル集合が空集合となった際の前記（ｔ−１）回目の計算対象のラベル集合が含むラベルのうち、もしくは、前記（ｔ＋１）回目の計算対象のラベル集合が空集合となった際の前記ｔ回目の計算対象のラベル集合が含むラベルのうち、前記下限値に最大値を与えるラベルを、当該データポイントに付与するラベルと決定する
ことを含むこと特徴とする請求項３に記載のラベリング方法。
【請求項５】
請求項１または２に記載のラベリング装置としてコンピュータを機能させるラベリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベリング装置などに関する。
【背景技術】
【０００２】
データポイントと、データポイント間の類似度からなるグラフにおいて、ラベルが付与されているデータポイントに基づき、ラベルが付与されていないデータポイントへラベルを付与する、半教師あり学習という技術がある。半教師あり学習は、機械学習において注目が集まっている技術の一つであり、様々な手法が提案されている。例えば、Label  Propagationは、半教師あり学習において用いられる手法の一つである。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Dengyong  Zhou，Olivier  Bousquet，Thomas  Navin  Lal，JasonWeston，and  Bernhard  Schoelkopf，“Learning  with  Local  and  Global  Consistency”，Max  Plank  Institute  for  Biological  Cybernetics，Germany，2003
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述の従来技術におけるLabel  Propagationは、同じクラスタに属するデータポイントは同じ意味的なラベルを共有するという前提に基づき、データポイントへラベル付与をおこなう。具体的には、Label  Propagationは、大量のデータポイントによって明らかになるクラスタ構造に基づき、ラベルが付与されたデータポイントからラベルが付与されていないデータポイントへスコアを伝搬させてラベル付与をおこなう。このため、Label  Propagationは、データポイントの数が多いほど、より高い精度でラベル付与をおこなうことができる。
【０００５】
一方、Label  Propagationは、データポイントの数が多いほど計算コストが高くなるという問題がある。すなわち、ラベル付与に用いるスコアは、コスト関数と呼ばれる関数を最小化する値に対応する。コスト関数に対する最適解は、データポイントから構成されるグラフ（例えばk-NN（k-Nearest  Neighbor  algorithm）グラフなど）の隣接行列の逆行列から求めることができる。
【０００６】
ここで、ｎをデータポイントの数とすると、グラフの隣接行列の大きさはＯ（ｎ２）のオーダであるため、逆行列を求めるにはＯ（ｎ３）の計算コストが必要になる。その結果、ｃをラベルの数とすると、データポイントへラベル付与をおこなうためには、Ｏ（ｎ３＋ｃｎ２）のオーダの計算コストが必要となる。そのため、データポイントの数が多くなると、ラベル付与の効率が低下する。なお、Ｏ（＊）は、ランダウ記号である。
【０００７】
そこで、Label  Propagationは、高速にスコア計算を行うために、ベキ乗法を用いてスコアを繰り返し計算する。ベキ乗法によるスコア計算は、最適スコアに収束する性質を有する。しかし、繰り返し計算はスコアの残差が事前に設定した値より小さくなると終了するため、ベキ乗法により計算されたスコアは残差を含む。よって、ベキ乗法により計算されたスコアは、理論的スコアから乖離するため、ラベル付与の精度に問題がある。
【０００８】
本願が開示する実施形態の一例は、上記に鑑みてなされたものであって、ラベルが付与されていないデータポイントへラベルを高速かつ精度よく付与することを目的とする。
【課題を解決するための手段】
【０００９】
本願が開示する実施形態の一例は、データポイントと、初期ラベル集合との入力を受け付ける。そして、実施形態の一例は、各データポイントに対する計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値について、０回目の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値を、計算対象のラベル集合を初期ラベル集合として計算する。そして、実施形態の一例は、ｔ回目（ｔは自然数）の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値を（ｔ−１）回目の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値に基づき再帰的に計算する処理と、再帰的に計算したｔ回目の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値に対して、所定条件を満たすｔ回目の計算対象のラベル集合が含むラベルを（ｔ＋１）回の計算対象のラベル集合へ追加し、所定条件を満たさないｔ回目の計算対象のラベル集合が含むラベルを（ｔ＋１）回の計算対象のラベル集合への追加対象から除外する処理との各処理をｔ回目の計算対象のラベル集合もしくは（ｔ＋１）回の計算対象のラベル集合が空集合となるまでｔについて再帰的に繰り返す。
【発明の効果】
【００１０】
本願が開示する実施形態の一例によれば、例えば、ラベルが付与されていないデータポイントへラベルを高速かつ精度よく付与することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、定義１を示す図である。
【図２】図２は、補助定理１を示す図である。
【図３】図３は、補助定理２を示す図である。
【図４】図４は、補助定理３を示す図である。
【図５】図５は、定義２を示す図である。
【図６】図６は、補助定理４を示す図である。
【図７】図７は、補助定理５を示す図である。
【図８】図８は、補助定理６を示す図である。
【図９】図９は、補助定理７を示す図である。
【図１０】図１０は、補助定理８を示す図である。
【図１１】図１１は、定義３を示す図である。
【図１２】図１２は、補助定理９を示す図である。
【図１３】図１３は、補助定理１０を示す図である。
【図１４】図１４は、補助定理１１を示す図である。
【図１５】図１５は、定理１を示す図である。
【図１６】図１６は、定理２を示す図である。
【図１７】図１７は、ラベリング装置の構成の一例を示すブロック図である。
【図１８】図１８は、ラベル付与処理の一例を示すフローチャートである。
【図１９】図１９は、ラベル付与処理アルゴリズムの一例を示す図である。
【図２０】図２０は、ラベル付与プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
実施形態の説明に先立ち、以下の説明で用いる主な記号の定義、従来手法の数理的背景の説明、実施形態の数理的背景の説明をおこなう。その後、実施形態を説明する。
【００１３】
［主な記号の定義］
実施形態で用いる主な記号を下表に示す。以下、従来手法の数理的背景、実施形態の数理的背景、実施形態の各説明において、同一の記号を用いる。
【００１４】
【表１】
2015232781.tif 000003
【００１５】
［従来手法の数理的背景］
以下、従来手法の数理的背景を説明する。データポイントの集合ＸをＸ＝｛Ｘ１，・・・，Ｘｍ，Ｘｍ＋１，・・・，Ｘｎ｝（ｎは、Ｘの要素数、１＜ｍ＜ｎ）、ラベルの集合Ｌ＝｛ｌ１，・・・，ｌｃ｝（ｃはＬの要素数）とする。以下、Ｌを「初期ラベル集合」と呼ぶ。ここで、Ｘの部分集合｛Ｘ１，・・・，Ｘｍ｝をラベル付与済みのデータポイントの集合とし、Ｘ＼｛Ｘ１，・・・，Ｘｍ｝＝｛Ｘｍ＋１，・・・，Ｘｎ｝を、ラベル未付与のデータポイントの集合とする。従来手法であるLabel  Propagationは、以下に述べる手順で、ラベル未付与のデータポイントに対してラベル付与する。
【００１６】
まず、データポイントの集合Ｘがノード集合Ｖに対応する、すなわちＶ＝ＸとなるグラフＧ＝｛Ｖ，Ｅ｝を構築する。グラフＧは、データポイントをノードとする。Ｅは、エッジの集合であり、各エッジの重みが、例えばデータポイント間の類似度に対応する。
【００１７】
グラフ構築の手法として種々の手法を用いることができるが、ｋ−ＮＮ（k-Nearest  Neighbor  algorithm）グラフを用いるとする。ｋ−ＮＮグラフにおいて、２つのノードがｋ近傍であれば、この２つのノード間のエッジは無向エッジとなる。そのため、ｋ−ＮＮグラフは、対称グラフとなる。また、ｋ−ＮＮグラフにおけるエッジ数はＯ（ｎ）のオーダである。なお、Ｏ（＊）は、ランダウ記号である。
【００１８】
一般的に、エッジの重みは、ガウシアンカーネル（Gaussian  Kernel）を用いて計算される。すなわち、データポイントｘｉとｘｊの間のエッジの重みＷｉｊは、これらのデータポイントがｋ近傍であればＷｉｊ＝ｅｘｐ｛−||ｘｉ−ｘｊ||２／２σ２｝となり、ｋ近傍でなければＷｉｊ＝０となる。Ｗｉｊは、ｋ−ＮＮグラフにおけるｎ×ｎの隣接行列Ｗのｉｊ成分となる。なお、||＊||はＬ２ノルムであり、σはハイパーパラメータである。
【００１９】
そして、ラベル未付与のデータポイントに対して付与するラベルを決定するために、各データポイントのスコアを計算する。Label  Propagationにおいて、ラベルのスコアは、後述するコスト関数を最小化する最適解として定義される。
【００２０】
ｎ×ｃの行列Ｆ（以下、行列Ｆを分類行列と呼ぶ）は、各データポイントにおけるラベルごとのスコアを保持する。分類行列Ｆは、ラベル付与済みのデータポイントからラベル未付与のデータポイントへ、スコアを伝搬させてラベル付与するために用いられる。
【００２１】
そして、ｎ×ｃの初期ラベル行列Ｙの各成分は、初期値として、データポイントｘｉへｙ（ｘｉ）＝ｌｉとラベル付与されていればＹｉｊ＝１であり、ラベル付与されていなければＹｉｊ＝０である。ベクトルＦｉを分類行列Ｆにおける第ｉ行ベクトルとし、ベクトルＹｉを初期ラベル行列Ｙにおける第ｉ行ベクトルとすると、Ｆ＝［Ｆ１，Ｆ２，・・・，Ｆｎ］Ｔであり、Ｙ＝［Ｙ１，Ｙ２，・・・，Ｙｎ］Ｔである。ただし、＊Ｔは、行列もしくはベクトルの転置を表す。
【００２２】
分類行列Ｆに関するコスト関数Ｃ（Ｆ）は、式（１）のように定義される。コスト関数Ｃ（Ｆ）は、ラベルの推定の精度を向上させるように定義される。
【００２３】
【数１】
2015232781.tif 000004
【００２４】
コスト関数Ｃ（Ｆ）の右辺第１項は、近傍のデータポイントであれば類似スコアを有するという条件に対応し、右辺第２項は最終的なラベリング結果が最初の付与ラベルと類似するという条件に対応する。コスト関数Ｃ（Ｆ）を最小にする最適スコアを与える分類行列Ｆは、式（２）のようになる。
【００２５】
【数２】
2015232781.tif 000005
【００２６】
ここで、ラベルｌｉに対応する分類行列Ｆの第ｉ列ベクトルをベクトルｆｉ（１≦ｉ≦ｃ）とする。また、データポイントｘｉに対応するベクトルｆｊのｉ番目の要素をｆ（ｘｉ｜ｌｊ）とする。データポイントｘｉのラベルｙ（ｘｉ）は、式（３）により求める。
【００２７】
【数３】
2015232781.tif 000006
【００２８】
式（２）は、ラベルのスコアを求めるためには、逆行列の計算が必要であることを示す。分類行列Ｆは、行列（Ｉ−αＳ）−１と初期ラベル行列Ｙの行列積である。行列（Ｉ−αＳ）はｎ×ｎであることから、逆行列（Ｉ−αＳ）−１の計算は、Ｏ（ｎ３）のオーダの計算コストが必要となる。また、逆行列（Ｉ−αＳ）−１はｎ×ｎであり、初期ラベル行列Ｙはｎ×ｃであるため、行列（Ｉ−αＳ）−１と初期ラベル行列Ｙの行列積の計算は、Ｏ(ｃｎ２)のオーダの計算コストが必要となる。よって、分類行列Ｆの計算は、Ｏ（ｎ３＋ｃｎ２）のオーダの計算コストが必要となる。すなわち、従来手法であるLabel  Propagationは、Ｏ（ｎ３＋ｃｎ２）という非常に高い計算コストを必要とする。
【００２９】
そこで、Label  Propagationは、ラベリングの計算速度を向上させるために、ベキ乗法を用いて分類行列Ｆを求める。Label  Propagationにおいてベキ乗法を用いる手法は、標準的な手法となっている。ベキ乗法を用いて分類行列Ｆを求める手法は、式（４）において、分類行列Ｆを求める際のｔ回目の繰り返し計算における行列Ｆｔを、ｔについて再帰的に更新することにより求める。
【００３０】
【数４】
2015232781.tif 000007
【００３１】
式（４）に基づき、ベキ乗法により行列Ｆｔにおいてｔ→∞とすると、Ｆｔは収束し、最適な分類行列Ｆになるという性質、すなわちＦ∞＝Ｆとなる性質がある。しかし、実際は、ベキ乗法による分類行列Ｆの計算は、スコアの残差が所定値以下となるまで、有限回だけ繰り返されるに過ぎない。よって、ベキ乗法による分類行列Ｆの計算結果は、残差を含んだ結果となり、理論的に最適な分類行列Ｆから乖離する。このため、ラベル付与済みのデータポイントからラベル未付与のデータポイントへ、ベキ乗法により計算された分類行列Ｆによりスコアを伝搬させてラベル付与すると、ラベル付与の精度が低くなるというデメリットがある。
【００３２】
［実施形態の数理的背景］
次に、実施形態の数理的背景を説明する。実施形態は、全てのラベルに対して収束するまでスコアを計算するベキ乗法による従来手法とは異なり、全てのラベルに対してスコアを計算することはおこなわず、ラベルに対して選択的にスコアを計算する。実施形態における計算対象とラベルの選択は、ラベルのスコアの下限値と上限値を用いておこなう。
【００３３】
実施形態は、式（４）におけるｔ回目の繰り返し計算（ｔ＝０，１，２，・・・）における計算対象のラベル集合Ｌｔに対する下限値と上限値を計算する。ラベル集合Ｌｔの求め方については後述する。ｙｉを初期ラベル行列Ｙにおける第ｉ列ベクトルとし、ｙ（ｘｉ｜ｌｊ）をベクトルｙｉにおけるｉ番目の要素とする。ここで、ベクトルｙｉは、初期値としてｌｊとラベル付与されるデータポイントｘｉのスコアに対応する。また、ｙ（ｘｉ｜ｌｊ）＝Ｙｉｊは、ラベルｌｊに対するデータポイントｘｉの初期ラベルのスコアに対応する。
【００３４】
ラベルのスコアの下限値と上限値を求めるために、ラベル付与済みのデータポイントからラベル未付与のデータポイントへ、スコアを伝搬させるための伝搬スコアｐｔ（ｘｉ｜ｌ）を用いる。データポイントｘｉのラベルｌのｔ回目の繰り返し計算における伝搬スコアｐｔ（ｘｉ｜ｌ）は、式（５）に基づき計算される。
【００３５】
【数５】
2015232781.tif 000008
【００３６】
式（５）は、伝搬スコアは、ｔ＝０であればデータポイントｘｉの初期ラベルのスコアに初期化され、ｔ≠０であればｋ−ＮＮグラフにおけるｎ×ｎの隣接行列Ｗの正規化行列Ｓ（表１参照）を用い、１つ前の繰り返し計算の結果から逐次的に更新されることを示す。ただし、Ｓｉｊは正規化行列Ｓのｉｊ成分である。そして、データポイントｘｉのラベルｌに対するスコアの下限値は、伝搬スコアｐｔ（ｘｉ｜ｌ）を用いて、図１の定義１における式（６）に基づき計算される。
【００３７】
そして、下記の（Ａ）が成り立つことを示す前に、補助定理１および補助定理２が成り立つことを示す。補助定理１およびその証明は図２に示すとおりであり、補助定理２およびその証明は図３に示すとおりである。
【００３８】
【数６】
2015232781.tif 000009
【００３９】
そして、補助定理１および補助定理２を用いて、上記の（Ａ）が成り立つこと、すなわち補助定理３が成り立つことを示す。補助定理３およびその証明は、図４に示すとおりである。
【００４０】
また、データポイントｘｉのラベルｌに対するスコアの上限値は、伝搬スコアｐｔ（ｘｉ｜ｌ）を用いて、図５の定義２における式（９）に基づき計算される。
【００４１】
【数７】
2015232781.tif 000010
【００４２】
そして、上記の（Ｂ）が成り立つことを示す前に、補助定理４および補助定理５が成り立つことを示す。補助定理４およびその証明は図６に示すとおりであり、補助定理５およびその証明は図７に示すとおりである。
【００４３】
そして、補助定理４および補助定理５を用いて、上記の（Ｂ）が成り立つこと、すなわち補助定理６が成り立つことを示す。補助定理６およびその証明は、図８に示すとおりである。
【００４４】
実施形態は、下限値および上限値を逐次的に計算するが、下限値および上限値を計算するために、ｔについて、初回の計算時（ｔ＝０）にのみ上記の定義１および定義２をそれぞれ用い、２回目以降（ｔ≧１）の逐次計算は、図９の補助定理７で示す性質を用いて、効率的に逐次計算をおこなう。
【００４５】
【数８】
2015232781.tif 000011
【００４６】
補助定理７は、上記の（Ｃ）を図１の定義１および図５の定義２から計算することで得ることができる。
【００４７】
【数９】
2015232781.tif 000012
【００４８】
そして、上記の（Ｄ）の収束値については、図１０の補助定理８で示す性質がある。補助定理８は、補助定理４から得られるｐｔ（ｘｉ｜ｌ）≦ｎという性質を用いて、式（６）と式（９）から求めることができる。補助定理８は、繰り返し計算回数が増えるほど下限値と上限値の精度が向上していくことを示す。さらに補助定理８は、実施形態による手法が、最適なスコアによる従来手法と同じラベル付与の結果を与えることを示す。
【００４９】
次に、ｔ回目の繰り返し計算において計算対象となるラベルの集合について述べる。まず、ラベル集合Ｌｔの定義について述べ、次にラベル集合Ｌｔの性質について述べる。ラベル集合Ｌｔは、その下限値および上限値を用いて計算する。ｔ回目の繰り返し計算におけるラベル集合Ｌｔは、図１１の定義３のように定義される。
【００５０】
そして、ラベル集合Ｌｔの性質について、図１２の補助定理９および図１３の補助定理１０が成り立つ。そして、補助定理９および補助定理１０から、ラベル集合Ｌｔに関して、図１４の補助定理１１が成り立つ。
【００５１】
補助定理１１から、実施形態は、最適なスコアによる従来手法と同様にラベル付与の結果を得ることができる。そして、以上の数理的考察から、実施形態におけるラベル付与の結果と計算量について、図１５の定理１および図１６の定理２が成り立つ。
【００５２】
すなわち、実施形態は、最適なスコアによる従来手法と同様に、ラベル付与済みのデータポイントのスコアに基づき、ラベル未付与のデータポイントに対してラベル付与する。また、実施形態における、ラベル未付与のデータポイントに対してラベル付与する際の計算量は、最適なスコアによる従来手法よりも削減される。
【００５３】
［実施形態］
上記の数理的議論を踏まえ、以下、本願が開示するラベリング装置などの実施形態を、図面に基づいて説明する。以下の実施形態は、データポイントと、データポイント間の類似度からなるグラフと、ラベル付けされた複数のデータポイントとを入力とし、ラベルごとのスコアを計算し、ラベル付けされていないデータポイントに対してラベル付与する。なお、以下の実施形態は、一例を示すに過ぎず、本願が開示する技術を限定するものではない。
【００５４】
（ラベリング装置の構成）
図１７は、ラベリング装置の構成の一例を示すブロック図である。実施形態のラベリング装置１０は、スコア計算部１１、ラベル選択部１２、ラベル決定部１３を有する。ラベリング装置１０は、データポイントおよびデータポイント間の類似度からなるグラフと、ラベル付与された複数のデータポイントを入力とし、ラベルごとのスコアを計算し、ラベル付与されていないデータポイントへ付与するラベルを出力する。
【００５５】
具体的には、スコア計算部１１は、データポイントおよびデータポイント間の類似度からなるグラフと、計算対象のラベル集合とを入力とし、ラベルごとに各ノードにおけるスコアの下限値と上限値を計算する。そして、ラベル選択部１２は、スコア計算部１１により計算されたスコアの下限値と、上限値を入力とし、計算対象のラベルを出力する。スコア計算部１１およびラベル選択部１２は、計算対象のラベルの集合が空集合φとなるまで、繰り返し計算回数を示すカウンタｔをインクリメントして上記処理を繰り返すことで、繰り返し計算の中で再帰的に各ノードのスコアの下限値と上限値を推定し、ラベル未付与のデータポイントへラベル付与をおこなうために不要なスコアの計算を枝刈り、つまり除外する。そして、ラベル決定部１３は、全てのデータポイントについて、対応するスコアの下限値と、上限値を入力とし、ラベル未付与のデータポイントに対するラベルを決定する。
【００５６】
（ラベル付与処理）
図１８は、ラベル付与処理の一例を示すフローチャートである。先ず、図１７に示すラベリング装置１０は、ｋ−ＮＮグラフにおけるｎ×ｎの隣接行列Ｗ、ｋ−ＮＮグラフにおいて既にラベル付与されているデータポイントの集合Ｘ＝｛Ｘ１，・・・，Ｘｍ｝の入力を受け付ける（ステップＳ１１）。そして、ラベリング装置１０は、式（４）の繰り返し計算の繰り返し回数を示すカウンタｔについてｔ＝０と初期化し、式（４）におけるｔ回目の繰り返し計算（ｔ＝０，１，２，・・・）における計算対象のラベルの集合ＬｔについてＬｔ＝Ｌ（Ｌは、初期ラベル集合）と初期化する（ステップＳ１２）。
【００５７】
次に、ラベリング装置１０のスコア計算部１１は、ステップＳ１３〜Ｓ２３のループ処理を、ｌｊ∈Ｌｔなる全てのラベルｌｊについて順次繰り返して実行する。すなわち、スコア計算部１１は、ｔ＝０ならば（ステップＳ１４；Ｙｅｓ）、ステップＳ１５〜Ｓ１８のループ処理を、ｘｉ∈Ｘなる全てのデータポイントｘｉについて順次繰り返して実行する。
【００５８】
ステップＳ１６では、スコア計算部１１は、式（５）に基づき、ｌｊ，ｘｉに関する伝搬スコアｐｔ（ｘｉ｜ｌｊ）を計算する。そして、ステップＳ１７では、スコア計算部１１は、定義１の式（６）（図１参照）および定義２の式（９）（図５参照）に基づき、ラベルの伝搬スコアからスコアｆ（ｘｉ｜ｌｊ）の下限値および上限値をそれぞれ計算する。
【００５９】
一方、スコア計算部１１は、ｔ≠０ならば（ステップＳ１４；Ｎｏ）、ステップＳ１９〜Ｓ２２のループ処理を、ｘｉ∈Ｘなる全てのデータポイントｘｉについて順次繰り返して実行する。ステップＳ２０では、スコア計算部１１は、式（５）に基づき、ｌｊ，ｘｉに関する伝搬スコアＰｔ（ｘｉ｜ｌｊ）を、隣接行列Ｗの正規化行列Ｓのｉｊ成分Ｓｉｊと、伝搬スコアＰｔ−１（ｌｊ｜ｘｉ）をもとに更新する。そして、ステップＳ２１では、スコア計算部１１は、補助定理７の式（１２）および（１３）（図９参照）に基づき、ラベルの伝搬スコアからスコアｆ（ｘｉ｜ｌｊ）の下限値および上限値をそれぞれ更新する。
【００６０】
ステップＳ１３〜Ｓ２３のループ処理が終了すると、ラベリング装置１０のラベル選択部１２は、計算対象のラベルの集合Ｌｔの次回の繰り返し計算対象のラベルの集合Ｌｔ＋１についてＬｔ＋１＝φと初期化する（ステップＳ２４）。
【００６１】
次に、ラベル選択部１２は、ステップＳ２５〜Ｓ３１のループ処理を、ｘｉ∈Ｘなる全てのデータポイントｘｉについて順次繰り返して実行する。さらに、ラベル選択部１２は、ステップＳ２５〜Ｓ３１のループ処理内において、ステップＳ２６〜Ｓ３０のループ処理を、ｌｊ∈Ｌｔなる全てのラベルｌｊについて順次繰り返して実行する。
【００６２】
ステップＳ２７では、ラベル選択部１２は、次の式（Ｅ）であるようなｌｋ∈Ｌ（Ｌは、初期ラベル集合）が存在するか否かを判定する。
【００６３】
【数１０】
2015232781.tif 000013
【００６４】
ラベル選択部１２は、ステップＳ２７の判定がＹｅｓのとき、ステップＳ２８へ処理を移。ステップＳ２８では、ラベル選択部１２は、全てのｌｋ∈Ｌ（Ｌは、初期ラベル集合）について次の式（Ｆ）のような条件が満たれるか否かを判定する。
【００６５】
【数１１】
2015232781.tif 000014
【００６６】
なお、ステップＳ２７またはステップＳ２８のいずれかの判定がＮｏであることは、定義３（図１１参照）に示す、ｌｊ∈ＬｔなるラベルｌｊがＬｔ＋１に含まれる条件（ｉ）かつ（ii）の対偶である。
【００６７】
ラベル選択部１２は、ステップＳ２８の判定がＹｅｓの場合、ラベルｌｊをラベルの集合Ｌｔ＋１へ追加する（ステップＳ２９）。一方、ラベル選択部１２は、ステップＳ２７またはステップＳ２８のいずれかの判定がＮｏの場合、ステップＳ３０へ処理を移す、すなわち、ステップＳ２６〜Ｓ２９のループ処理において、次のラベルｌｊ∈Ｌｔを選択して当該のループ処理を継続する。
【００６８】
ラベル選択部１２は、ステップＳ２６〜Ｓ３０のループ処理が終了し、ステップＳ２５〜Ｓ３１のループ処理が終了すると、ステップＳ３２へ処理を移す。ステップＳ３２では、ラベリング装置１０は、ラベル集合Ｌｔ≠φか否かを判定し、ステップＳ３２の判定がＹｅｓの場合、ｔ＝ｔ＋１とｔを１インクリメントし（ステップＳ３３）、ステップＳ３４へ処理を移す。一方、ラベリング装置１０は、ステップＳ３２の判定がＮｏの場合、ステップＳ３４へ処理を移す。
【００６９】
ステップＳ３４では、ラベリング装置１０は、ラベル集合Ｌｔ＝φか否かを判定し、ステップＳ３４の判定がＹｅｓの場合、ステップＳ３５へ処理を移し、ステップＳ３４の判定がＮｏの場合、ステップＳ１３へ処理を移す。
【００７０】
次に、ラベリング装置１０のラベル決定部１３は、ステップＳ３５〜Ｓ３７のループ処理を、ｘｉ∈Ｘなる全てのデータポイントｘｉについて順次繰り返して実行する。
【００７１】
ステップＳ３６では、ラベル決定部１３は、下記の式（１４）に基づき、データポイントｘｉのラベルｙ（ｘｉ）を求める（ただし、ｌｊ∈Ｌ）。
【００７２】
【数１２】
2015232781.tif 000015
【００７３】
ラベル決定部１３は、ステップＳ３５〜Ｓ３７のループ処理が終了すると、ステップＳ３８へ処理を移す。ステップＳ３８では、ラベリング装置１０は、全てがラベル付けされたデータポイントｘｉおよび対応するラベルｙ（ｘｉ）のデータセットを出力する。ステップＳ３８が終了すると、ラベル付与処理は終了する。
【００７４】
（ラベル付与処理アルゴリズム）
図１９は、ラベル付与処理アルゴリズムの一例を示す図である。図１９に示すラベル付与処理アルゴリズムの第１〜２行目は、図１８のステップＳ１２に相当する。ラベル付与処理アルゴリズムの第３〜２８行目のループ処理は、図１８のステップＳ１３〜Ｓ３４に相当する。
【００７５】
ラベル付与処理アルゴリズムの第３〜２８行目のループ処理のうち、第４〜１６行目のループ処理は、図１８のステップＳ１３〜Ｓ２３に相当する。また、ラベル付与処理アルゴリズムの第４〜１６行目のループ処理のうち、第５、１０、１５行目は、図１８のステップＳ１４に相当する。また、ラベル付与処理アルゴリズムの第４〜１６行目のループ処理のうち、第６〜９行目のループ処理は、図１８のステップＳ１５〜Ｓ１８に相当する。また、ラベル付与処理アルゴリズムの第１１〜１４行目のループ処理は、図１８のステップＳ１９〜Ｓ２２に相当する。
【００７６】
また、ラベル付与処理アルゴリズムの第３〜２８行目のループ処理のうち、第１７行目の処理は、図１８のステップＳ２４に相当する。また、ラベル付与処理アルゴリズムの第３〜２８行目のループ処理のうち、第１８〜２４行目の処理は、図１８のステップＳ２５〜Ｓ３１に相当する。また、ラベル付与処理アルゴリズムの第３〜２８行目のループ処理のうち、第１９〜２３行目の処理は、図１８のステップＳ２６〜Ｓ３０に相当する。また、ラベル付与処理アルゴリズムの第３〜２８行目のループ処理のうち、第２０〜２２行目の処理は、図１８のステップＳ２７〜Ｓ２９に相当する。また、ラベル付与処理アルゴリズムの第３〜２８行目のループ処理のうち、第２５〜２７行目の処理は、図１８のステップＳ３２〜Ｓ３３に相当する。
【００７７】
また、ラベル付与処理アルゴリズムの第２９〜３１行目のループ処理は、図１８のステップＳ３５〜Ｓ３８に相当する。
【００７８】
（実施形態の効果）
実施形態は、データポイントと、初期ラベル集合との入力を受け付ける。そして、実施形態は、各データポイントに対する計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値について、０回目の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値を、計算対象のラベル集合を初期ラベル集合として計算する。そして、実施形態は、ｔ回目（ｔは自然数）の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値を（ｔ−１）回目の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値に基づき再帰的に計算する処理と、再帰的に計算したｔ回目の計算対象のラベル集合が含むラベルごとの所定スコアの下限値および上限値に対して、所定条件を満たすｔ回目の計算対象のラベル集合が含むラベルを（ｔ＋１）回の計算対象のラベル集合へ追加し、所定条件を満たさないｔ回目の計算対象のラベル集合が含むラベルを（ｔ＋１）回の計算対象のラベル集合への追加対象から除外する処理との各処理をｔ回目の計算対象のラベル集合もしくは（ｔ＋１）回の計算対象のラベル集合が空集合となるまでｔについて再帰的に繰り返す。
【００７９】
さらに、実施形態は、各データポイントに対して、ｔ回目の計算対象のラベル集合が空集合となった際の（ｔ−１）回目の計算対象のラベル集合が含むラベルのうち、もしくは、（ｔ＋１）回目の計算対象のラベル集合が空集合となった際のｔ回目の計算対象のラベル集合が含むラベルのうち、下限値に最大値を与えるラベルを、当該データポイントに付与するラベルと決定する。
【００８０】
実施形態は、計算対象のラベルが存在しなければ、ラベルのスコアが収束していなくても繰り返し計算を打ち切る。よって、無駄なラベルのスコア計算をおこなわず、計算量を削減できる。また、実施形態によるラベル付与の結果は、最適なスコアによってラベル付与する従来技術と全く同じになる。これは、ラベルのスコアの下限値および上限値により、スコアの計算が必要でないラベルを枝刈り、すなわち除外できるからである。また、実施形態は、ベキ乗法による従来手法のように繰り返し計算を打ち切るための閾値などのパラメータ設定を必要とせず、処理の高速性とラベル付与の精度との間にトレードオフが発生するという問題を回避できる。
【００８１】
（実施形態のシステム構成について）
図１７に示したラベリング装置１０の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、ラベリング装置１０の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００８２】
また、ラベリング装置１０においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、ラベリング装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００８３】
また、実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００８４】
（プログラムについて）
また、実施形態において説明したラベリング装置１０のＣＰＵなどの制御装置が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、制御装置が実行する処理をコンピュータが実行可能な言語で記述したラベル付与プログラムを作成することもできる。この場合、コンピュータがラベル付与プログラムを実行することにより、実施形態と同様の効果を得ることができる。さらに、ラベル付与プログラムをコンピュータ読み取り可能な記録媒体に記録して、記録媒体に記録されたラベル付与プログラムをコンピュータに読み込ませて実行することにより実施形態と同様の処理を実現できる。以下に、図１７に示したラベリング装置１０と同様の機能を実現するプログラムを実行するコンピュータの一例を説明する。
【００８５】
図２０は、ラベル付与プログラムを実行するコンピュータを示す図である。コンピュータ１０００は、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらは、バス１０８０によって接続される。
【００８６】
図２０に示すように、メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。また、ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。また、ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、磁気ディスクや光ディスクなどの着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０は、例えばマウス１０５１、キーボード１０５２に接続される。また、ビデオアダプタ１０６０は、例えばディスプレイ１０６１に接続される。
【００８７】
ここで、図２０に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、ラベル付与プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。
【００８８】
また、実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出す。そして、ＣＰＵ１０２０が、ラベル付与プログラムの各手順を実行する。
【００８９】
なお、ラベル付与プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られない。すなわち、プログラムモジュール１０９３およびプログラムデータ１０９４は、着脱可能な記憶媒体に記憶され、ディスクドライブなどを介してＣＰＵ１０２０によって読み出されてもよい。
【００９０】
ラベル付与プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）など）を介して接続された他のコンピュータに記憶されていてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出され、実行されてもよい。
【００９１】
また、ラベル付与プログラムのモジュール分割は、例えば図１７に示すスコア計算部１１、ラベル選択部１２、ラベル決定部１３およびその他の処理を実行する機能部それぞれが実行する処理単位でおこなってもよい。しかし、モジュールの分割および統合は、これに限らず、処理効率や保守性などを考慮し、適宜なされてもよい。
【００９２】
以上の実施形態ならびにその変形は、本願が開示する技術に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【００９３】
１０  ラベリング装置  
１１  スコア計算部    
１２  ラベル選択部    
１３  ラベル決定部    
１０００  コンピュータ    
１０１０  メモリ          
１０２０  ＣＰＵ          
【図１】
2015232781.tif 000016
【図２】
2015232781.tif 000017
【図３】
2015232781.tif 000018
【図４】
2015232781.tif 000019
【図５】
2015232781.tif 000020
【図６】
2015232781.tif 000021
【図７】
2015232781.tif 000022
【図８】
2015232781.tif 000023
【図９】
2015232781.tif 000024
【図１０】
2015232781.tif 000025
【図１１】
2015232781.tif 000026
【図１２】
2015232781.tif 000027
【図１３】
2015232781.tif 000028
【図１４】
2015232781.tif 000029
【図１５】
2015232781.tif 000030
【図１６】
2015232781.tif 000031
【図１７】
2015232781.tif 000032
【図１８】
2015232781.tif 000033
【図１９】
2015232781.tif 000034
【図２０】
2015232781.tif 000035