(57)【要約】      （修正有）【課題】確率論的クエリーを入力として用いて項目データベースを検索する方法を提供する。【解決手段】確率的入力クエリーに対して順位付けした結果セットを提示する。クエリー中のタームが認識され、各タームに確率が割り当てられる。この確率は、そのタームを正確に認識することに対する信頼性を表す。ターム及び割り当てられた確率を用いて確率論的クエリーに対応する項目についてデータベースを検索し、結果セットを生成する。この結果セットはその後、確率に応じてハイライティングされてユーザに提示される。【選択図】図１
2009245424.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと、
前記データベースを検索しながら、前記認識された確率論的クエリー中に不確実性を導入するステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項２】
前記不確実性を導入することは、マッチング関数を用いて前記認識された確率論的クエリー中の前記タームを変更する、請求項１に記載の方法。
【請求項３】
前記マッチング関数は、前記確率論的クエリーから選択されたタームを反復して削除し、各削除の後に、前記確率論的クエリーが空になるまで前記検索を繰り返す、請求項２に記載の方法。
【請求項４】
前記マッチング関数は、検索が行われている間にどのようにマッチングが行われるかの説明を生成する、請求項２に記載の方法。
【請求項５】
前記ハイライティングは前記説明に応じる、請求項４に記載の方法。
【請求項６】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと
を含み、前記階層グラフは、前記結果セットの親−子の関係をツリーとして表す、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項７】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと
を含み、前記階層グラフは、ハイライティングされた地理情報を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項８】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと、
前記検索の前に、エイリアシング関数を前記クエリーに適用するステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項９】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと
を含み、前記ハイライティングは、前記階層グラフに応じて引き継がれる、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１０】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと
を含み、前記結果セット中の選択される結果が隠される、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１１】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと
を含み、前記ハイライティングは、前記階層グラフをトラバースする、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１２】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと、
多数のマッチング結果を表示するステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１３】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと、
前記結果セットを表すヒストグラムを表示するステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１４】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと、
前記ハイライティングされた結果セットを階層グラフとして出力するステップと、
前記階層グラフの深度をスライダによって制御するステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１５】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
確率論的クエリーを取得するステップと、
前記確率論的クエリー中のタームを認識するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記認識された確率論的クエリー中に不確実性を導入しながら、前記ターム及び前記割り当てられた確率を用いて前記確率論的クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項１６】
前記不確実性を導入することは、マッチング関数を用いて前記認識された確率論的クエリー中の前記タームを変更する、請求項１５に記載の方法。
【請求項１７】
前記マッチング関数は、検索が行われている間にどのようにマッチングが行われるかの説明を生成する、請求項１５に記載の方法。
【請求項１８】
前記ハイライティングは前記説明に応じる、請求項１５に記載の方法。
【請求項１９】
コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法であって、
タームを含むクエリーを取得するステップと、
前記クエリーの前記ターム中に不確実性を導入するステップと、
各タームに確率を割り当てるステップであって、前記確率は前記タームを正確に認識することに対する信頼性を表す、ステップと、
前記ターム及び前記割り当てられた確率を用いて前記クエリーに対応する項目についてデータベースを検索することによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと
を含む、コンピュータにより実施される、確率論的クエリーに対して順位付けした結果セットをレンダリングする方法。
【請求項２０】
前記ハイライティングされた結果セットを階層グラフとして出力するステップをさらに含む、請求項１９に記載の方法。
【請求項２１】
前記階層グラフはツリーである、請求項２０に記載の方法。
【請求項２２】
コンピュータにより実施される、確率論的クエリーマッチング関数に対して順位付けした結果セットをレンダリングする方法であって、
タームを有するクエリーを取得するステップと、
確率論的クエリーマッチング関数を前記クエリーの前記タームによって初期化するステップと、
前記クエリーに対応する項目についてデータベースを検索するステップと、
各項目に前記確率論的クエリーマッチング関数を適用するステップと、
前記確率論的マッチング関数に応じて各項目に一致確率を割り当てることによって、結果セットを生成するステップと、
前記結果セット中の前記項目を前記確率に応じてハイライティングするステップと
を含む、コンピュータにより実施される、確率論的クエリーマッチング関数に対して順位付けした結果セットをレンダリングする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、データベースを検索して結果セットを提示することに関し、特に、不明確なクエリーすなわち確率論的クエリーを用いて検索して順位付けした結果セットを提示することに関する。
【背景技術】
【０００２】
作成され世界中に配信される検索可能なコンテンツの量は日々著しい速さで増加している。コンテンツは、ウェブページ、画像、ビデオ、音楽等の形態であり得る。コンテンツは、放送局、ケーブル配信事業者及び衛星配信事業者、無線プロバイダ、並びにインターネットを含むいくつかの供給源から容易に入手することができる。コンテンツの量が増加するに従い、所望のコンテンツを検索する問題も同様に増大する。
【０００３】
インターネット配信チャネルは、テレビシステム、デジタルビデオレコーダ（ＤＶＲ）、パーソナルコンピュータ（ＰＣ）、並びに携帯電話、ラップトップ及び個人情報端末（ＰＤＡ）等の携帯機器にコンテンツを直接ストリーミング又はダウンロードすることができる。ＰＣベースのブラウザは、キーボードを使用したテキスト入力によりコンテンツを検索するのに十分なインタフェースを提供する。しかし、英数字キーボードを備えていない機器を用いたコンテンツの検索には満足なソリューションがない。
【０００４】
例えば、テレビ及び他の再生機器とともに用いられる典型的なリモコンは、数字キーパッド、カーソル位置決めキー、及び制御対象のシステムの様々な動作モードを制御する他のキーのみを備える。ほとんどのリモコンには、ポインタ（マウスのような）機能も、英数字キーもない。オプションの選択はカーソル制御のメニューによってのみ行われ、テキスト入力は極めて難しく、不便で、時間がかかる。数週間先の番組が１００チャネル以上について電子番組表（ＥＰＧ）上で入手可能である場合、番組の検索は苛立たしいものとなる可能性がある。基本的に、典型的なリモコン装置はテキスト入力装置としては役に立たない。同じ問題が、ほとんどの小型のハンドヘルド式携帯機器について存在する。
【０００５】
１つのソリューションは、クエリーインタフェースに音声インタフェースを提供することである。或る１つのインタフェースは、音声を用いて、限定されたコマンドセットを指定する（A. Ibrahim、J. Lundberg及びJ. Johansson著「Speech Enhanced Remote Control for Media Terminal」（Proceedings of Eurospeech '01, Volume 4, pp. 2685-2688, 2001）、並びに、AgileTV社（米国カリフォルニア州メンロパーク所在）から入手可能なＰｒｏｍｐｔｕを参照）。Ｐｒｏｍｐｔｕリモコンは、トークボタン及びマイクを備える。このリモコンは、セットトップボックスとインタフェースして、所定の音声入力コマンドを用いてオンデマンドビデオコンテンツを走査し見つける。他のインタフェースはダイアログベースである（P. Johansson著「MADFILM -- A Multimodal Approach to Handle Search and Organization in a Movie Recommendation System」（Proceedings of the 1st Nordic Symposium on Multimodal Communication, pp. 53-65, September 25-26, 2003）、及びW. Wahlster著「SmartKom: Symmetric Multimodality in an Adaptive and Reusable Dialogue Shell」（Proceedings of the Human Computer Interaction Status Conference 2003, pp. 47-62, June 2003）を参照）。
【０００６】
１番目のタイプのインタフェースに伴う問題は、ユーザがまず、システムを操作するコマンドを学習しなければならず、誤り訂正が必要である場合があることである（Berglund他著「Error Resolution Strategies for Interactive Television Speech Interfaces」（Human-Computer Interaction, Interact 2003, pp. 105-112, 2003））。２番目のタイプのインタフェースは、設計及び開発のコスト及び複雑さを増大する。また、会話形式の音声インタフェースが、即座の応答をユーザにより求められる、リモコンを用いたテレビシステムとの対話に適しているかは定かでない。
【０００７】
別のインタフェースは、音声入力−リスト出力パラダイムを用いる（Divi他著「A Speech-In List-Out Approach to Spoken User Interfaces」（Human Language Technology Conference, May 2004））。このインタフェースは、Wolf他著「The MERL SpokenQuery Information Retrieval System: A System for Retrieving Pertinent Documents from a Spoken Query」（IEEE International Conference on Multimedia and Expo (ICME), Vol. 2, pp. 317-320, August 2002）、Wolf他著「SpokenQuery: An Alternate Approach to Choosing Items with Speech」（International Conference on Speech and Language Processing (ICSLP), ICSLP 2004, October 2004）、及び米国特許第６，８７７，００１号「Retrieving Documents with Spoken Queries」（Wolf他、２００５年４月５日発行、参照により本明細書中に援用される）に記載されるＳｐｏｋｅｎＱｕｅｒｙ技術に基づく。
【０００８】
ＳｐｏｋｅｎＱｕｅｒｙ技術では、音声認識エンジンの出力はテキストクエリーの完全な指定としては用いられず、むしろ、データベースの項目と照合することができるトークンセットとして用いられる。概念上、このインタフェースはテキストクエリーインタフェースに類似している。しかし、１つの大きな違いとして、クエリー中の認識された単語が確率的不確実性を有する。すなわち、音声認識装置は完全ではなく、同じように聞こえるテキストの単語は、誤って認識される音声の単語であることが多い。認識装置はせいぜい、信頼性スコアを割り当てることしかできない。
【０００９】
多くの場合、ユーザは、要求した項目が特定のデータベースに存在しないのか、或いは、音声によるクエリーが誤って解釈されたのかを判断するという問題に直面する。
【００１０】
Ｇｏｏｇｌｅ（登録商標）、ＡｌｔａＶｉｓｔａ（登録商標）、及びＹａｈｏｏ（登録商標）等のほとんどのサーチエンジンは、極めて高度な技術を用いて、クエリーに応答して生成される結果セットを順位付けする。順位付けは、見つかった項目の関連度を考慮しようとする。関連性は、キーワードの出現頻度及び出現場所、その項目が他の同様の項目とどうリンクされているか、又は恐らくは、費やされている広告料金に基づくことができる。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、確率論的クエリーを入力として用いて項目データベースを検索する方法を提供する。
【課題を解決するための手段】
【００１２】
クエリーは、ターム、例えばユーザが発した音声の単語又は句の表現から成る。各タームには、そのタームがユーザの意図したものであったという確率が関連付けられる。これらのタームと、そのタームがユーザの意図したものと一致したという関連する確率とを用いてデータベースを検索し、項目の順位付けした結果セットを生成する。各項目には、それが含まれることを正当化するために用いられたターム及びその項目の順位を含む記述が、その項目がユーザの意図したものであったという確率とともに関連付けられる。
【００１３】
記述は、注釈付きのターム及びハイライティングを用いて、順位付けした結果セットとしてユーザに提示される。結果セットのハイライティングは、関連する確率に従う。ハイライティングは、項目が提示される順位付け、並びに記述の視覚的外観、例えば、文字及び単語のサイズ、色、強調、又はフォントを含むことができる。外観の効果は、空間的及び時間的なものとすることができる。例えば、単語を移動又は点滅させることができる。ハイライティングは音響により伝えることもできる。
【００１４】
ハイライティングは、従来技術のサーチエンジンのような検索の関連性スコアには基づかず、むしろ、何らかの認識エンジンによるクエリーの解釈の信頼性スコアに基づくことに留意すべきである。
【００１５】
ハイライティングは、クエリーがどのように解釈されてデータベースの検索中に適用されたかというフィードバックをユーザに提供する。データベースを検索する前に、認識されたクエリー中に不確実性を導入することもできることが留意されるべきである。
【００１６】
一実施の形態では、結果セットは階層グラフとして提示され、階層は結果セットの順位付けによって求められる。結果セットに対応するヒストグラムも提示することができる。ヒストグラム及び階層グラフは、「強度」スライダ（slider）によって閾値を定めることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態による、確率論的クエリーに応答して結果セットを提示する方法のフロー図である。
【図２】完全に拡張された階層グラフにおける「china（中国）」の検索の結果の概略図である。
【図３】階層グラフにおける伝播されるハイライトの概略図である。
【図４】隠れた結果又は折り畳まれた結果を有する階層グラフの概略図である。
【図５】完全に折り畳まれた階層グラフの概略図である。
【図６】不明確なクエリーの階層グラフの概略図である。
【図７】階層グラフのヒストグラム及び可視性閾値スライダの図である。
【図８】折り畳み可能な階層を有する地理マップの概略図である。
【図９】地理マップの結果セットの概略図である。
【発明を実施するための形態】
【００１８】
図１は、本発明の一実施の形態による、確率論的クエリーに応答して結果セットを提示する方法１００を示す。方法１００への入力１０１は確率論的クエリーである。
【００１９】
本明細書中で定義するように、確率論的クエリーは、クエリーの意味の解釈に伴う或る程度の不確実性を有する。通常の確率論的クエリーは音声によるクエリーである。確率論的クエリーの他の例として画像、又は音楽の「スニペット」がある。
【００２０】
クエリーの不確実性は、複数の原因の任意の組み合わせに起因するものである可能性がある。音声の場合、これらの原因として、不明瞭な発音、環境雑音、マイクの問題等がある。認識プロセスそのもの及び照合される音声モデルが不確実性を高める。様々な言語の方言の違いが、クエリーの意味に関する不確実性を高める。
【００２１】
画像の場合、サンプリングされた各画素の値に関する不確実性がある。照明及び影、並びに光学効果が画像を不鮮明にする可能性がある。画像中の物体は認識するのが困難な場合がある。画像認識装置は、ターム、例えば、形状、色、及びサイズ等の画像特徴を画像から抽出し、入力画像中に各タームが出現する確率を提供しようとする。しかし、完全な確実性が常に可能であるとは限らない。
【００２２】
本発明の目的は、検索エンジンによって生成される結果を、これらの不確実性、又は認識プロセスにおける信頼度を考慮する方法で提示することである。
【００２３】
クエリー１１１が例えばマイク又はカメラにより取得される（１１０）。クエリーは認識され（１２０）、可能なターム１２１のセットとして解釈される。確率１２２が各タームに割り当てられる。認識（１２０）は、自動音声認識装置、又は解釈を助けるデータベース１２５にアクセスすることができるコンピュータビジョン物体認識装置によって行うことができる。データベースはまた、検索（１３０）すべき項目を含んで、結果セット１３１を生成することができる。項目は、ウェブページ、画像、文書、音楽ファイル等であることができる。通常、結果セット中の項目には短い記述が関連付けられる。この短い記述は、結果セットを生成する際に「オンザフライ」で生成することができる。通常、短い記述のみが実際の項目そのものへのリンクとともに表示又は印刷され、ユーザはその後、１つの項目を選択してフル表示することができる。
【００２４】
したがって、データベース１２５の検索（１３０）は結果セット１３１を生成する。結果セットには、認識の確率１２２に、見つけたタームがともにデータベースにあったという確率を結合したものに基づくか、又はそれを含む確率１３２が関連付けられる。データベース結果は、順位付けを変える重みを含み得る。
【００２５】
結果セットは、確率１３２に応じてハイライティングを含むように変更される（１４０）。「ハイライティング」という用語は視覚効果及び音響効果を含むことができる。ハイライティングされた結果セット１４５は、後述のように外観スタイル１４１に従ってハイライティングされる。
【００２６】
通常、結果セットにおける項目の記述中の「ターム」は、確率論的クエリー中のタームに対応する。信頼性スコア又は確率の高いタームがハイライティングされる。これらのタームは、部分的な単語又は完全な単語、数字、文字、英数字、句、「サムネール」画像等であることができる。ハイライティングの外観１４１は、輝度、フォント、サイズ、色、点滅速度、太字、浮き彫り、影付き、「浮き出し」テキストのような３Ｄ効果、下線、歪み、コントラスト、フォーカス、かぶり、マーキング、丸囲み、枠囲み及び背景効果、アニメーション等を含むことができる。
【００２７】
ハイライティングの外観は、そのタームが項目中に出現したことを表すためのブーリアン、例えば太字フォント又は通常フォントとすることができる。ハイライティングは、順番、例えば、フォントサイズ、又は信頼性に関連する明度を示すことができる。外観は、複数の順序、例えば、信頼性に関連する明度及び検索中のタームの重み付けに関連するサイズ、並びにその他に関連する色を一度に示すことができる。
【００２８】
ハイライティングは音響信号を含むことができる。例えば、結果セットが電話通信により提示される場合、ハイライティングは、音量、音質、周波数、速度、音の効果、音の挿入、音のオーバーレイ、例えばベル音を考慮することができる。
【００２９】
画像のハイライティングは、歪み、色、輝度、オーバーレイ、アニメーション等を考慮することができる。ビデオも同様にハイライティングすることができる。
【００３０】
他の確率論的クエリーは手書き文字の形態とすることができることに留意すべきである。例えば、手書き文字認識では、入力は、それぞれに信頼性レベルを有する文字及びタームを形成する線の集合として特徴付けることができる。文字は、データベース中に見つかると予測される信頼性レベルを有する単語を形成する。データベース自体は、可能なトランスクリプトを定義する単語シーケンスを含む。手書き文字の結果として得られる可能なトランスクリプション中に、ハイライトを用いて、手書き文字のタームに一致した又はそれから導出されたデータベースエントリの場所を示すことができる。
【００３１】
階層結果セット
これまで、確率論的クエリーの結果セットのハイライティングを視覚的及び聴覚的に説明してきた。親出願では、出力は、最良の一致が最初にくる順位付けした結果セットである。親出願におけるハイライティングは、クエリーが正確に一致していることの信頼性スコアに基づく。
【００３２】
ここで、結果の提示を、マーク付けされたグラフとなるように拡張し、垂直位置及び水平位置は未定義であるか、又は親−子のような結果セットの異なる順序付けを表すように選択され、ハイライトは結果セットの提示に新しい順序を提供する。
【００３３】
本方法を、音声認識信頼性スコア、又は他の任意の不明確なクエリーの確率に適用することができる。
【００３４】
クエリー自体が完全に確定されている場合であっても、ユーザにとって有用であり得る近いか又は関連する一致を見つける方法として不確実性又は不明確性を導入することができる。１つの技法は、検索している（１３０）間にマッチング関数１１３を適用することによってこれを達成する。まず、マッチング関数は完全一致に関して検査する。その後、マッチング関数は部分的一致に関して検査する。続いて、関数は文字又はタームを確率論的クエリーから反復して削除し、さらなる一致に関して検査する。これは、クエリーが空になるまで繰り返される。
【００３５】
関数が進行すると、関数は、最初の一致を達成するために関数が行わなければならない変更の数、及び、或るスケール、たとえば英数字等を用いて見つけることができる変更のサイズに基づいて、一致確率順序をデータベース中のマッチングされた各項目に割り当てる。
【００３６】
マッチング関数の目的は、すべての項目をユーザのクエリーに対する一致の確率によって順位付けすることである。マッチング関数は、検索が行われている間にどのようにマッチングが行われるか、すなわち、何がマッチングされるか、及び、マッチング関数によって何の変更が行われたかの説明１１４を生成することもできる。この説明を用いて、後の提示における正確なハイライトが生成される。マッチング関数は、たとえば以下のような、誤ってタイプされた文字、スペルミス、誤って理解されている単語の表、すなわちエイリアス表さえ利用することができる。
ＱＴＹ⇔ＱＵＡＮＴＩＴＹ⇔ＣＯＵＮＴ⇔ＮＵＭＢＥＲ⇔ＮＵＭ
【００３７】
いくつかのマッチング関数は、より正確な結果セットが有用でないと仮定して、同一の一致確率値を有する項目の結果セットを生成して、処理時間を低減することができる。これらの結果は、類似の一致値が類似のハイライト強度によって提示される、本発明にとって有用であり得る。
【００３８】
本発明の一実施の形態において、ハイライティングされた結果セットを階層グラフとして提示する。階層グラフ中の各要素の一致する部分がハイライティングされる。ハイライトは、クエリーとの一致の確率を指示することができる。
【００３９】
ハイライトは、クエリーのいずれの部分が一致するか、及びいずれの部分が一致しないかを示すこともできる。ハイライトは、階層に適用するときに引き継ぐことができるか、又は隣接する部分グラフをトラバースすることができ、それによって「最強の」ハイライトが明確に示される。
【００４０】
グラフ中の結果は隠れているか、又は確率閾値を用いて示されることができる。ユーザは、この閾値をスライダを介して表示画面上で設定することができる。このハイライト戦略によって、スライダの有用性が向上する。
【００４１】
図２は、認識され（１２０）、データベース１２５を検索する（１３０）のに用いられる入力クエリー１１１、「china」を示す。結果セットは完全に拡張された階層グラフ２００として提示される。この例において、最高の確率を有する）完全一致２０１が、最強のハイライト、最も大きなフォント、及び最も大きな外郭線を与えられる。部分的一致は、この例においていずれの文字が一致したかを示す、より弱いハイライトを有し、したがって「chair（椅子）」２０２の「ch」、及び「chalk（チョーク）」２０３の「ch」はより弱い（より確率が低い）一致として示されている。結果「table（テーブル）」２０４はこの例ではクエリーと一致しなかったため、ハイライトを有しない。この階層グラフは完全に拡張されており、すべての結果が見える。図３〜図５は、ハイライトがどのように階層をトラバースするかの詳細を示す。図３は、図２に示すクエリー「china」の同じ結果セット２００を示す。しかしながら、この提示では、最強のハイライトが階層を上方に伝播されており、それによって「place（場所）」３０１がここでは最強のハイライト外郭線によって示されている。ここで、「thing（物）」３０２及び「furniture（家具）」３０３はより弱いハイライトによって示されている。
【００４２】
図４は、図３に示すクエリー「china」の検索の同じ結果セット２００を示す。しかしながら、この提示では、一致しない結果「table」２０４は、破線によって示されるように階層から隠れているか又は折り畳まれている。
【００４３】
図５は、同じ結果セット２００を示す。しかしながら、この提示では、階層は完全に折り畳まれており、「ルート」ノード４０１〜４０２のみが階層を上方にトラバースするハイライトによって示されており、一致のカウントが示されている。この提示では、ユーザは、１つの完全一致が「place」４０１に関して見つかり、「thing」４０２に関して２つの弱い一致が見つかったことを依然として観察することができる。
【００４４】
図６は、不明確なクエリーを有する確率論的検索の結果セットを示している。したがって、結果セットは可能な一致の順位付けを有する。階層グラフ２００に適用されると、結果セットは可能性のある一致が、複数の一致の順序付けされた部分グラフに分割され、グラフの深度が複数の一致の相対的な順位付けを指示するグラフを形成する。グラフにおいて、部分グラフの可視性を、確率閾値をグラフに適用することによって制御することができる。
【００４５】
図７に示されるように、検索確率のヒストグラム７００も、検索を改良する指針としてユーザに提示される。これは、閾値を、調整可能な「強度」スライダ７０１の形態でグラフに適用することによって行うことができる。スライダは、拡張される階層の深度も制御する。すなわち、グラフをスライダを介して拡張するか又は折り畳むことができる。
【００４６】
図８は、「china」の検索の同じ結果セット２００を示すが、これらの結果は、階層地理マップ上に示されている。完全一致８１０がハイライティングされており、８２０に位置する階層がハイライティングされている。階層は、ユーザのマップビューが拡大されるか又は手動で制御されている場合に自動的に拡張されるか又は折り畳まれることができる。
【００４７】
図９は、「china」の検索の同じ結果セット２００を示すが、これらの結果は、階層のないマップ上に示されている。追加のマップデータ８４０が示されている。
【００４８】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内でさまざまな他の適合及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべてのこのような変形及び変更を包含することである。
【００４９】
本発明を好適な実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応形態及び変更形態を実施してもよいことが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入るそのような変形形態及び変更形態をすべて網羅することである。
【図１】
2009245424.tif 000003
【図２】
2009245424.tif 000004
【図３】
2009245424.tif 000005
【図４】
2009245424.tif 000006
【図５】
2009245424.tif 000007
【図６】
2009245424.tif 000008
【図７】
2009245424.tif 000009
【図８】
2009245424.tif 000010
【図９】
2009245424.tif 000011
【外国語明細書】
2009245424.tif 000012
2009245424.tif 000013
2009245424.tif 000014
2009245424.tif 000015
2009245424.tif 000016
2009245424.tif 000017
2009245424.tif 000018
2009245424.tif 000019
2009245424.tif 000020
2009245424.tif 000021
2009245424.tif 000022
2009245424.tif 000023
2009245424.tif 000024
2009245424.tif 000025
2009245424.tif 000026
2009245424.tif 000027
2009245424.tif 000028
2009245424.tif 000029
2009245424.tif 000030
2009245424.tif 000031
2009245424.tif 000032
2009245424.tif 000033
2009245424.tif 000034
2009245424.tif 000035
2009245424.tif 000036
2009245424.tif 000037
2009245424.tif 000038
2009245424.tif 000039
2009245424.tif 000040
2009245424.tif 000041
2009245424.tif 000042