(57)【要約】【課題】  改良されたビジュアル・コンテキスト管理技術を提供する。【解決手段】  新しい情報を取り込むように既存のビジュアル表示を更新するための技術は、後のユーザ・クエリによって要求される新しい情報を獲得するステップと、前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出するステップとを含み、前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される。【選択図】  図４
2009512061.tif 000002
【特許請求の範囲】
【請求項１】
新しい情報を取り込むように既存のビジュアル表示を更新する方法であって、
後のユーザ・クエリによって要求される新しい情報を獲得する第１のステップと、
前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２のステップとを含み、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、方法。
【請求項２】
前記第１のステップが、前記ビジュアル・コンテキスト管理制約をフィーチャ・ベースの望ましさメトリックとしてモデル化することをさらに含む、請求項１に記載の方法。
【請求項３】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、表示オーバーラップ値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項４】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、知覚目印の保存値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項５】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、遷移の滑らか値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項６】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、ビジュアル順序値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項７】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、ビジュアル・クラッタ値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項８】
前記第１のステップが、ユーザ情報を使用して、前記フィーチャ・ベースのメトリックを作成するステップをさらに含む、請求項２に記載の方法。
【請求項９】
前記ユーザ情報が、前記ユーザのデータ・ナビゲーション・プリファレンスを含む、請求項８に記載の方法。
【請求項１０】
前記第１のステップが、１つ以上のビジュアル変換オペレータについて前記望ましさメトリックが最大化されるように前記最適化演算を行うステップをさらに含む、請求項２に記載の方法。
【請求項１１】
前記最適化演算が大域的最適化法を含む、請求項１に記載の方法。
【請求項１２】
前記大域的最適化法が焼きなまし法を含む、請求項１１に記載の方法。
【請求項１３】
新しい情報を取り込むように既存のビジュアル表示を更新するための装置であって、
メモリと、
前記メモリに結合されたプロセッサとを備え、
前記プロセッサが、
後のユーザ・クエリによって要求される新しい情報を獲得する第１の動作と、
前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２の動作とを実行し、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、装置。
【請求項１４】
前記第１の動作が、前記ビジュアル・コンテキスト管理制約をフィーチャ・ベースの望ましさメトリックとしてモデル化することをさらに含む、請求項１３に記載の装置。
【請求項１５】
前記第１の動作が、前記フィーチャ・ベースのメトリックのうちの１つとして、表示オーバーラップ値を測定することをさらに含む、請求項１４に記載の装置。
【請求項１６】
前記第１の動作が、前記フィーチャ・ベースのメトリックのうちの１つとして、知覚目印の保存値を測定することをさらに含む、請求項１４に記載の装置。
【請求項１７】
前記第１の動作が、前記フィーチャ・ベースのメトリックのうちの１つとして、遷移の滑らか値を測定することをさらに含む、請求項１４に記載の装置。
【請求項１８】
前記第１の動作が、前記フィーチャ・ベースのメトリックのうちの１つとして、ビジュアル順序値を測定することをさらに含む、請求項１４に記載の装置。
【請求項１９】
前記第１の動作が、前記フィーチャ・ベースのメトリックのうちの１つとして、ビジュアル・クラッタ値を測定することをさらに含む、請求項１４に記載の装置。
【請求項２０】
前記第１の動作が、ユーザ情報を使用して、前記フィーチャ・ベースのメトリックを作成することをさらに含む、請求項１４に記載の装置。
【請求項２１】
前記ユーザ情報が、前記ユーザのデータ・ナビゲーション・プリファレンスを含む、請求項２０に記載の装置。
【請求項２２】
前記第１の動作が、１つ以上のビジュアル変換オペレータについて前記望ましさメトリックが最大化されるように最適化演算を行うことをさらに含む、請求項１４に記載の装置。
【請求項２３】
前記最適化演算が大域的最適化法を含む、請求項１３に記載の装置。
【請求項２４】
前記大域的最適化法が焼きなまし法を含む、請求項２３に記載の装置。
【請求項２５】
１つ以上のプログラムを保持するコンピュータ可読媒体を備え、新しい情報を取り込むように既存のビジュアル表示を更新するための製品であって、前記プログラムが実行されるときに、
後のユーザ・クエリによって要求される新しい情報を獲得する第１のステップと、
前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２のステップとを実装し、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、製品。
【請求項２６】
新しい情報を取り込むように既存のビジュアル表示を更新するためのサービスを提供する方法であって、
サービス・プロバイダが、後のユーザ・クエリによって要求される新しい情報が獲得されることに応答して、前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出するステップを可能にすることを含み、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報探索システムに係り、さらに詳細に説明すれば、情報探索システムにおけるビジュアル・コンテキスト管理用の最適化ベースの技術に係る。
【背景技術】
【０００２】
人間−コンピュータ間の対話では、ユーザが新しい１組のデータを求めるとき、コンピュータ・システムは、そのビジュアル出力プレゼンテーションを動的に更新する必要がある。本発明は、ビジュアル・コンテキスト管理、すなわち、ユーザが全ての関連情報を全体として理解することができるように、新しく要求される情報を既存のビジュアル・コンテキストにどのように取り込むかを動的に決定するプロセスに注目する。ここで、「ビジュアル・コンテキスト」という用語は、ユーザがクエリを発するときに知覚するビジュアル・シーンを意味する。かかるプロセスは、人間−コンピュータ間の会話中に導入される、種々の制約（例えば、意味的な連続性を保証すること及びビジュアル・クラッタを最小化すること）や、不測の情報を免れないことが多い。例えば、新しいデータを伝えるために特定のビジュアル・オブジェクトを導入する場合、関係するデータを提示するための既存のビジュアル・オブジェクトによって影響されることがある。新しい情報を既存のシーンと統合しなければ、ユーザは、情報を比較し且つ組み合わせることに困難を感じることがある。
【０００３】
人間−コンピュータ間の会話がどのように展開するかを予測することは非常に困難であるので、全ての可能なビジュアル・コンテキスト変換を事前に計画することは実際的ではない。従来、研究者及び技術者は、ビジュアル・コンテキスト管理に対する欲張り又はスキーマ・ベースの接近方法を試みた。しかし、これらの接近方法は、通常、一度に１つの制約を扱うに過ぎないばかりか、これらの制約自体が互いにどのように影響するかを考慮していない。その結果、かかる既存の接近方法から得られたビジュアル・コンテキスト管理の結果は、望ましくないことがある。
【特許文献１】「Optimization-Based Data Content Determination」と題する、米国特許出願第１０／９６９５８１号（２００４年１０月２０日出願）
【特許文献２】「Optimization-Based Media Allocation」と題する、米国特許出願第１１／０３１９５１号（２００５年１月７日出願）
【非特許文献１】K. Houck, “Contextual Revision in Information-Seeking Conversation Systems,” ICSLP 2004
【非特許文献２】J. Chai et al., “Context-based MultimodalInput Understanding in Conversation Systems,”Proceedings IEEE ICMI, pp. 67-92, 2002
【非特許文献３】S. Pan, “A Multi-layer Conversation Management Approach for Information-Seeking Applications,” ISCLP 2004
【非特許文献４】M. Zhou and M. Chen, “AutomatedGeneration of Graphic Sketches by Examples,” IJCAI ’03, pp. 65-71, 2003
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従って、改良されたビジュアル・コンテキスト管理技術に対する要請が存在する。
【課題を解決するための手段】
【０００５】
本発明は、改良されたビジュアル・コンテキスト管理技術を提供する。かかる改良されたビジュアル・コンテキスト管理技術は、改良された情報探索システムを構築するために使用することができる。
【０００６】
例えば、本発明の１つの代表的側面では、新しい情報を取り込むように既存のビジュアル表示を更新するための技術は、後のユーザ・クエリによって要求される新しい情報を獲得する第１のステップと、前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２のステップとを含み、前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される。
【０００７】
前記第１のステップは、前記ビジュアル・コンテキスト管理制約をフィーチャ・ベースの望ましさメトリックとしてモデル化することをさらに含むことができる。前記フィーチャ・ベースのメトリックは、表示オーバーラップ値（display overlap value）、知覚目印の保存値（perceptual landmark preservation value）、遷移の滑らか値（transition smoothnessvalue）、ビジュアル順序値（visual ordering value）、ビジュアル・クラッタ値（visual clutter value）のうちの１つ以上を測定することができる。前記フィーチャ・ベースのメトリックは、ユーザ情報、例えば、ユーザのデータ・ナビゲーション・プリファレンスを使用して作成することができる。
【０００８】
前記第１のステップは、１つ以上のビジュアル変換オペレータについて前記望ましさメトリックが最大化されるように前記最適化演算を行うステップをさらに含むことができる。
【０００９】
さらに、前記最適化演算は大域的最適化法（例えば、焼きなまし法（simulated-annealing technique））を含むことができる。
【００１０】
有利なことに、人間−コンピュータ間の会話中に導入される種々の、不測の情報を徐々に提示するために、本発明は、ビジュアル・コンテキスト管理を最適化問題としてモデル化する。１つの主目的は、全ての関連する制約（例えば、意味的な連続性を保証すること及びビジュアル・クラッタを最小化すること）の満足度を最大化する、１組の最適のビジュアル変換を見つけることである。その結果、本発明は、１組の包括的な制約を同時にバランスさせることによって、１組の近似最適のビジュアル変換を導出することができる。かかる技術は、容易に拡張可能である。というのは、かかる技術は、全てのビジュアル・コンテキスト管理制約を一様にモデル化するために、フィーチャ・ベースのメトリックを使用するからである。
【発明を実施するための最良の形態】
【００１１】
以下では、本発明を不動産アプリケーション及びサービス・アプリケーションのような代表的な情報探索アプリケーションに関連して説明する。しかし、本発明は、かかるアプリケーションに限定されないことを理解されたい。むしろ、本発明は、最適化ベースのビジュアル・コンテキスト管理技術及びサービスを提供することが望ましい任意のアプリケーションに対し、一般的に適用可能である。さらに、本発明は、高品質の情報プレゼンテーション又はかかるプレゼンテーション・サービスを提供することが望ましい任意のアプリケーションに対し、一般的に適用可能である。
【００１２】
先ず、次の用語を定義する。「データ・オブジェクト」という用語は、提示することを意図する任意のタイプのデータ内容（例えば、不動産データベース内に存在する住宅リスト又はウェブサイト上に存在するホテルのリスト）を広く意味する。「メディア・オブジェクト」という用語は、データ内容を提示するために使用することができる任意のタイプのメディア（例えば、音声、テキスト、グラフィックス等）を広く意味する。また、「コンテキスト」という用語は、意図したデータ内容のプレゼンテーションが与えられる状況を意味する。これは、ユーザが実行中のタスク、人間−コンピュータ間の対話中に確立された会話コンテキスト、ユーザの嗜好（プリファレンス）及び興味を含むユーザ・モデル、装置プロパティを含む環境モデルのような、情報を含むことができる。
【００１３】
以下で詳述するように、本発明が提供するフレームワーク、システム及び方法は、後のユーザ・クエリによって要求される新しい情報を取り込むように、情報探索システムに関連する既存のビジュアル表示を動的に更新することに係る。かかる技術は、前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する。その場合において、ビジュアル・コンテキスト管理は、種々のビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される。
【００１４】
図面を参照して説明する。図１は、本発明の１つの実施形態に従ったビジュアル・コンテキスト管理コンポーネントを使用する、知的で且つコンテキスト・センシティブな情報探索システムを示す。かかるシステムを「会話システム」と称することもできるが、その理由は、ユーザとシステムの間の１つ以上のクエリと１つ以上の応答のシーケンスを一般的に会話と称することができるからである。
【００１５】
図示のように、情報探索システム１００は、解釈モジュール１０２、会話管理モジュール１０４、内容決定モジュール１０６、コンテキスト管理モジュール１０８及びプレゼンテーション設計モジュール１１０を含む。
【００１６】
解釈モジュール１０２は、K. Houck, “Contextual Revision in Information-Seeking Conversation Systems,” ICSLP 2004 及び／又は J. Chai et al., “Context-based MultimodalInput Understanding in Conversation Systems,”Proceedings IEEE ICMI, pp. 67-92, 2002 に記載の技術を使用することができる。但し、本発明は、かかる技術に限定されるものではない。
【００１７】
また、会話管理モジュール１０４は、S. Pan, “A Multi-layer Conversation Management Approach for Information-Seeking Applications,” ISCLP 2004 に記載の技術を使用することができる。
【００１８】
また、内容決定モジュール１０６は、「Optimization-Based Data Content Determination」と題する、米国特許出願第１０／９６９５８１号（２００４年１０月２０日出願）に記載の技術を使用することができる。
【００１９】
さらに、コンテキスト管理モジュール１０８は、前掲の J. Chai et al., “Context-based MultimodalInput Understanding in Conversation Systems,”Proceedings IEEE ICMI, pp. 67-92, 2002 に記載の技術を使用することができる。
【００２０】
前記コンポーネントによって使用することができる技術について引用された前記文献は、かかるコンポーネントが使用することができる技術の単なる例に過ぎないことを理解されたい。すなわち、かかるコンポーネントは、かかる例示的な技術を実装することに限定されない。
【００２１】
しかし、本発明のビジュアル・コンテキスト管理技術は、好ましくはプレゼンテーション設計モジュール１１０内で実装されることを理解されたい。
【００２２】
システム１００への入力は、１つ以上の形式で（例えば、グラフィカル・ユーザ・インタフェースを通して、又は音声及びジェスチャによって）与えられるユーザ要求である。かかる要求を与えられると、解釈モジュール１０２を使用して、当該要求の意味を解釈する。その解釈結果に基づき、会話管理モジュール１０４は、ハイ・レベルの適切なシステム処置を決定する。コンテキストに依存して、会話管理モジュール１０４は、要求されたデータを提示することによりユーザ要求を直接的に受け入れるように決定するか、又はユーザに対し追加の質問を行うことを選択することができる。ハイ・レベルのシステム処置は、提示すべき正確な内容を記述しないので、このシステム処置は、詳細化のために内容決定モジュール１０６に送られる。
【００２３】
内容決定モジュール１０６は、対話コンテキストに基づいて、応答の適正なデータ内容（例えば、現在のユーザ・クエリ及び時間や空間のような利用可能なプレゼンテーション資源に基づいて、どれだけのデータが検索されるか）を決定する。コンテキスト管理モジュール１０８は、種々の決定（例えば、ユーザの興味及びプリファレンス）を行うために必要とされるコンテキスト情報を管理し且つこれを提供する。一般に、コンテキストのタイプには、会話コンテキスト、ユーザ・コンテキスト及び環境コンテキストの３つがある。かかる情報は、１つ以上のデータベース内に格納することができる。会話情報は、ユーザ要求及びコンピュータ応答のシーケンスを記録する。ユーザ情報は、ユーザのプリファレンス及び興味を含む。環境情報は、システム環境に関する情報（例えば、使用される表示のタイプ）を含む。
【００２４】
データ内容が決定された後、メディア割り振りコンポーネント（図示せず）を使用して、１つ以上のデータ・メディア・マッピングの形式で意図したデータを伝えるために異なるメディアを割り振ることができる。なお、メディア割り振りコンポーネントは、例えば、「Optimization-Based Media Allocation」と題する、米国特許出願第１１／０３１９５１号（２００５年１月７日出願）に記載のものとすることができる。
【００２５】
その後、かかる結果は、提示のためにプレゼンテーション設計モジュール１１０に送られる。前述のように、本発明のビジュアル・コンテキスト管理技術は、好ましくはプレゼンテーション設計モジュール１１０内で実装される。
【００２６】
情報探索システム１００は、知的で且つマルチモーダルの会話の使用を通して、コンテキスト・センシティブな情報アクセス及び探査をサポートする。具体的には、本システムは、ユーザが、自然言語、グラフィカル・ユーザ・インタフェース（ＧＵＩ）及びジェスチャを含む複数の様式を使用して、コンテキストにおいて情報要求を表現することを可能にする。さらに、本システムは、ビジュアル及び音声出力を含む独自の応答を動的に作成する（例えば、図２を参照）。本システムは、種々のアプリケーションのうち任意のアプリケーションで実装できるが、本明細書では、本システムの特徴を説明するため２つの代表的アプリケーション、すなわち、ユーザが居住用財産を探索するのを援助する不動産アプリケーション、並びにユーザがホテル及びその快適な設備（例えば、レストラン）を見つけるのを援助するサービス・アプリケーションを使用する。
【００２７】
ユーザ要求を理解することに基づき、本システムは、その応答を３つのステップで自動的に作成する。第１に、本システムは、応答のタイプを決定する。図２のユーザ・クエリＵ１の場合、本システムは、要求された住宅を直接的に提示することを決定する。コンテキストに依存して、本システムは、異なるタイプの応答を作成することができる。例えば、本システムは、検索されるデータ・セットが非常に大きければ、追加の制約を供給するようにユーザに求めることができる。第２に、本システムは、応答の内容を決定する。Ｕ１に応答する場合、本システムは、価格及び様式のような住宅属性のサブセットを選択する。第３に、本システムは、適切なメディア及びプレゼンテーション技術を使用して、応答の形式を設計する。例えば、図２のシステム応答Ｒ１では、本システムは、グラフィックスを使用して地図上に住宅データを表示し、そして音声を使用して検索された住宅の数を要約する。
【００２８】
ユーザ・クエリＵ２（図２）のような後続の要求を扱うために、本システムは、Ｒ１に関連する既存のビジュアル・コンテキストの殆どを保存しつつ、最も安い住宅を強調する応答Ｒ２を作成する。対照的に、要求Ｕ２’については、本システムは、要求された住宅を拡大表示し、他の住宅を最小表示に維持する（応答Ｒ２’）。ここで、ビジュアル・コンテキストという用語は、ユーザがクエリを発する場合に知覚するビジュアル・シーンを意味する。新しい情報を既存のシーンと統合しなければ、ユーザは、情報を比較し且つ組み合わせることに困難を感じることがある。例えば、応答Ｒ２が最も安い住宅だけを表示するのであれば、ユーザは、この住宅を以前に検索された他の住宅に容易に関係付けることができない。
【００２９】
この例によって実証されるように、本システムは、ユーザ要求に対するその応答をランタイムで調整する。本発明は、ビジュアル・コンテキスト管理、すなわち、ユーザが全ての関連情報を全体として理解することができるように、新しく要求される情報を既存のビジュアル・コンテキストにどのように取り込むかを動的に決定するプロセスに注目する。より正確に説明すれば、ビジュアル・コンテキスト管理を使用して１組のビジュアル変換を導出することにより、新しい情報を取り込むように既存のコンテキストを更新する。例えば、図２の応答Ｒ２を得るために、本システムは、最も安い住宅に詳細事項を追加し且つ検索された他の住宅を単純化することにより、応答Ｒ１を更新する。
【００３０】
図３は、本発明の１つの実施形態に従った、プレゼンテーション設計モジュール（例えば、図１のモジュール１１０）を示す。具体的には、図３は、最適化ベースのビジュアル・コンテキスト管理フレームワーク３００の実施形態を示す。すなわち、このプレゼンテーション設計モジュールによって実装されたビジュアル・コンテキスト管理技術は、ユーザが全ての関連情報を全体として理解することができるように、新しく要求される情報を既存のビジュアル・コンテキストにどのように取り込むかを動的に決定する。
【００３１】
フレームワーク３００への入力は、既存のコンテキスト（以下で詳述）と、伝えるべき１つ以上のデータ・オブジェクト及び１組の利用可能なメディア・オブジェクトの形式を有するプレゼンテーション結果とを含む。例えば、データ・オブジェクトは、ユーザが提示することを要求する１組の住宅とすることができ、メディア・オブジェクトは、音声、テキスト及びグラフィックスのような使用すべき利用可能なメディアを含むことができる。ビジュアル・コンテキスト・マネージャ３０２に従って、最適化されたプレゼンテーションが生成される。以下、かかる最適化されたプレゼンテーションの生成方法を具体的に説明する。
【００３２】
図４は、ビジュアル設計機構とも称する、プレゼンテーション設計モジュール３００（図３）の全体的な動作を示す。このビジュアル設計機構は、与えられたユーザ・クエリを扱うために、ビジュアル出力を自動的に作成する。実施形態では、これは３ステップ・プロセスである。第１に、スケッチ・ジェネレータは、ビジュアル・スケッチを作成する。このスケッチ・ジェネレータは、１組のビジュアル・オブジェクトを使用してビジュアル化すべきデータを符号化する。従来のスケッチ生成技術は、例えば、M. Zhou and M. Chen, “AutomatedGeneration of Graphic Sketches by Examples,” IJCAI ’03, pp. 65-71, 2003 に記載されている。
【００３３】
第２に、ビジュアル・レイアウト・マネージャは、このスケッチ内のビジュアル・オブジェクトのサイズ及び位置を決定する。具体的には、そのプロセスは、ビジュアル・バランスを保証し且つオブジェクト遮蔽（object occlusion）を回避するような、１組の空間レイアウト制約を自動的に導出する。１つの実施形態では、このプロセスは、非線形の制約ソルバを使用して幾何制約（例えば、プロポーショナル及びレイヤリング制約）を解決することができ、そして空間マネージャを使用して浮遊オブジェクト（例えば、コールアウト及び文字ラベル）の位置を決めることができる。
【００３４】
第３に、コンテキスト・マネージャは、スケッチを取り込むように既存のビジュアル・コンテキストを更新する。
【００３５】
このプロセスは３ステップのパイプラインとして実装できるが、これらの３ステップは相互に関連付けることができる。例えば、レイアウト・マネージャは、コンテキスト・マネージャが何を行うかということを殆ど知らないので、コンテキスト・マネージャがどのオブジェクトを維持／削除すべきかを決定した後に、これらのオブジェクトを再配置することを必要とすることがある。これらの２つのステップの間で行ったり来たりするのを回避するため、レイアウト・マネージャは、当該シーン内の各ビジュアル・オブジェクトごとに一連の候補サイズ及び位置パラメータを計算することができる。
【００３６】
以下では、１組の例を使用して、ビジュアル・コンテキスト管理が、ユーザ・プリファレンス及び種々のビジュアル化制約のような多くの要因にどのように影響されるかを説明する。第１に、（ユーザ・クエリ表現によってしばしば暗示される）ユーザのデータ・ナビゲーション・プリファレンスは、ビジュアル・コンテキスト管理に影響を与える。例えば、図２のクエリＵ２は、ユーザがデータを閲覧していることを暗示するのに対し、クエリＵ２’は、ユーザがデータをフィルタしていることを暗示することがある。本システムは、ユーザの意図を推測するために、「まさに」又は「どれが」のような言語キューを使用することができる。従って、クエリＵ２については、本システムは、さらなるデータ閲覧を容易にするためにビジュアル・コンテキストの殆どを保存するのに対し（応答Ｒ２）、クエリＵ２’については、データ・フィルタリングを満たすために最も安い住宅を拡大表示する（応答Ｒ２’）。
【００３７】
さらに、ユーザの会話に関するプリファレンスが、ビジュアル・コンテキスト管理に影響する。デフォルトにより、本システムは、ユーザが連続的な会話を行うものと仮定し、ユーザ・クエリを以前のクエリのコンテキストにおいて解釈する。ここで、図２のクエリＵ１の後に図５のクエリＵ３が発せられるものと仮定する。その延長として、本システムは、応答Ｒ１内に示した関連する住宅を保存しつつ、要求された地区データを提示する。しかし、会話中に、ユーザは新しいコンテキストの開始を望むことがある。その場合、本システムは、ユーザが「新しいコンテキスト」ボタンをクリックして、当該ユーザのコンテクスト・スイッチング・プリファレンスを指示することを許可することができる。クエリＵ１の後にクエリＵ３を発する代わりに、ユーザは、図６のクエリＵ４を発して、新しいコンテキストにスイッチする。この場合、本システムは、要求された学校のデータだけを示す新しいビジュアル出力を作成する。
【００３８】
ユーザのプリファレンスに加えて、複数の表示にわたって連続性を維持したり、ビジュアル・クラッタを最小化するような種々のビジュアル化制約が、ビジュアル・コンテキスト管理に影響を及ぼす。例えば、図５のクエリＵ３について意味的な連続性を維持するために、本システムは、要求された地区データを関連する住宅のコンテキストに取り込む。さらに、図７のビジュアルな連続性を維持するために、本システムは、以前に検索されたホテルと共に要求されたレストランを表示する。但し、本発明者のデータ・オントロジ（data ontology）によれば、これらのレストランとホテルは、遠隔的に関係付けられる。
【００３９】
ユーザ−システム間の会話中に、複数のビジュアル・オブジェクトをビジュアル・コンテキスト内に累積することができる。複雑なビジュアル表示は、ユーザの作業メモリを過負荷にしたり、情報の理解を妨げることがあるので、本システムは、連続性を維持しつつ、ビジュアル・クラッタを最小化するように試みる。クラッタを削減するために、本システムは、図５の住宅及び図７のホテルのような比較的重要でない情報を単純化するか、又は無関係のデータを削除することができる。
【００４０】
また、ユーザが複数のシーンにわたって情報を統合するのを支援するために、本システムは、重要な知覚目印を保存し且つ滑らかな遷移を提供する。例えば、図２では、本システムは、ビジュアルな遷移を固定するのを支援する、ハドソン川や主要な幹線道路のような地理的目印を保存する。さらに、本システムは、ユーザが変更の経過を追うことを可能にするために、滑らかなビジュアル遷移を保証する。例えば、本システムは、カメラの変更及びビジュアル・オブジェクトのアニメーション表示を行うことができる。
【００４１】
従って、本システムは、ユーザのプリファレンスに対応すること、視覚的な連続性を保証すること、ビジュアル・クラッタを最小化することを含む、種々のビジュアル・コンテキスト管理制約を考慮する。これらの制約は、しばしば相互依存性を呈するばかりか、互いに矛盾することもある。例えば、意味的な連続性の保存は、ビジュアル・クラッタの削減制約に違反することがある。従って、全ての制約をバランスさせることができない単純なヒューリスティックスを使用して、一貫性のあるビジュアル・コンテキストを維持することは非常に困難であるだろう。
【００４２】
関連する全ての制約を同時にバランスさせるために、本発明は、ビジュアル・コンテキスト管理に対する最適化ベースの接近方法を提供する。以下では、（例えば、図１の情報探索システム１００のプレゼンテーション設計モジュール１１０によって実装された）この接近方法の詳細を説明する。
【００４３】
このプロセスについては、これを３つのステップに分けて説明する。第１に、ビジュアル・コンテキスト及びビジュアル・オペレータを特徴付ける、本発明のフィーチャ・ベースの表現を提示する（サブセクションＡ）。ここで、ビジュアル・オペレータは、１つ以上のビジュアル・オブジェクトのプロパティを更新する、ビジュアル変換を定義する。例えば、強調表示オペレータは、ビジュアル・オブジェクトの外観を更新する。第２に、定義されたフィーチャを使用して、種々のビジュアル・コンテキスト管理制約を一様にモデル化する、１組のメトリックを作成する（サブセクションＢ）。具体的には、各メトリックは、ビジュアル・コンテキストを更新するために１つ以上のビジュアル・オペレータを適用する望ましさを評価する。第３に、関連する全ての制約（サブセクションＣ）の満足度を最大化することによって１組のビジュアル・オペレータを動的に導出する、焼きなましアルゴリズムを提示する。
【００４４】
（Ａ）フィーチャ・ベースの表現
ビジュアル・コンテキストは、ユーザ−システム間の会話中に継続的に更新される。かかる動的なビジュアル・コンテキストをモデル化するため、各ユーザの順番（user turn）の開始時又は終了時におけるコンテキストの状態を記述する。形式的に、次の表記法を使用する。ユーザの順番t+1 が与えられると、St  は、当該順番の開始時におけるビジュアル・コンテキストを表し、St+1 は当該順番の終了時におけるビジュアル・コンテキストを表す。１組のフィーチャを使用して、St 及び St+1の意味的及び構文的なプロパティを記述する。同様に、１組のフィーチャを使用して、各ビジュアル・オペレータを特徴付ける。
【００４５】
（Ａ）（ｉ）２レベルのビジュアル・コンテキスト表現
ビジュアル・コンテキスト St は、１組のビジュアル・オブジェクトから構成される。例えば、ユーザの順番Ｕ２（図２）の開始時において、ビジュアル・コンテキストは、検索された住宅及び地区（Ｒ１）のようなオブジェクトを含む。Ｓｔ  における全体的なシーン及びこれに関連する各ビジュアル・オブジェクトを特徴付けるために、本発明者は、シーンの全体的なプロパティ及び各ビジュアル・オブジェクトの細目を記述するための２レベルの記述子を開発した。
【００４６】
具体的には、或るシーン内にあるビジュアル・オブジェクトの総数（volume）及び使用される色の数（colorVariety）のような集合化されたフィーチャを使用して、当該シーンを記述する。本発明の目標は、新しいシーンを既存のビジュアル・コンテキストに取り込むことにあるから、同じ１組のフィーチャを使用して、当該新しいシーン（例えば、図２のＵ２における最も安い住宅の細目）を記述する。この統合を容易にするために、 foci 及び scope という２つのフィーチャを追加する。foci というフィーチャは、現クエリの焦点を記述する。これに対し、scope というフィーチャは、当該新しいシーン内に現われるべき全ての情報を含む。図８のクエリＵ８については、foci は、要求された鉄道駅である。これに対し、scope は、当該鉄道駅及び当該鉄道駅を制約する住宅の両方を含む。一のユーザ・クエリを与えられると、本システムは、foci 及び scope の両方を動的に決定する。これらのフィーチャは、カメラ・パラメータを設定し且つ新しいシーンと既存のビジュアル・コンテキストとの間の意味的な関連を評価するために使用される。
【００４７】
全体的なシーンを記述することに加えて、各ビジュアル・オブジェクトのプロパティを特徴付ける。ビジュアル・オブジェクトは、データ・オブジェクトを符号化したものであって、色、サイズ及び位置のような基本的なビジュアル・プロパティを有する。ここで、ビジュアル・コンテキスト管理を容易にするため、データ及びビジュアルな意味的フィーチャに注目する。category のようなデータ・フィーチャを使用して、符号化されたデータの意味的カテゴリを記述し、prominence のようなビジュアル・フィーチャを使用して、ビジュアル符号化がどのように知覚されるかを指定する。次の表１は、本システムが使用する意味的フィーチャをリストする。これらのフィーチャのうち、以下で重点的に説明する３つの複雑なフィーチャは、データ重要度（dImportance）、ビジュアル重要度（vlmportance）及びビジュアル卓立度（prominence）である。なお、表１において記号 * を付したフィーチャは、動的に計算されるものである。
【表１】
2009512061.tif 000003
【００４８】
データ重要度について説明する。「データ重要度」というフィーチャは、所与のユーザの順番に対し、データ・オブジェクトがどの程度重要であるかを指示する。全てのデータ・オブジェクトは、同じ重要度の値（０.０）で開始する。本システムは、データ重要度を２つの方法で動的に更新する。第１に、本システムは、その内容セレクタを使用して、データ重要度を決定する。もし、内容セレクタが、所与のユーザの順番において提示すべきデータ・オブジェクトを選択すれば、その結果、内容セレクタは、このオブジェクトの重要度を更新する。図８のクエリＵ８については、内容セレクタは、最も高い重要度を有する要求された鉄道駅を選択するとともに、より低い重要度を有する鉄道駅を制約する住宅を選択する。もし、データ・オブジェクトが選択されていなければ、その重要度は、時間減衰関数を使用して減少される。例えば、図２のＵ２に応答するために、本システムは、最も安い住宅を除いて、以前に示された住宅を選択しない。従って、それらの重要度の値は、順番Ｕ２において減少される。ユーザが新しいコンテキストを開始する特別なケースでは、本システムは、選択されていないデータの重要度を０.０にリセットする。
【００４９】
第２に、本システムは、データ関係を使用して、データ重要度を決定する。これが非常に有用であるのは、内容セレクタが、同じ重要度を複数のデータ・オブジェクトに割り当てる場合である。応答Ｒ１（図２）では、内容セレクタは、同じ重要度を検索された全ての住宅に割り当てる。これらの住宅は、Ｕ３（図５）では言及されていないので、それらの重要度は減少される。しかし、ハーツデール（Hartsdale）にある住宅は、他の住宅に比べると、Ｕ３に対しより意味的に関連する。その結果、本システムは、検索された地区データ（図５）を理解するのに有用なコンテキストをユーザに供給するために、これらの住宅を良好に保存する。従って、意味に関連するメトリックを次のように定義する。
【数１】
2009512061.tif 000004
【数２】
2009512061.tif 000005
【００５０】
本システムは、データ・オントロジを使用して、d 及び d'jの間のデータ関係 r を検索する。その後、本システムは、当該データベースを使用して、当該関係を確認する。ここで、d を住宅とし、 d'j をデータベース内の地区とする。本発明のオントロジによれば、住宅は地区内に位置する。本システムは、この関係を使用して、住宅 d がデータベース内の地区 d'j に実際に存在するか否かを確認する。この関係が成立すれば、 β=1 であり、さもなければ、 β=0 である。次に、オントロジにおけるデータ関係の各タイプごとに r() の値を静的に定義する。
【００５１】
要するに、所与のユーザの順番 t+1 におけるデータ・オブジェクト d のデータ重要度を次式のように定義する。
【数３】
2009512061.tif 000006
【００５２】
ビジュアル重要度について説明する。データ重要度は、ビジュアル・オブジェクトがユーザ・クエリに対しどのように意味的に関係するかを評価する。これに対し、ビジュアル重要度は、ビジュアル・オブジェクトが現クエリの foci に対しどのように空間的に関係付けられるかを測定する。一般に、ユーザが要求した情報を提示する場合、近傍に位置するアイテムを示すことが望ましい。なぜなら、かかるアイテムは、ユーザが意図した情報を理解するのに有用なコンテキストを確立することを援助するからである。例えば、図７の（ｂ）では、本システムは、要求されたレストランに加えて、近傍のホテルを示すことにより、全てのアイテムが何処にあるかという全体的な印象をユーザに与えるようにしている。
【００５３】
この概念によって、ビジュアル重要度というフィーチャは、次式に示すように、現クエリのfoci のビジュアル表現 V' に対するビジュアル・オブジェクト v の空間的関連度である。
【数４】
2009512061.tif 000007
【００５４】
ビジュアル卓立度について説明する。ビジュアル卓立度は、ユーザがビジュアル・オブジェクトをどの程度容易に知覚することができるかを測定する。ビジュアル卓立度は、色、サイズ及び位置という３つの基本的なビジュアル変数を使用してモデル化される。ビジュアル・オブジェクト v が与えられると、その色卓立度 P1(v)、サイズ卓立度 P2(v)及び位置卓立度 P3(v)を定義する。
【００５５】
色卓立度は、背景に対するビジュアル・オブジェクトのコントラストが増大すればするほど、当該ビジュアル・オブジェクトの知覚を容易にする卓立度が増大することを記述する。例えば、背景が白色である場合、赤色のオブジェクトは、黄色のオブジェクトよりも目立ち安い。関数 contrast() は、次式に示すように、２色間のコントラスト値を戻す。
【数５】
2009512061.tif 000008
【００５６】
サイズ卓立度は、ビジュアル・オブジェクトが大きくなればなるほど、当該ビジュアル・オブジェクトが目立って現われることを記述する。これは、次式に示す通りである。
【数６】
2009512061.tif 000009
【００５７】
位置卓立度は、表示の中心近傍に置かれたオブジェクトが、他の任意の位置に置かれたオブジェクトよりも目立つことを記述する。これは、次式に示す通りである。
【数７】
2009512061.tif 000010
【００５８】
前記３つの式を組み合わせることにより、次式に示すように、ビジュアル・オブジェクト v の全体的なビジュアル卓立度がモデル化される。
【数８】
2009512061.tif 000011
【００５９】
（Ａ）（ｉｉ）ビジュアル・オペレータ表現
ビジュアル・コンテキストを更新し且つ新しい情報を取り込むビジュアル変換をモデル化するために１組のビジュアル・オペレータを使用する。ビジュアル・オペレータは、それらの効果に基づいて、分類することができる。本発明者は、４グループのオペレータとして、カメラのパラメータを修正するカメラ・オペレータと、ビジュアル外観を更新する外観オペレータ（例えば、Highlight ）と、幾何的プロパティを変更する幾何的オペレータ（例えば、Move 及び Scale ）と、シーン構造を修正する構造オペレータ（例えば、Add ）とを識別した。次の表２は、本システムが使用するオペレータをリストする。実際の実装に依存して、オペレータは、異なるビジュアル効果を呈することがある。例えば、オブジェクトを透明にするか、又は単にオブジェクトを隠蔽することによって、Delete を実装することができる。
【表２】
2009512061.tif 000012
【００６０】
全てのビジュアル・オペレータを一様に表すために、各オペレータを７つのフィーチャに関連付ける。フィーチャ・オペランドは、オペレータが演算するビジュアル・オブジェクトを表し、フィーチャ・パラメータは、意図した変換を実行するために必要とされる特定の情報を保持する。以下に示すように、Scale というオペレータは、scaleFactor という１つのパラメータを有する。effect というフィーチャは、演算の後にオペランドのどのプロパティが修正されるべきかを測定する関数である。例えば、Scale は、オブジェクトのサイズを変更する。他方、cost というフィーチャは、意図したビジュアル変換を実行するコストを評価する。Cost は、ユーザが当該変換を知覚するのに必要な知覚的コストを測定する。例えば、ユーザにとっては、強調表示の効果よりもオブジェクトの移動を知覚する方がより高価につく。最後に、temporal-priority、startTime 及びendTime というフィーチャは、オペレータを適用するタイミングを制御する。次の表３は、Scale というオペレータの定義を概説する。
【表３】
2009512061.tif 000013
【００６１】
（Ｂ）フィーチャ・ベースの望ましさメトリック
前述のように、多くの制約は、ユーザのプリファレンス及びビジュアル化制約を含む、ビジュアル・コンテキスト管理に影響を及ぼす。全ての制約を一様にモデル化するために、ビジュアル・コンテキスト及びビジュアル・オペレータの表現に基づいて、１組のメトリックを定義する。これらのメトリックは、新しい情報を取り込むように既存のビジュアル・コンテキストに１つ以上のビジュアル・オペレータを適用することの望ましさを評価する。それらの目的に沿って、これらのメトリックを２つのグループ、すなわちビジュアル運動量メトリック及びビジュアル構造化メトリックに分割する。ビジュアル運動量メトリックは、複数の表示間にわたるビジュアル・コンテキストの一貫性を評価する。ビジュアル構造化メトリックは、新しい情報が統合された後、ビジュアル・コンテキストの構造的な一貫性を評価する。ここでの目的は、完全な１組のビジュアル・コンテキスト管理制約を列挙することではない。そうではなく、重要な制約をどのようにして定量化するかを示すことである。説明の便宜上、全てのフィーチャ／メトリック値は、［０，１］の間に位置するように正規化される。
【００６２】
（Ｂ）（ｉ）ビジュアル運動量メトリック
ビジュアル運動量は、複数の表示にわたって情報を抽出し且つ統合するユーザの能力を測定する。ビジュアル運動量の値は、複数の表示にわたって情報を理解するユーザの能力に比例する。このため、本システムは、ビジュアル・コンテキストを更新するときに、そのビジュアル運動量を最大化するように試みる。具体的には、ビジュアル・コンテキスト管理タスクに適用可能な３つの技術を使用する。すなわち、（１）連続的な表示の意味的及びビジュアル・オーバーラップを最大化する技術、（２）知覚的な目印を保存する技術、（３）滑らかなビジュアル遷移を保証する技術を使用するということである。
【００６３】
表示オーバーラップの最大化について説明する。適正な表示オーバーラップは、連続的な表示間にわたる情報を、ユーザが徐々につなぎ合わせることを支援する。２つのメトリック、すなわちビジュアル・オーバーラップ・メトリック及び意味的オーバーラップ・メトリックを定義する。ビジュアル・オーバーラップ・メトリックは、２つの表示間の不変性、特に、各ビジュアル・オブジェクトの状態 St とその新しい状態 St + 1 の間の平均的不変性を次式のように計算する。
【数９】
2009512061.tif 000014
【数１０】
2009512061.tif 000015
【００６４】
同様に、複数の表示にわたって意味的に関係するアイテムがともに残っているか否かを評価する、意味的オーバーラップ・メトリックを定義する。これは、次式に示すように、St 及び St + 1 の意味的な関連性を計算する。
【数１１】
2009512061.tif 000016
【００６５】
前述のように定義されたビジュアル・オーバーラップ・メトリック及び意味的オーバーラップ・メトリックを使用して、ユーザ・ナビゲーション・プリファレンスによって規制される、全体的な表示オーバーラップをモデル化する。これは、次式に示すように、データ閲覧のためにより多くの表示オーバーラップを許容するが、データ・フィルタリングのためにより少ないオーバーラップしか許可しない。
【数１２】
2009512061.tif 000017
【００６６】
知覚目印の保存について説明する。知覚目印は、ユーザが連続するシーン内の情報を関係付けることを援助する、ビジュアル・コンテキスト遷移を固定する識別しやすいフィーチャである。例えば、米国ニューヨーク州ウェストチェスタ郡の地図が、図２及び図４〜図６に示される表示用の共通の背景として用いられ、そして可能である限り、主要な川及びハイウェイのような重要な地理的目印（例えば、図２のハドソン川）が複数のシーン内に存続する。ビジュアル・コンテキスト内に最大数の知覚目印を保存するため、次式に示すように、当該コンテキスト内にある目印の正規化された数をカウントする。
【数１３】
2009512061.tif 000018
【００６７】
滑らかな遷移の保証について説明する。シーン内の突然の変化は、ユーザがこれらの変化を視覚的に追跡するのを困難にする。その結果、既存のシーンと新しいシーンとの間の因果関係が失われることがある。連続的な表示間の滑らかな遷移を保証するために、アニメーションを使用して、ユーザに対しこれらの変化を解釈するための強力なキューを提供することがしばしば行われる。１組のビジュアル・オペレータを適用する場合の平均的な滑らか度を計算するためのメトリックを、次式のように定義する。
【数１４】
2009512061.tif 000019
【００６８】
前記メトリックは、オペレータが被る精神的コストが小さくなればなるほど、ユーザが知覚する遷移がより滑らかになることを記述する。
【００６９】
式（４）〜式（６）を組み合わせて、最大の表示間連続性を保証するための全体的なビジュアル運動量メトリックを、次式のように定義する。
【数１５】
2009512061.tif 000020
【００７０】
（Ｂ）（ｉｉ）ビジュアル構造化メトリック
ビジュアル・コンテキストの遷移中にビジュアル運動量を最大化することに加えて、当該遷移の後に当該コンテキストの構造が一貫していることを保証する。図４のスケッチ生成は、ビジュアル符号化に関する構造化問題を扱うので、ここでは、２つの側面からビジュアル統合に関する構造化問題に注目する。１つは、ユーザが新しい内容に容易に専念できるように、適正なビジュアル順序を保証することである。他は、新しい情報の統合後にビジュアル・クラッタを最小化することである。
【００７１】
適正なビジュアル順序の確立について説明する。適正なビジュアル順序を確立するため、現ユーザ・クエリにとって重要なデータ・アイテムが目立って表現されるように制約する。例えば、図８の（ｂ）では、本システムは、新しく要求された鉄道駅の情報を強調表示する一方、住宅の表現を当該鉄道駅へのそれらの関連性に基づいて単純化する。すなわち、これらの鉄道駅を制約する住宅が僅かに単純化されるのに対し、他の住宅はそれらの最小値に減少される（図８の（ａ）及び（ｂ）を参照）。データの重要度及びビジュアルな卓立度の間のかかる所望の相関性を捕捉するため、ビジュアル順序メトリックを次式のように定義する。
【数１６】
2009512061.tif 000021
【数１７】
2009512061.tif 000022
【００７２】
ビジュアル・クラッタの最小化について説明する。視覚的に乱雑なプレゼンテーションは混乱を生み、シーンの走査を不可能にすることがある。有用な情報を有するが乱雑でないビジュアル・コンテキストを提供するため、表示の全体的な複雑度を測定する。ビジュアルな複雑度に影響する、複数組の要因が知られている。１組の要因は、シーン内に現われる異なる色及び形状の数のような、オブジェクトの量及びそれらのプロパティの変化を含む。他の１組の要因は、対称性及び開放性のような、シーンの空間レイアウトに関係がある。図４のレイアウト・マネージャは、対称性を含む空間レイアウト制約を維持するので、ここでは、最初の１組の要因を使用して、ビジュアル複雑度を次式のように測定する。
【数１８】
2009512061.tif 000023
【００７３】
メトリック areaUsage() は、St + 1 によって占有される正規化スクリーン空間を次式のように計算する。
【数１９】
2009512061.tif 000024
【００７４】
メトリックshapeComplexity() は、次式に示すように、St+1 における異なる形状の総数及び全ての形状の平均的な複雑度を計算する（異なる形状は、異なる複雑度値を割り当てられる。例えば、テキストは、円のような簡単な幾何形状よりも複雑であると見なされる。）。
【数２０】
2009512061.tif 000025
【００７５】
シーンのビジュアル複雑度を最小化するために、以下の式を最大化する。
【数２１】
2009512061.tif 000026
【００７６】
（Ｃ） 焼きなましアルゴリズム
式（７）〜式（９）を組み合わせて、全体的な目的関数を次式のように定義する。
【数２２】
2009512061.tif 000027
【００７７】
ここでの目標は、目的関数を最大化するような１組のビジュアル・オペレータを見つけることである。このタスクは、典型的な二次割当問題を解決することであり、これはＮＰ困難である。単純な欲張りアルゴリズムは、ローカルな極大に陥ることがあるので、本発明は、このクラスの問題を解決するのに有効であることが分かっている焼きなまし法を使用する。
【００７８】
次の表４は、例示的な焼きなましアルゴリズムを概説する。
【表４】
2009512061.tif 000028
【００７９】
このアルゴリズムへの入力は、ユーザの順番 t + 1の開始時におけるビジュアル・コンテキスト S 及び統合すべき新しいシーン S´ である。このアルゴリズムは、所望の結果リストに反復的に追加するために（第２行〜第１５行）、「温度」パラメータ T を使用する。本発明者の実験では、 T0=2.0、最小温度 Tmin=0.05 及び減少率 Δt=0.1 であるように T を初期化した。これらの値は、ともに反復の回数を制御するものである。
【００８０】
各反復中、このアルゴリズムは１組のオペレータをサンプルする（今や MAX_SAMPLE_COUNT=40）（第４行〜第１３行）。各サンプリングでは、ルーチン find_operator() は、欲張り戦略を使用して一番上の候補を見つける（第５行）。具体的には、このアルゴリズムは、既に選択されたオペレータ及びオペレータ op を同じオペレータによって更新されていないビジュアル・オブジェクトに適用するために、reward() を計算する（式（１０））。その後、このアルゴリズムは、全ての候補をそれらの報酬値によってランク付けし、一番上のものを戻す。このアルゴリズムは、一番上の候補及び既存の１組の結果を使用して、前記報酬が、既存の１組の結果だけを使用する場合よりも大きいか否かをテストする（第７行〜第８行）。もし、前記報酬の方が良ければ、一番上の候補が既存の１組の結果に追加される（第９行）。さもなければ、このアルゴリズムは、現在の制御確率が、[０，１]の間で rand() によって生成される乱数より大きいか否かをテストする（第１０行）。それが真であれば、前記候補が追加される（第１１行）。
【００８１】
各反復中、パラメータ T は、最適以下のオペレータを受け入れる確率を制御する。すなわち、このアルゴリズムが最適以下のオペレータを受け入れる可能性を小さくするように、パラメータ T は徐々に減少される（第１４行）。このアルゴリズムが最終的に収束する場合（すなわち、T が目標の最小温度に達する場合）、このアルゴリズムは、式（１０）の目的関数を最大化する、１組のビジュアル・オペレータを戻す（第１６行）。複雑度の find_operator() は、 O(n2×m2) である。但し、n は St 及び S´ におけるビジュアル・オブジェクトの総数であり、m は使用可能なオペレータの数である。温度減少中のステップ数及び各温度において評価されるサンプルの総数は一定であるので、このアルゴリズムの総合的な複雑度は O(n2×m2) である。
【００８２】
１組の所望のビジュアル・オペレータを見つけた後、本システムは、当該オペレータをそれらのタイプ及びそれらのオペランドによってグループ化する。例えば、本システムは、同じタイプのオペランドを有する全ての Highlight オペレータをともにグループ化する。その後、本システムは、これらのオペレータを適用する順序を決定する。１グループ内のオペレータは、同時に適用することができる。かかる適用は、ビジュアル遷移中に知覚的なグループを認識するようにユーザをガイドする。例えば、１グループの住宅を同時に強調表示すると、ユーザは、それらの住宅をグループとして知覚することができる。さらに、異なるグループ内のオペレータは、時間的な優先順位によって順序付けられる。例えば、古いデータが新しいデータを上書きするのを防止するため、通常の場合、Delete はAdd よりも前に生じる。ここで、オペレータの各タイプごとの時間的な優先順位を静的に定義する。
【００８３】
１つの実施形態では、ビジュアル・コンテキスト管理方法を設定するために、３つのステップが使用される。第１に、データ意味カテゴリを割り当てるような静的フィーチャを定義する（表１）。本発明者の経験から、簡単なデータ・オントロジを構築すると、これらのフィーチャを定義するのが楽になる。第２に、ビジュアル・オペレータのカタログを構築する（表２）。第３に、アプリケーションにとって重要な種々の制約をモデル化するために、フィーチャ・ベースのメトリックを作成する。例えば、モバイル・アプリケーションでは、装置に依存するビジュアル・コンテキスト管理制約をモデル化することができる。また、アプリケーションのニーズに基づいて、メトリックのチューニングを望むことがある。例えば、データ閲覧アプリケーションでは、表示オーバーラップのための重みを増加させることができる（式（４））。
【００８４】
本プロセスをブートストラップし且つチューニング上の誤りを回避するためには、単純に開始することを提案する。前述の説明では、２つの異なるアプリケーションにおける種々の対話状況を適正に扱うために、簡単なデータ・オントロジ、１組の基本的なビジュアル・オペレータ及び等しく重み付けられたメトリック（式（１０））を使用した。必要であれば、これを拡張するのは容易である。第１に、新しいビジュアル・オペレータを容易に導入することができる（例えば、ビジュアル・モーフィング用の魚眼ビュー・オペレータの追加）。さらに、所望の機能性を得るため、本発明の目的関数に新しいフィーチャ／メトリック（例えば、装置に依存するオペレータ・コスト・メトリック）を容易に取り込むことができる。
【００８５】
マルチモーダル会話システムをサポートすることに加えて、ビジュアル・コンテキスト管理に対する本発明の接近方法は、一層良好なビジュアル出力を作成するというより広い問題に適用可能である。例えば、この接近方法は、ＧＵＩ駆動式の対話型のビジュアル出力システム内で使用することができ、その場合には、ユーザ対話の複数の順番にわたって得られる情報を統合するために、より一貫性のあるビジュアル出力を生成することができる。
【００８６】
対話型環境においてビジュアル出力を作成する場合、全体的なコンテキストの一貫性を保証するために、新しい情報を既存の表示へどのようにして徐々に統合するかを動的に決定することが必要である。以上で詳述したように、本発明は、ビジュアル・コンテキスト管理に対する最適化ベースの接近方法を提示する。既存のビジュアル・コンテキスト及び新しい情報を与えられると、本発明の目標は、最良の態様で既存のビジュアル・コンテキストを更新し且つ新しい情報を取り込むことができる、１組のビジュアル・オペレータを見つけることである。この目標を達成するため、本発明は、ビジュアル順序を保存し、ビジュアル運動量を維持するような種々のコンテキスト管理制約をモデル化するための、１組のメトリックを形成する。これらのメトリックを使用して、本発明は、１組のビジュアル・オペレータを適用する場合の全体的な望ましさを評価するために、全体的な目的関数を定義する。最後に、本発明は、焼きなましアルゴリズムを使用して目的関数を最大化し、所望のオペレータを見つける。
【００８７】
前述の制約のサブセットをより決定論的なコンテキストでしばしば考慮する既存の接近方法とは異なり、本発明の最適化ベースの接近方法は、種々の対話状況について包括的な１組の制約を動的にバランスさせる。また、本発明は、新しいフィーチャ／制約を容易に取り込むことができるという理由で、容易に拡張可能である。本発明を２つの異なるアプリケーションに適用した結果は、本システムが、人間の設計者に対して遜色がないほど適切に機能することを示している。
【００８８】
最後に、図９を参照して説明する。図９は、本発明の１つの実施形態に従った情報探索システムを実装するのに適したコンピュータ・システムを示す。例えば、図９のアーキテクチャは、図１〜図８を参照して説明した任意及び全てのコンポーネント及び／又はステップを実装するのに使用することができる。
【００８９】
図示のように、コンピュータ・システム９００は、プロセッサ９０２、メモリ９０４、Ｉ／Ｏ装置９０６及びコンピュータ・バス９１０又は代替的接続手段を介して結合されたネットワーク・インタフェース９０８に従って、実装することができる。
【００９０】
「プロセッサ」という用語は、例えばＣＰＵ（中央処理装置）及び／又は他の処理回路を含む、任意の処理装置を包含するものと理解されたい。また、「プロセッサ」という用語は、複数の処理装置を意味することがあり、そして一の処理装置に関連する種々の要素を他の処理装置によって共有可能であることも理解されたい。
【００９１】
「メモリ」という用語は、プロセッサ又はＣＰＵに関連するメモリ、例えば、ＲＡＭ、ＲＯＭ、固定メモリ装置（例えば、ハードドライブ）、取り外し可能なメモリ装置（例えば、フレキシブル・ディスク）、フラッシュ・メモリ等を含むように意図される。
【００９２】
また、「Ｉ／Ｏ装置」という用語は、処理装置にデータを入力するための１つ以上の入力装置（例えば、キーボード、マウス等）及び／又は処理装置に関連する結果を提示するための１つ以上の出力装置（例えば、スピーカ、表示装置等）を含むように意図される。
【００９３】
また、「ネットワーク・インタフェース」という用語は、例えば、コンピュータ・システムが適切な通信プロトコルを介して他のコンピュータ・システムと通信することを可能にする、１つ以上のトランシーバを含むように意図される。
【００９４】
従って、本明細書で説明した方法を実施するための命令又はコードを含むソフトウェア・コンポーネントは、これを関連するメモリ装置（例えば、ＲＯＭ、固定式又は取り外し可能なメモリ）の１つ以上に格納し、そして使用する準備が完了した場合、その一部又は全部を（例えば、ＲＡＭへ）ロードし、ＣＰＵによって実行することができる。
【００９５】
さらに、本発明は、ビジュアル・コンテキスト管理サービスを提供するための技術を含むことを理解されたい。例えば、サービス・プロバイダは、ビジュアル・コンテキスト管理サービスを提供することについて、（例えば、サービス・レベルの契約又は他の非公式の合意を介して）サービス顧客又はクライアントと合意する。すなわち、１つの例だけを挙げれば、サービス・プロバイダは、顧客のウェブ・サイト及び関連するアプリケーションをホストすることができる。その場合、サービス・プロバイダは、当該サービス・プロバイダとサービス顧客との間の契約条件に従って、本明細書で説明した１つ以上の方法を含むビジュアル・コンテキスト管理サービスを提供することができる。
【００９６】
以上では、添付の図面を参照して本発明の実施形態を説明したが、本発明はこれらの実施形態それ自体に限定されるものではないこと、そして当業者によれば、本発明の範囲又は精神から逸脱することなく、種々の他の変更及び修正をなし得ることを理解されたい。
【図面の簡単な説明】
【００９７】
【図１】本発明の１つの実施形態に従った、ビジュアル・コンテキスト管理コンポーネントを使用する、知的で且つコンテキスト・センシティブな情報探索システムを示す図である。
【図２】本発明の１つの実施形態に従った、第１の記録済みユーザ−システム会話フラグメントを示す図である。
【図３】本発明の１つの実施形態に従った、ビジュアル・コンテキスト管理フレームワークを示す図である。
【図４】本発明の１つの実施形態に従った、ビジュアル出力生成方法を示す図である。
【図５】本発明の１つの実施形態に従った、第２の記録済みユーザ−システム会話フラグメントを示す図である。
【図６】本発明の１つの実施形態に従った、第３の記録済みユーザ−システム会話フラグメントを示す図である。
【図７】本発明の１つの実施形態に従った、第４の記録済みユーザ−システム会話フラグメントを示す図である。
【図８】本発明の１つの実施形態に従った、第５の記録済みユーザ−システム会話フラグメントを示す図である。
【図９】本発明の１つの実施形態に従った、情報探索システムを実装するのに適したコンピュータ・システムを示す図である。
【符号の説明】
【００９８】
１００  情報探索システム
１０２  解釈モジュール
１０４  会話管理モジュール
１０６  内容決定モジュール
１０８  コンテキスト管理モジュール
１１０  プレゼンテーション設計モジュール
３００  プレゼンテーション設計モジュール
３０２  ビジュアル・コンテキスト・マネージャ
【図１】
2009512061.tif 000029
【図２】
2009512061.tif 000030
【図３】
2009512061.tif 000031
【図４】
2009512061.tif 000032
【図５】
2009512061.tif 000033
【図６】
2009512061.tif 000034
【図７】
2009512061.tif 000035
【図８】
2009512061.tif 000036
【図９】
2009512061.tif 000037
【手続補正書】
【提出日】平成20年12月8日(2008.12.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
新しい情報を取り込むように既存のビジュアル表示を更新する方法であって、
後のユーザ・クエリによって要求される新しい情報を獲得する第１のステップと、
前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２のステップとを含み、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、方法。
【請求項２】
前記第１のステップが、前記ビジュアル・コンテキスト管理制約をフィーチャ・ベースの望ましさメトリックとしてモデル化することをさらに含む、請求項１に記載の方法。
【請求項３】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、表示オーバーラップ値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項４】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、知覚目印の保存値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項５】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、遷移の滑らか値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項６】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、ビジュアル順序値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項７】
前記第１のステップが、前記フィーチャ・ベースのメトリックのうちの１つとして、ビジュアル・クラッタ値を測定するステップをさらに含む、請求項２に記載の方法。
【請求項８】
前記第１のステップが、ユーザ情報を使用して、前記フィーチャ・ベースのメトリックを作成するステップをさらに含む、請求項２に記載の方法。
【請求項９】
前記ユーザ情報が、前記ユーザのデータ・ナビゲーション・プリファレンスを含む、請求項８に記載の方法。
【請求項１０】
前記第１のステップが、１つ以上のビジュアル変換オペレータについて前記望ましさメトリックが最大化されるように前記最適化演算を行うステップをさらに含む、請求項２に記載の方法。
【請求項１１】
前記最適化演算が大域的最適化法を含む、請求項１に記載の方法。
【請求項１２】
前記大域的最適化法が焼きなまし法を含む、請求項１１に記載の方法。
【請求項１３】
新しい情報を取り込むように既存のビジュアル表示を更新するための装置であって、
メモリと、
前記メモリに結合されたプロセッサとを備え、
前記プロセッサが、
後のユーザ・クエリによって要求される新しい情報を獲得する第１の動作と、
前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２の動作とを実行し、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、装置。
【請求項１４】
１つ以上のプログラムを保持するコンピュータ可読媒体を備え、新しい情報を取り込むように既存のビジュアル表示を更新するためのシステムであって、前記プログラムが実行されるときに、
後のユーザ・クエリによって要求される新しい情報を獲得する第１のステップと、
前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出する第２のステップとを実装し、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、システム。
【請求項１５】
新しい情報を取り込むように既存のビジュアル表示を更新するためのサービスを提供する方法であって、
サービス・プロバイダが、後のユーザ・クエリによって要求される新しい情報が獲得されることに応答して、前記新しい情報を取り込むように前記既存の表示の少なくとも一部を更新するための１つ以上のビジュアル変換を動的に導出するステップを可能にすることを含み、
前記変換の導出が、ビジュアル・コンテキスト管理制約をバランスさせ且つ意図される情報の所望のプレゼンテーションを達成するように試みる最適化演算としてモデル化される、方法。
【国際調査報告】
2009512061.tif 000038