(57)【要約】【課題】マッチングの修正作業において、作業に要する手数を削減する。【解決手段】本発明は、２つのラベル列のマッチングを行い、コスト最小化法により、マッチング結果ｗと最小コストＣを求め、ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によってラベル列ＳＡ，ＳＢのマッチングｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチングの距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択し、候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を操作者に提示し、該操作者から対応の正誤を取得し、該ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与え、変更されたコストを加味して、再度マッチング処理以降の処理を繰り返す。【選択図】  図１
2005165538.tif 000002
【特許請求の範囲】
【請求項１】
入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正する情報処理装置上における、ラベルの系列のマッチング誤り修正方法において、
マッチング処理手段が、前記２つのラベル列のマッチングを行い、コスト最小化法により、前記マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納するマッチング処理過程と、
修正候補選択手段が、ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によって前記ラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択過程と、
前記候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力することにより操作者に提示し、該操作者から対応の正誤を取得し、コスト付与手段が、該ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与過程と、
前記コスト付与過程で変更されたコストを加味して、再度前記マッチング処理過程以降の処理を繰り返す繰り返し過程からなることを特徴とするラベルの系列のマッチング誤り修正方法。
【請求項２】
前記コスト付与過程において、
前記操作者が前記ラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
コスト付与手段が、前記ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、前記ラベルａｉと前記ラベルｂｊの対応に低いコストを与える請求項１記載のラベルの系列のマッチング誤り修正方法。
【請求項３】
入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するラベルの系列のマッチング誤り修正装置であって、
前記２つのラベル列のマッチングを行い、コスト最小化法により、前記マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納するマッチング処理手段と、
ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によって前記ラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択手段と、
前記候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力することにより操作者に提示し、該操作者から対応の正誤を取得するインタフェース手段と、
前記ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与手段と、
前記コスト付与手段で変更されたコストを加味して、再度前記マッチング処理手段、前記修正候補選択手段、前記インタフェース手段、及び前記コスト付与手段を繰り返す繰り返し手段と、を有することを特徴とするラベルの系列のマッチング誤り修正装置。
【請求項４】
前記コスト付与手段は、
前記操作者が前記ラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
前記ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、前記ラベルａｉと前記ラベルｂｊの対応に低いコストを与える手段を含む請求項３記載のラベルの系列のマッチング誤り修正装置。
【請求項５】
入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するコンピュータに実行させるラベルの系列のマッチング誤り修正プログラムであって、
前記２つのラベル列のマッチングを行い、コスト最小化法により、前記マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納させるマッチング処理ステップと、
ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によって前記ラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択ステップと、
前記候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力させることにより操作者に提示させ、該操作者から対応の正誤を取得させるインタフェースステップと、
前記ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与ステップと、
前記コスト付与ステップで変更されたコストを加味して、再度前記マッチング処理ステップ、前記修正候補選択ステップ、前記インタフェースステップ、及び前記コスト付与ステップを、繰り返えさせる繰り返し制御ステップと、をコンピュータに実行させることを特徴とするラベルの系列のマッチング誤り修正プログラム。
【請求項６】
前記コスト付与ステップは、
前記操作者が前記ラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
前記ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、前記ラベルａｉと前記ラベルｂｊの対応に低いコストを与えるステップをコンピュータに実行させる請求項５記載のラベルの系列のマッチング誤り修正プログラム。
【請求項７】
入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するコンピュータに実行させるラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、
前記２つのラベル列のマッチングを行い、コスト最小化法により、前記マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納させるマッチング処理ステップと、
ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によって前記ラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択ステップと、
前記候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力させることにより操作者に提示させ、該操作者から対応の正誤を取得させるインタフェースステップと、
前記ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与ステップと、
前記コスト付与ステップで変更されたコストを加味して、再度前記マッチング処理ステップ、前記修正候補選択ステップ、前記インタフェースステップ、及び前記コスト付与ステップを、繰り返えさせる繰り返し制御ステップと、をコンピュータに実行させるプログラムを格納したことを特徴とするラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体。
【請求項８】
前記コスト付与ステップは、
前記操作者が前記ラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
前記ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、前記ラベルａｉと前記ラベルｂｊの対応に低いコストを与えるステップをコンピュータに実行させる請求項７記載のラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベルの系列マッチングの誤り修正方法及び装置及びプログラム及びラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体に係り、特に、たんぱく質のアミノ酸の配列等を比較するためのラベルの系列のマッチングにおいて発生するマッチングの誤りを対話的に修正するためのラベルの系列マッチングの誤り修正方法及び装置及びプログラム及びラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体に関する。
【背景技術】
【０００２】
ラベルの系列のマッチング（または対応付け）は、多くの場面で利用される。似た文章を互いにずれが最小になるように単語毎に対応付けたり、たんぱく質のアミノ酸の配列を比較したりする際に用いられる技術である。
【０００３】
近年では、マルチメディア技術の発達により、映像や音声を計算機上で扱えるようになってきている。これに伴い、原稿や台本のテキストという文字情報と、映像番組中で話者が発話している音声信号（通常、映像番組は音声を含む）を対応付けるように、異種メディア間でのマッチングを求めることも試みられるようになってきている（例えば、非特許文献１、２参照）。
【０００４】
マッチングの問題は、数学的にはあるコスト関数の下で最小化問題と捉えることができる。ここで、Ａ，Ｂをラベルの集合とする。ａをＡの元、ｂをＢの元とする（ａ∈Ａ，ｂ∈Ｂ）。Ａの元の系列ＳＡ＝｛ａ１，ａ２，ａ３，…，ａｎ｝（ａｉ∈Ａ，１≦ｉ≦ｎ）をＡのラベル列、Ｂの元の系列ＳＢ＝｛ｂ１，ｂ２，ｂ３，…，ｂｍ｝（ｂｉ∈Ｂ，１≦ｉ≦ｍ）をＢのラベル列とする。
【０００５】
ラベル列ＳＡとラベル列ＳＢのマッチング結果をｗとする。ｗは、整数［１，ｎ］を整数［１，ｍ］に写す写像であり、ラベル列ＳＡのｉ番目のラベルａｉと、ラベル列ＳＢのｗ（ｉ）番目のラベルｂｗ（ｉ）が対応付いていることを意味するものとする。ｗには、一般には何らかの制約が課せられる。例えば、ラベルの並び順を逆転させないという制約（ｉ＜ｊならばｗ（ｉ）≦ｗ（ｊ）や、ｗの値があまり急に変化しないという傾斜制限（ｗ（ｉ＋１）≦ｗ（ｉ）＋α、αは定数）を課す場合がある。
【０００６】
ラベルａとラベルｂを対応付ける場合のコストをｃ（ａ，ｂ）とする。コストｃ（ａ，ｂ）は、ａとｂの関数であり、ａとｂが似ているほど小さい値をとり、完全に一致する場合に最小値０をとるものとする。
【０００７】
ラベル列ＳＡとラベル列ＳＢのマッチング結果ｗのコストＣを、以下の数式１で
【０００８】
【数１】
2005165538.tif 000003
と定義する。最小のコストＣを与えるｗを、ラベル列ＳＡとラベル列ＳＢの最適マッチング結果ｗ０と定義する。Ｃ（ｗ）は、マッチング結果をスカラー量に写す関数であり、コスト関数と呼ぶことにする。よって、２系列のマッチングを求める問題は、コスト関数の下での最小化問題に帰着する。
【０００９】
マッチングを求めるためには、一般最小化アルゴリズムを使用することができる。例えば、全探索や、焼きなまし法を用いることができる（例えば、非特許文献３参照）。特に、並び順の逆転がない場合には、高速な動的計画法（ダイナミックプログラミング、ＤＰ）によるＤＰマッチングと呼ばれる方法がよく利用されている。
【００１０】
これらの最小化アルゴリズムは、所与のコスト関数の下で最善の解を求めるものである。
【００１１】
なお、最小化問題は、コスト最小化問題、エネルギー最小化問題、最適化問題などとも呼ばれる。また、符合を反転させればコストを最大化する問題となるので、最小化問題と最大化問題は本質的に同じ問題である。
【００１２】
ここで、本明細書中で用いるいくつかの用語について定義しておく。
【００１３】
『対応が「正しい」または、「誤り」である』とは、人間がその対応を吟味し判定した結果を指すものとする。コスト最小化法により計算されたマッチング結果は、コストを最小化するという意味において常に正しいといえるが、マッチング結果を利用する人間は、別の独自の基準によって正誤を判定するので、必ずしもその結果を受け入れられるものではない。また、音声信号とテキストを対応付ける場合には、音声認識の結果に誤りが混入しているような場合もあり、そのような場合には、コストを最小化するようなマッチングであっても誤りを含むと考えられ、その正誤はコストを評価することでは判定し得ず、人間の判定によらざるを得ないであろう。
【００１４】
コストの最小化法などの機械的な手順でマッチングを行うことを『自動マッチング』と呼ぶこととする。自動機械で実行可能であるという意味の含みをもっているが、必ずしも機械で実行させなければならないという意味ではない。
【非特許文献１】平成１２年度視聴覚障害者向け放送ソフト制作技術研究開発プロジェクト最終報告書，通信・放送機構
【非特許文献２】谷村正剛、中川裕志、“ドラマのビデオ音声トラックとシナリオのセリフの時刻同期法”、情報処理学会第１１８回  知能と複雑系研究会研究報告、ＳＩＧ−ＩＣＳ，  ｎｏ．１８８−４，ｐｐ．２５−３１
【非特許文献３】Richard O. Duda, Peter E. Hart and David G. Stork,  尾上守夫監訳、パターン識別、新技術コミュニケーションズ
【発明の開示】
【発明が解決しようとする課題】
【００１５】
しかしながら、前述したコスト関数の最小化問題としてマッチングを求める方法で、異なるメディア系列のマッチングを求めようとしてもうまくいかない。
【００１６】
台本の文字列と発話音声の音声認識結果の系列を対応付けることを例に考える。このような場合には、必ずしも原稿通りに発話がなされるとは限らない。また、番組制作の過程で、台本と異なるセリフが挿入されたり、削除されたり、セリフの順序が入れ替わる場合がある。また、現在の技術水準では、音声認識の誤りを無くすることは難しく、現実的には、音声認識結果は誤りを含むことを前提とする必要がある。従って、台本の文字列と、音声認識結果は、そもそも一致するとは限らない。
【００１７】
そのような場合でも、コスト関数を最小化するという意味で最善のマッチング結果が得られるのであるが、それが利用者にとって受容できるものであるとは限らない。利用者の望むマッチング結果の基準が一定であり、定式化できるものであれば、それらをコスト関数に反映させることによって、マッチング結果を利用者の望むマッチング結果に近づけることが可能であろう。しかしながら、利用者の希望を定式化することが困難な場合がある。また、利用者の希望がマッチングを実施する度に異なり、その都度定式化を行う作業が発生することを許容できない場合がある。従って、現実的には、利用者が各々望むようにマッチングの結果を修正する工程が必要となる。マッチングの修正工程では、利用者は番組と台本を見比べ、マッチング結果の正誤を判断しながらマッチング結果を修正することになる。
【００１８】
また、大局的に修正しなければならない場合があり、このことがさらに問題を生む。例えば、利用者が望むマッチング結果とラベル１つ分ずれているような場合を想定すると、ずれている全てのラベルについて修正を施さなければならず、手数が大きくなってしまう。
【００１９】
また、修正すべきラベルがどこにいくつ存在するのかは、目視して確認しないとわからないのであるから、マッチング結果の修正作業を単純に行おうとすれば、マッチングの結果を最初から最後まで目視し、全ての対応について正誤を判定し、間違っている対応の全てについて正しい対応先へ対応させるという手順となろう。
【００２０】
一方、自動マッチングを用いず、最初から人手でマッチングを行おうとすれば、ラベル列ＳＡとラベル列ＳＢを最初から最後まで目視し、全ての対応について正しい対応先へ対応させるという手順となろう。
【００２１】
それでは、自動マッチングを実行した後にその誤りを修正する作業に要する時間Ｔ１と、自動マッチングを用いず手作業でマッチングを行う作業に要する時間Ｔ２にはどの程度の違いがあるであろうか。Ｔ１を定式化すると数式２のようになる。
【００２２】
Ｔ１＝ｔａｕｔｏ＋Ｎｔｃｈｅｃｋ＋ｎｍｉｓｓｔｂｉｎｄ        ・・・数式２
ここで、ｔａｕｔｏは、自動マッチングに要する時間、Ｎは対応の数、ｔｃｈｅｃｋは、対応１個について正誤を判定するのに要する時間、ｎｍｉｓｓは、誤った対応の数、ｔｂｉｎｄは、対応１個について正しい対応先を探し対応付けるのに要する時間とする。後者の時間Ｔ２を定式化すると、数式３のようになる。
【００２３】
Ｔ２＝Ｎｔｃｈｅｃｋ＋Ｎｔｂｉｎｄ
Ｔ１とＴ２の違いを大雑把に見積もる。ｔａｕｔｏは機械で実行できるので非常に小さいとみなし０で近似する。また、目視で正誤を確認する作業も、正しい対応先へ対応付ける作業に比べると簡単で時間もかからないであろうから、ｔｃｈｅｃｋ＜＜ｔｂｉｎｄとみなして、ｔｃｈｅｃｋを０で近似する。すると、両者の比Ｔ１／Ｔ２は高々ｎｍｉｓｓ／Ｎの程度となる。ここで、前述したように、対応の誤りの数は少なくても修正すべき手数は多くなってしまう場合があることを考慮すると、自動マッチングを使って単純な手順で手作業で修正する場合の手作業の負荷と、全て手作業でマッチングを行う場合の手作業の負荷の差は、前者が非常に小さいとはいえない。同時に、手作業でマッチングの結果を修正する方法で、短時間で済む方法、あるいは、手数の少ない方法があれば、なお有効であると考えられる。
【００２４】
以上の議論から理解されるように、自動マッチングという機械で高速に実行できる方法を利用したとしても、マッチングの誤りの混入を避けられないのならば、結局はその速度的利点を充分享受することはできなくなってしまうという問題がある。
【００２５】
本発明は、上記の点に鑑みなされたもので、マッチングの修正作業において、作業に要する手数を削減するためのラベルの系列マッチングの誤り修正方法及び装置及びプログラム及びラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００２６】
図１は、本発明の原理を説明するための図である。
【００２７】
本発明は、入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するラベルの系列のマッチング誤り修正方法において、
マッチング処理手段が、２つのラベル列のマッチングを行い、コスト最小化法により、マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納するマッチング処理過程(ステップ１)と、
修正候補選択手段が、ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によってラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択過程(ステップ２)と、
候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力することにより操作者に提示し、該操作者から対応の正誤を取得し(ステップ３)、コスト付与手段が、該ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与過程(ステップ４)と、
コスト付与過程で変更されたコストを加味して、再度マッチング処理過程(ステップ１)以降の処理を繰り返す(ステップ５)繰り返し過程からなる。
【００２８】
また、上記のコスト付与過程において、
操作者がラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
コスト付与手段が、ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、ラベルａｉとラベルｂｊの対応に低いコストを与える。
【００２９】
図２は、本発明の原理構成図である。
【００３０】
本発明は、入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するラベルの系列のマッチング誤り修正装置であって、
２つのラベル列のマッチングを行い、コスト最小化法により、マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納するマッチング処理手段１１１と、
ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によってラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択手段１１２と、
候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力することにより操作者に提示し、該操作者から対応の正誤を取得するインタフェース手段１１３と、
ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与手段１１５と、
コスト付与手段で変更されたコストを加味して、再度マッチング処理手段１１１、修正候補選択手段１１２、インタフェース手段１１３、及びコスト付与手段１１５を、繰り返す繰り返し手段１１７と、を有する。
【００３１】
また、上記のコスト付与手段１１５は、
操作者がラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、ラベルａｉとラベルｂｊの対応に低いコストを与える手段を含む。
【００３２】
本発明は、入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するコンピュータに実行させるラベルの系列のマッチング誤り修正プログラムであって、
２つのラベル列のマッチングを行い、コスト最小化法により、マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納させるマッチング処理ステップと、
ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によってラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択ステップと、
候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力させることにより操作者に提示させ、該操作者から対応の正誤を取得させるインタフェースステップと、
ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与ステップと、
コスト付与ステップで変更されたコストを加味して、再度マッチング処理ステップ、修正候補選択ステップ、インタフェースステップ、及びコスト付与ステップを、繰り返えさせる繰り返し制御ステップと、をコンピュータに実行させる。
【００３３】
また、上記のコスト付与ステップは、
操作者がラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、ラベルａｉとラベルｂｊの対応に低いコストを与えるステップをコンピュータに実行させる。
【００３４】
本発明は、入力された２つのラベル列ＳＡ＝{ａ１，ａ２，ａ３，…，ａｎ}，ＳＢ＝{ｂ１，ｂ２，ｂ３，…，ｂｍ}のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を修正するコンピュータに実行させるラベルの系列のマッチング誤り修正プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、
ラベル列のマッチングを行い、コスト最小化法により、マッチング結果ｗと最小コストＣを求め、一時的に記憶手段に格納させるマッチング処理ステップと、
ｉ∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に不利なコストを与えたとして仮定して、コスト最小化法によってラベル列ＳＡ，ＳＢのマッチング結果ｗｉと最小コストＣｉを求めた場合に、該最小コストＣｉが小さく、かつ、マッチング結果の距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは、複数の候補ｉを選択する修正候補選択ステップと、
候補ｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を表示手段に出力させることにより操作者に提示させ、該操作者から対応の正誤を取得させるインタフェースステップと、
ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、該ラベルａｉとｂｗ（ｉ）の対応に不利なコスト与え、該コストを記憶手段に格納するコスト付与ステップと、
コスト付与ステップで変更されたコストを加味して、再度マッチング処理ステップ、修正候補選択ステップ、インタフェースステップ、及びコスト付与ステップを、繰り返えさせる繰り返し制御ステップと、をコンピュータに実行させるプログラムを格納する。
【００３５】
また、上記のコスト付与ステップは、
操作者がラベルａｉとｂｗ（ｉ）の対応を判定した際に、対応が誤っている場合に、該ラベルａｉの正しい対応先としてラベルｂｊが選択された場合には、
ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、ラベルａｉとラベルｂｊの対応に低いコストを与えるステップをコンピュータに実行させる。
【発明の効果】
【００３６】
本発明によれば、マッチング結果に誤りが存在する場合に、修正の影響の大きい順に誤りを修正することができるので、誤りを総当りで修正しなくとも、誤りの無いマッチングもしくは、誤りの少ないマッチング結果が少ない手数で得ることができる。
【発明を実施するための最良の形態】
【００３７】
以下、図面と共に本発明の実施の形態を説明する。
【００３８】
本発明は、マッチング結果の誤りを修正する際に、全ての誤りを総当りで修正するのではなく、修正の影響の大きい順に誤りを修正することによって、誤りのない状態へ速く到達させようという着想によってなされたものである。
【００３９】
図３は、本発明の一実施の形態における動作の概要を示すフローチャートである。
【００４０】
まず、自動マッチングを行い、一時的に記憶手段に格納しておく（ステップ１０１）。
【００４１】
次に、自動マッチングの結果を解析し、修正を施すことにより、自動マッチングの結果が大きく変化し、なおかつ、マッチングのコストが大きく下がるような対応を探索する（ステップ１０２）。
【００４２】
上記の探索された対応を、人が目視により正誤を判定し（ステップ１０３）、誤っていたならば、正しい対応先を探し、正しい対応に高い一致度（すなわち、低コスト）を付与する。または、誤っている対応に、高いコスト（すなわち、低い一致度）を付与する（ステップ１０４）。
【００４３】
誤りがなくなったと判断されるまで、あるいは、誤りが減り、許容できるほど正解に近付いたと判断されるまで繰り返す（ステップ１０５）。
【００４４】
この手順によれば、修正すべき誤りがどこにあるか、目視により探さなくてもよいため、人の作業の負荷が軽減される。また、影響度の大きい誤りを修正してマッチングをやり直すため、波及効果で他の誤りよりも正しくなり、修正の手順の回数が減少し、人の作業の負荷が軽減されると期待される。
【００４５】
また、誤りが減少し、利用者が許容できる範囲内に達したと判断したならば正解にいたらなくとも途中で修正を止めてよい。
【００４６】
上記のステップ１０４において、マッチングの変化の大小を評価するには、マッチング結果ｗ１、ｗ２間の距離ｄ（ｗ１，ｗ２）を例えば、数式４のように定義し、ｄの大小で評価することができる。δｉｊはクロネッカーのδであり、ｉ＝ｊのとき１、それ以外のとき０をとる。
【００４７】
【数２】
2005165538.tif 000004
本明細書に記載する方法では、２つのラベル列ＳＡ＝｛ａ１，ａ２，ａ３，…，ａｎ｝、ＳＢ＝｛ｂ１，ｂ２，ｂ３，…，ｂｍ｝のマッチング結果ｗ：［１，…，ｎ］→［１，…，ｍ］を求める方法であって、
（１）コスト最小化法によりマッチング結果ｗと最小コストＣを求め、
（２）１∈［１，…，ｎ］について、ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えたと仮定してコスト最小化法によって、ラベル列ＳＡ，ＳＢのｗｉと最小コストＣｉを求めた場合に、Ｃｉが小さく、かつ、マッチング結果距離ｄ（ｗ，ｗｉ）が大きくなるような１個もしくは複数のｉを選び、
（３）上記の選んだｉについて、ラベルａｉとｂｗ（ｉ）の対応の正誤を目視により判定し、
（４）上記ラベルａｉとｂｗ（ｉ）の対応が誤りの場合には、ラベルａｉとｂｗ（ｉ）の対応に高いコストを与え、
（５）（４）で変更されたコストを加味して再度コスト最小化法によりマッチング結果ｗと最小コストＣを求め、上記（２）から（５）の手順を繰り返すマッチング方法について説明する。
【００４８】
また、本発明では、上記のマッチング方法において、ステップ１０３において、ラベルａｉとｂｗ（ｉ）の対応の制御を判定すると共に、対応が誤っている場合には、ａｉの正しい対応先ｂｊを選び、ステップ１０４において、ラベルａｉとｂｗ（ｉ）の対応に高いコストを与えると共に、ラベルａｉとｂｊの対応に低いコストを与えるマッチング方法について説明する。
【００４９】
以下では、映像番組の発話区間と、台本のセリフを対応付けるという状況を例にとり説明する。
【００５０】
図４は、本発明の一実施の形態におけるシステム構成を示す。
【００５１】
同図に示すシステムは、情報処理装置１０１、表示装置１０２、入力装置１０３から構成されている。
【００５２】
操作者は、システムと対話しながらマッチング結果の修正を行う。対話のインタフェースとして、操作者へ情報を提示するために表示装置１０２が用いられ、操作者の操作を入力するために入力装置１０３が用いられる。
【００５３】
図５は、本発明の一実施の形態における表示処理装置に表示される画面の例を示す。同図に示す画面は、いわゆるグラフィカルユーザインタフェースとなっており、仮想的にボタン等が配置されている。
【００５４】
図５の領域２０１は、画面の表示領域を表している。領域２０２は、番組の発話区間を表示する領域である。発話区間２０６〜２０９は、各々が一つの発話区間を表しており、発話がなされている間の番組の映像の代表画像を表示している。代表画像は、例えば、発話開始時間の映像を静止画として抽出して作成する。本実施の形態では、発話区間を代表画像にて表すよう記述しているが、発話区間を表す方法はこれに限らず、他の方法でもよい。例えば、発話区間の開始時刻と終了時刻を表示してもよい。発話区間２０６〜２０９はボタンになっており、これを操作することにより、当該発話区間の映像（音声も含む）が再生されるものとする。スクロールバー２０３は、番組の中で所望の発話区間を表示させるためのものである。領域２０４は、台本のセリフを表示する領域である。
【００５５】
セリフ２１０〜２１５は、各々が一区切りのセリフを表しており、セリフの文が表示されている。スクロールバー２０５は、番組の中で所望のセリフを表示するためのものである。矢印２１６は、発話区間とセリフの対応関係を表している。例えば、発話区間２０６とセリフ２１０が矢印で結ばれていると、発話区間２０６とセリフ２１０が対応していることを表している。領域２１７は、システムが操作者へ提示するメッセージを出力する領域である。ボタン２１８及び２１９は、システムが操作者にある対応の正誤を問い合わせたときに、操作者がシステムへ応答するためのものである。ボタン２１８は対応が正しいと答えるためのもので、ボタン２１９は対応が誤っていると答えるためのものである。ボタン２２０は、マッチング結果の修正の処理を終了するためのボタンである。
【００５６】
マッチングの例の説明の前に、入力データの準備について説明する。
【００５７】
図６は、本発明の一実施の形態における番組と台本の対応付けの作業の全体の流れを表した図である。
【００５８】
同図において、映像ファイル３０１は、対応付けたい番組をディジタル化し、ＭＰＥＧ形式などに変換したファイルである。台本３０３は、対応付けたい台本をディジタル化し、テキストファイルとしたものである。発話区間抽出処理３０６は、映像ファイル３０１を入力とし、発話区間を抽出し、発話区間の列３０２を出力する。ラベルａｉ（１≦ｉ≦ｎ）は、ｉ番目の発話区間を表すラベルとする。ｎは番組中に抽出された発話区間の総数である。発話区間を抽出する方法、例えば、「南憲一、阿久津明人、浜田洋、外村佳伸“音情報を用いた映像インデクシングとその応用”信学論Ｄ−ＩＩ，ｖｏｌ．Ｊ８１−Ｄ−ＩＩ，ｎｏ．３，ｐｐ．５２９−５３７，１９９８」に示す方法を利用することができる。セリフ抽出処理３０７は、台本３０３を入力とし、セリフの列３０４を出力する。セリフとは、つまり、台本上に表された１発話区間ということであるが、例えば、発話文を表すカギ括弧（「」）で囲まれた１発話と解釈する。セリフの区切り方は、これによらず、他の基準によって区切ってもよい。ラベルｂｉ（１≦ｉ≦ｍ）は、ｉ番目のセリフを表すラベルとする。ｍは台本中のセリフの総数である。マッチング処理３１０は、映像ファイル３０１と、音声区間列３０２と、セリフ列３０４とを入力とし、操作者と対話をしつつ、発話区間列３０２とセリフ列３０４のマッチング結果３０５を求め、出力する。マッチング結果を記号ｗで表す。マッチングを行うのに必須なのは発話区間列３０２とセリフ列３０４だけであるが、操作者が対応の正誤を判定する際、映像を参照できると都合がよいため、映像ファイル３０１も入力するように構成している。
【００５９】
マッチングの実施に先立ち、コストの評価方法と、自動マッチングの方法を定めておく必要がある。
【００６０】
ラベルとラベルのコストｃ（ａｉ，ｂｊ）の構成方法は種々のものが可能であるが、例えば、次のように構成する。発話区間ａｉの発話の継続時間をｔｉ、セリフｂｊのモーラ数をｒｊとする。文献「谷村正剛、中川裕志、“ドラマのビデオ音声トラックとシナリオのセリフの時刻同期法”、情報処理学会第118回知能と複雑系研究会研究報告、SIG-ICS，no．188-4，pp．25-31」によれば、発話区間の継続時間はセリフのモーラ数に近似的に比例することが知られている。比例定数（「継続時間」／「モーラ数」）をαとする。そして、数式５のようにラベル間のコストを定義する。
【００６１】
【数３】
2005165538.tif 000005
ラベル間のコストの定義は、この方法に限らず、例えば、音声認識技術を利用して発話の音声信号とセリフとの類似度を用いてもよいし他の方法を用いてもよい。
【００６２】
本発明は、コストの値を動的に変更させるという特徴を有するので、コスト関数は修正可能である必要がある。これを実現するために、ヒントリストを用いる。ヒントリストは、組（発話区間インデックス、セリフインデックス、コスト）の組のリストである。最初は、ヒントリストは空であるとする。ラベルａｉとｂｊのコストを評価するとき、ヒントリストを探索し、もし、ヒントリスト内に、発話区間インデックスがｉであり、セリフインデックスがｊであるような組が存在したら、この組のコストの値をａｉとｂｊのコストとする。もし、ヒントリスト内に存在しない場合は、数式５によってコストを算出する。このようなコスト値を上書きできるようにしたコスト関数を、
【００６３】
【数４】
2005165538.tif 000006
と表す。
【００６４】
自動マッチングの方法は、一般の非線形最小化問題の解法を用いる。例えば、焼きなまし法（アニーリング法）を用いることができる（文献：Richard O. Duda, Peter E. Hart and David G. Stock,  尾上守夫監訳、パターン識別、新技術コミュニケーションズ）。
【００６５】
次に、本発明のラベルの系列マッチング結果の誤り修正方法の説明を行う前に、図4における情報処理装置１０１の詳細構成について説明する。
【００６６】
図７は、本発明の一実施の形態におけるマッチング誤り修正装置の構成を示す。
【００６７】
同図に示す装置は、図４に示す情報処理装置１０１に対応する。
【００６８】
同図に示す装置１０１は、マッチング処理部１１１、修正候補選択部１１２、インタフェース部１１３、入力判定部１１４、コスト付与部１１５、ヒントリスト１１６、及び終了判定部１１７から構成される。
【００６９】
マッチング処理部１１１は、図６におけるマッチング処理３０８を行い、マッチング結果をメモリ等の記憶手段に格納する。
【００７０】
修正候補選択部１１２は、操作者に提示するための修正候補を選択する。修正候補とは、修正を行うことでマッチングの結果がより大きく変化し、かつ、マッチングのコストがより小さくなると期待される対応の候補である。
【００７１】
インタフェース部１１３は、表示装置１０２及び入力装置１０３との情報のやり取りを行う。
【００７２】
入力判定部１１４は、操作者からどのボタンが押下されたか等を判定する。
【００７３】
コスト付与部１１５は、入力判定部１１４において、操作者からの判断（対応が誤り、対応が正しい）に基づいて、コスト関数にコストを付与する。
【００７４】
ヒントリスト１１６は、メモリ等の記憶手段であり、発話区間、インデックス、セリフインデックス、コストの組からなるリストである。
【００７５】
終了判定部１１７は、全ての修正候補に対する処理が終了したか否か、または、操作者が終了ボタンを押下したかを判定する。
【００７６】
図８は、本発明の一実施の形態におけるマッチング誤り修正処理のフローチャートである。
【００７７】
ステップ４０１）  まず、マッチング処理部１１１における自動マッチングにより、発話区間とセリフのマッチング結果ｗを求める。ｉ番目の発話区間とｊ番目のセリフの対応のコストを
【００７８】
【数５】
2005165538.tif 000007
とし、マッチングのコストＣを最小化するようなマッチング結果ｗを求め、このときの最小コストをＣｍｉｎとする。最小化には焼きなまし法などを用いることができる。
【００７９】
【数６】
2005165538.tif 000008
そして、得られたマッチング結果の状態をインタフェース部１１３を介して表示装置１０２に表示する。表示の方法は、領域２０２中に、発話区間ごとに代表画像を表示し、領域２０４の中にセリフ毎にセリフの文面を表示する。対応している発話区間ａｉとセリフｂｗ（ｉ）の間には、領域２１６に矢印を表示する。なお、発話区間ａｉとセリフｂｗ（ｉ）が領域２０２、２０４内にない時は、矢印を表示せずともよい。代表画像は、映像ファイル３０１から、発話区間ａｉの発話開始時刻の画像を静止画として抽出し、これを代表画像とする。
【００８０】
ステップ４０２）  修正候補選択部１１２において、Ｐ個の修正候補の対応を選択する。修正の候補となる対応は、その対応を修正することにより、マッチングの結果がより大きく変化し、なおかつ、マッチングのコストがより小さくなると期待される対応である。その選択の方法の詳細は後述する。
【００８１】
当該処理の結果、Ｐ個の発話区間のインデックス値が配列ＸのＸ［１］〜Ｘ［Ｐ］に格納されるものとする。Ｐは定数である必要はなく、当該処理を実行する都度に異なる値でもよい。また、Ｐは１でもよい。
【００８２】
ステップ４０３）  変数ｐに１を代入する。
【００８３】
ステップ４０４）  ｐ番目の発話区間の修正候補のインデックスＸ［ｐ］を、変数ｉに代入する。
【００８４】
ステップ４０５）  発話区間ａｉとセリフｂｗ（ｉ）を結ぶ矢印を表示装置１０２に強調表示する。強調表示の方法は、色を変えてもよいし、点滅させてもよいし、他の方法でもよい。発話区間ａｉとセリフｂｗ（ｉ）が領域２０２、２０４内にないときは、スクロールさせ、ともに表示されるような状態にする。しかる後、メッセージ出力領域２１７に、対応の正誤の入力要求を表示する。入力要求の表示は、例えば、「この対応は正しいですか？」と表示する。
【００８５】
ステップ４０６）  情報処理装置１０１は、画面上のボタンのいずれかが押されるまで待機する。
【００８６】
情報処理装置１０１が待機している間、操作者はステップ４０５での入力要求に促され、強調表示されている矢印の指している発話区間ａｉとセリフｂｗ（ｉ）を吟味する。必要であれば、代表表示画像を押下し、当該発話区間の映像（音声も含む）を再生し、発話内容を聴き取り、セリフｂｗ（ｉ）との同一性を判定する。必要であればスクロールバー２０３，２０５を操作して、当該発話区間の前後や、当該セリフの前後を確認してもよい。操作者がこの対応が正しいと判定した場合には、「正」ボタン２１８を押下し、誤りと判定した場合には「誤」ボタン２１９を押下する。「全体を確認」ボタン２２０を押下するケースについては後述する。
【００８７】
操作者がいずれかのボタンを押下すると、処理はステップ４０７へ移行する。
【００８８】
ステップ４０７）  入力判定部１１４は、押下されたボタンが「正」ボタン２１８であるか判定し、そうであれば、ステップ４１１に移行し、そうでなければステップ４０８へ移行する。
【００８９】
ステップ４０８）  押下されたボタンが「誤」ボタン２１９であるか判定し、そうであれば、ステップ４１２に移行する。そうでなければステップ４０９に移行する。
【００９０】
ステップ４０９）  押下されたボタンが「終了」ボタン２２０であるか判定し、そうであれば、ステップ４１０へ移行し、そうでなければステップ４０６に戻り、また別のボタンが押下されるまで待機する。
【００９１】
ステップ４１０）  現状のマッチング結果ｗを出力し、処理を終了する。
【００９２】
ステップ４１１）  当該ステップに処理が移行した場合は、発話区間ａｉとセリフｂｗ（ｉ）の対応が正しいと操作者が判定したのであるから、コスト付与部１１５は、
【００９３】
【数７】
2005165538.tif 000009
に有利なコストを付与する。そのために、ヒントリスト１１６に、組（ｉ，ｗ（ｉ），ε）を挿入する。εは、定数であり、小さな数である。例えば、ε＝０とする。その後、ステップ４１７に移行する。
ステップ４１２）  当該ステップに処理が移行した場合は、発話区間ａｉとセリフｂｗ（ｉ）の対応が誤りと操作者が判定したのであるから、
【００９４】
【数８】
2005165538.tif 000010
に不利なコストを付与する。そのため、ヒントリスト１１６に、組（ｉ，ｗ（ｉ），Ω）を挿入する。Ωは、定数であり、充分大きな数である。例えば、その後、ステップ４１３に以降する。
【００９５】
ステップ４１３）  コスト付与部１１５において、発話区間ａｉに対応する正しいセリフはどれか、操作者に選択を促すよう選択を要求する。例えば、メッセージ出力領域２１７に、「この発話区間に対応する正しいセリフを選択して下さい」と表示する。
【００９６】
ステップ４１４）  情報処理装置１０１は、セリフの一つが選択されるまで待機する。
【００９７】
当該ステップにおいて待機している間、操作者は、ステップ４１３での入力要求に促され、強調表示されている矢印の指している発話区間ａｉと、セリフの系列とを吟味する。必要であれば、代表画像を押下し、当該発話区間の映像(音声も含む)を再生し、発話内容を聴き取る。スクロールバー２０５を操作して、対応するセリフを探し、選択する。選択の操作は、例えば、表示領域２０４の対応するセリフの部分を押下することでなされるものとする。
【００９８】
操作者がいずれかのセリフを押下すると、処理は、ステップ４１５へ移行する。
【００９９】
ステップ４１５）  コスト付与部１１５は、セリフのインデックスｊを求める。操作者が選択したセリフをｂｊと表すことにする。
【０１００】
ステップ４１６）  発話区間ａｉとセリフｂｊの対応が正しいと操作者が判定したのであるから、コスト付与部１１５は、
【０１０１】
【数９】
2005165538.tif 000011
に有利なコストを付与する。そのために、ヒントリスト１１６に、組(ｉ，ｊ，ε)を挿入する。その後、ステップ４１７へ移行する。
【０１０２】
ステップ４１７）  変数ｐに値ｐ+１を代入する。
【０１０３】
ステップ４１８）  ｐとＰを比較し、ｐ≦Ｐであれば、修正候補をまだ尽くしていないので、ステップ４０４へ以降する。そうでなければ、修正候補を尽くしたので、ステップ４１９に移行する。
【０１０４】
ステップ４１９）  再度マッチング処理部１１１において、自動マッチングを実行する。コスト関数は、前回と同じく数式６を用いるが、ヒントリスト１１６の内容が前回と異なっているため、前回のマッチングとは異なるマッチング結果ｗが得られる。その後ステップ４０２へ戻り、再度修正候補を選択する。
【０１０５】
次に、上記のステップ４０２の処理の詳細について説明する。
【０１０６】
図９は、本発明の一実施の形態における修正候補選択処理のフローチャートである。
【０１０７】
ステップ５０１）  リストＬを空にする。
【０１０８】
ステップ５０２）  変数ｊに1を代入する。
【０１０９】
ステップ５０３）  ヒントリスト１１６に、発話区間インデックスがｊであるような組が存在するか検査する。もし存在しているならば、発話区間ｊは、既に操作者が何らかの正誤を判定したことを意味しているので、修正候補に入れる必要はないから、以下の処理をスキップし、ステップ５０９へ移行する。存在していなければステップ５０４に移行する。
【０１１０】
ステップ５０４）  ヒントリスト１１６に組（ｊ，ｗ（ｉ），Ω）を挿入する。このようにして、発話区間ｊとセリフｗ（ｊ）の対応が誤りと見做される状況を模擬的に設定する。
【０１１１】
ステップ５０５）  マッチング処理部１１１において、自動マッチングを実行する。自動マッチングの方法は、ステップ４０１及びステップ４１９と同様である。但し、マッチング結果をｗｊ、最小コストをＣｊとする。
【０１１２】
ステップ５０６）  修正候補適合度Ｈｊを求める。Ｈｊは、発話区間ｊが修正候補として適しているかを評価するための量である。本実施の形態では、
Ｈｊ＝Ｃｊ−ｋｄ（ｗ，ｗｊ）
により評価する。ここで、ｋは予め定めた定数とする。マッチングのコストが小さいほどＨｊの値も小さくなり、マッチング結果ｗとｗｊとの距離が大きくなるほどＨｊの値は小さくなる。なお、Ｈｊの評価方法はこれに限らず、他の方法を用いてもよい。
【０１１３】
ステップ５０７）  リストＬにペア(ｊ、Ｈｊ)を挿入する。
【０１１４】
ステップ５０８）  ヒントリスト１１６から組(ｊ，ｗ（ｊ），Ω)を削除し、元の状態に戻す。
【０１１５】
ステップ５０９）  変数ｊに値ｊ+１を代入する。
【０１１６】
ステップ５１０）  ｊと、発話区間の数ｎを比較すると、ｊ≦ｎであれば、ステップ５０３に戻り、そうでなければステップ５１１に移行する。
【０１１７】
ステップ５１１）  リストＬを、修正候補適合度Ｈｊの昇順でソートする。その結果、リストの先頭ほど、Ｈｊの値が小さいペアが配置される。
【０１１８】
ステップ５１２）  リストＬの先頭からＰ個のペアを取り出し、発話区間インデックスの値ｊを、配列Ｘに順に格納する。
【０１１９】
以上が、ステップ４０２の処理の詳細である。
【０１２０】
なお、上記の実施の形態では、全探索で修正候補を選び出すような形態を示したが、同等の結果を得られるならば、他の探索アルゴリズムを用いてもかまわない。
【０１２１】
本実施の形態では、ステップ４１１及びステップ４１６で、正しい対応に有利なコストを付与する例を示したが、代わりに、正しい対応以外の対応に不利なコストを付与するようにしてもよい。
【０１２２】
また、ステップ４１２で、特定のラベルの対応が誤りであることを反映させるために、当該ラベルの対応のコストを多角するような方法を示したが、その代わりに、当該ラベルが対応しないような制約条件を自動マッチングに盛り込むようにしてもよい。そのためには、Ωを無限大に設定するという方法や、両ラベル列を当該ラベルの前後に分け、ラベルより前のラベル列同士をマッチングし、ラベルより後のラベル列同士をマッチングし、その結果を結合するという方法などで行ってもよい。
【０１２３】
上記の図８のフローチャートは、請求項１(請求項３，５，７)及び請求項２(請求項４，６，８)を含めた動作となっているが、請求項１(請求項３，５，７)に関する処理のみを実行する場合には、ステップ４１３からステップ４１６を省略したものを実行する。
【０１２４】
上述したように、本発明の処理を用いることにより、マッチングに誤りが存在する場合に、修正の影響の大きい順に誤りを修正できるので、誤りを総当りで修正しなくとも、誤りの無いマッチング、もしくは、誤りの少ないマッチング結果が少ない手数で得ることができる。
【０１２５】
なお、上記の図８、図９に示す動作をプログラムとして構築し、情報処理装置１０１のようなコンピュータにインストールして実行する、または、ネットワークを介して流通させることも可能である。
【０１２６】
また、構築されたプログラムを、コンピュータに接続されるハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、コンピュータにインストールすることも可能である。
【０１２７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【産業上の利用可能性】
【０１２８】
本発明の処理が適用されるのは、発話区間とセリフのマッチングに限られるものではなく、文章の原稿と発生された音声信号のマッチングや、映像番組のショットと台本のカットとのマッチングなど、広範囲に適用可能なものである。
【図面の簡単な説明】
【０１２９】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における動作の概要を示すフローチャートである。
【図４】本発明の一実施の形態におけるシステム構成図である。
【図５】本発明の一実施の形態における表示処理装置に表示される画面の例である。
【図６】本発明の一実施の形態における番組と台本の対応付けの作業の全体の流れを示す図である。
【図７】本発明の一実施の形態におけるマッチング誤り修正装置の構成図である。
【図８】本発明の一実施の形態におけるマッチング誤り修正処理のフローチャートである。
【図９】本発明の一実施の形態における修正候補選択処理のフローチャートである。
【符号の説明】
【０１３０】
１０１  情報処理装置
１０２  表示装置
１０３  入力装置
１１１  マッチング処理手段、マッチング処理部
１１２  修正候補選択手段、修正候補選択部
１１３  インタフェース手段、インタフェース部
１１４  入力判定部
１１５  コスト付与手段、コスト付与部
１１７  繰り返し手段、終了判定部
２０１  表示領域
２０２  番組の発話区間を表示する領域
２０３  スクロールバー
２０４  台本のセリフを表示する領域
２０５  スクロールバー
２０６〜２０９  発話区間
２１０〜２１５  一区切りのセリフ
２１６  矢印（発話区間とセリフの対応関係）
２１７  システムが操作者へ提示するメッセージを出力する領域
２１８，２１９  操作者がシステムへ応答するためのボタン
２２０  マッチングの修正の処理を終了するためのボタン
３０１  映像ファイル
３０２  音声区間列
３０３  台本
３０４  セリフ列
３０５  マッチング
３０６  音声認識処理
３０７  セリフ抽出処理
３０８  マッチング処理
【図１】
2005165538.tif 000012
【図２】
2005165538.tif 000013
【図３】
2005165538.tif 000014
【図４】
2005165538.tif 000015
【図５】
2005165538.tif 000016
【図６】
2005165538.tif 000017
【図７】
2005165538.tif 000018
【図８】
2005165538.tif 000019
【図９】
2005165538.tif 000020