(57)【要約】【課題】階層情報を判別するためのシステムおよび方法を提供する。【解決手段】態様は、非テキスト情報を階層内容に構文解析するためにコリンズモデルを使用することを含んでいる。システムおよび方法は、行が相互にどのように関連するかを示すラベルを行に割り当てる。【選択図】図６
2006146894.tif 000002
【特許請求の範囲】
【請求項１】
受信した非テキスト情報の階層内容を認識する方法であって、
非テキスト情報を受信するステップと、
未処理特徴情報を判別するステップと、
前記未処理特徴情報から追加の特徴を判別するステップと、
前記受信情報内の各行に対してラベルを計算するステップと
を備えることを特徴とする方法。
【請求項２】
追加の特徴を判別する前記ステップは、
基本行特徴を判別するステップ
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記受信情報を前処理するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記前処理するステップは、
前記受信情報をローテーションするステップ
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記計算するステップは、コリンズモデルの適用を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記計算するステップは、トレーニングデータによりトレーニングされたコリンズモデルの適用を含むことを特徴とする請求項１に記載の方法。
【請求項７】
非テキスト情報の階層構造を判別する方法であって、
非テキスト情報を受信するステップと、
非テキスト情報の行を観察シーケンスｓｔとして処理するステップと、
ラベルシーケンスのコストが、
【数１】
2006146894.tif 000011
となるように、ラベルｌｔのシーケンスを見つけるために前記観察シーケンスｓｔを処理するステップであって、
Ｌは時間のラベルのシーケンスであり、ｓは観察のシーケンスであり、ｔはシーケンス内の位置であり、｛ｌｔ｝およびλｉはモデルパラメータであるステップと
を備えることを特徴とする方法。
【請求項８】
前記モデルパラメータは、前記モデルパラメータをトレーニング例内でラベルに収束するように調整することによって決定されることを特徴とする請求項７に記載の方法。
【請求項９】
【数２】
2006146894.tif 000012
となるように重みのセットを見つけることにより、トレーニング例｛Ｌｋ、ｓｋ｝を使用してモデルパラメータを決定するステップをさらに含むことを特徴とする請求項７に記載の方法。
【請求項１０】
各行は多数の特徴を含むように決定され、前記特徴はラベルを前記行に割り当てるために使用されることを特徴とする請求項７に記載の方法。
【請求項１１】
各行についてのインデントレベルを推定するステップであって、前記インデントレベルは特徴であるステップをさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
黒丸が行内に存在するかどうかを判別するステップであって、前記黒丸の存在は特徴であるステップをさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１３】
受信した非テキスト情報の階層内容を認識するシステムであって、
非テキスト情報を受信する手段と、
未処理特徴情報を判別する手段と、
前記未処理特徴情報から追加の特徴を判別する手段と、
前記受信情報内の各行についてラベルを計算する手段と
を備えることを特徴とするシステム。
【請求項１４】
追加の特徴を判別する前記手段は、
基本行特徴を判別する手段
をさらに含むことを特徴とする請求項１３に記載のシステム。
【請求項１５】
前記受信情報を前処理する手段をさらに備えることを特徴とする請求項１３に記載のシステム。
【請求項１６】
前処理する前記手段は、
前記受信情報をローテーションする手段をさらに備えることを特徴とする請求項１３に記載のシステム。
【請求項１７】
前記計算する手段は、コリンズモデルの適用を含むことを特徴とする請求項１３に記載のシステム。
【請求項１８】
前記計算する手段は、トレーニングデータによりトレーニングされたコリンズモデルの適用を含むことを特徴とする請求項１３に記載のシステム。
【請求項１９】
非テキスト情報の階層構造を判別するためのシステムであって、
非テキスト情報を受信する手段と、
非テキスト情報の行を観察シーケンスｓｔとして処理する手段と、
ラベルシーケンスのコストが、
【数３】
2006146894.tif 000013
となるように、ラベルｌｔのシーケンスを見つけるために前記観察シーケンスｓｔを処理する手段であって、
Ｌは時間のラベルのシーケンスであり、ｓは観察のシーケンスであり、ｔはシーケンス内の位置であり、｛ｌｔ｝およびλｉはモデルパラメータである手段と
を備えることを特徴とするシステム。
【請求項２０】
前記モデルパラメータは、前記モデルパラメータをトレーニング例内でラベルに収束するように調整することによって決定されることを特徴とする請求項１９に記載のシステム。
【請求項２１】
【数４】
2006146894.tif 000014
となるように重みのセット｛λｉ｝を見つけることにより、トレーニング例｛Ｌｋ、ｓｋ｝を使用してモデルパラメータを決定する手段をさらに備えることを特徴とする請求項１９に記載のシステム。
【請求項２２】
非テキスト情報を階層形式に構文解析するシステムであって、
非テキスト情報を受信する入力と、
ラベルを前記非テキスト情報の行に適用するために条件付きランダムフィールドを使用するプロセッサと、
前記非テキスト情報の行に関連付けられているラベルを出力する出力であって、前記ラベルは前記非テキスト情報の前記階層形式を記述する出力と
を備えることを特徴とするシステム。
【請求項２３】
前記ラベルを決定するために使用される前記条件付きランダムフィールドは、
【数５】
2006146894.tif 000015
であり、ここでＬは時間のラベルのシーケンスであり、ｓは観察のシーケンスであり、ｔはシーケンス内の位置であり、｛ｌｔ｝およびλｉはモデルパラメータであることを特徴とする請求項２２に記載のシステム。
【請求項２４】
前記プロセッサは、
【数６】
2006146894.tif 000016
となるように重みのセットを見つけることにより、トレーニング例｛Ｌｋ、ｓｋ｝を使用してモデルパラメータによって決定されたモデルパラメータを使用することを特徴とする請求項２３に記載のシステム。
【請求項２５】
格納されたプログラムを有するコンピュータ読取り可能記憶媒体であって、前記プログラムは受信した非テキスト情報の階層内容を認識するためのものであり、前記プログラムは、
非テキスト情報を受信するステップと、
未処理特徴情報を判別するステップと、
前記未処理特徴情報から追加の特徴を判別するステップと、
前記受信情報内の各行についてラベルを計算するステップと
を備えることを特徴とするコンピュータ読取り可能記憶媒体。
【請求項２６】
追加の特徴を判別する前記ステップは、
基本行特徴を判別するステップ
をさらに含むことを特徴とする請求項２５に記載のコンピュータ読取り可能記憶媒体。
【請求項２７】
前記プログラムはさらに、
前記受信情報を前処理するステップ
をさらに含むことを特徴とする請求項２５に記載のコンピュータ読取り可能記憶媒体。
【請求項２８】
前記前処理するステップはさらに、
前記受信情報をローテーションするステップ
をさらに含むことを特徴とする請求項２５に記載のコンピュータ読取り可能記憶媒体。
【請求項２９】
前記計算するステップは、コリンズモデルの適用を含むことを特徴とする請求項２５に記載のコンピュータ読取り可能記憶媒体。
【請求項３０】
前記計算するステップは、トレーニングデータによりトレーニングされたコリンズモデルの適用を含むことを特徴とする請求項２５に記載のコンピュータ読取り可能記憶媒体。
【請求項３１】
格納されたプログラムを有するコンピュータ読取り可能記憶媒体であって、前記プログラムは非テキスト情報の階層構造を判別するためのものであり、前記プログラムは、
非テキスト情報を受信するステップと、
非テキスト情報の行を観察シーケンスｓｔとして処理するステップと、
前記ラベルシーケンスのコストが、
【数７】
2006146894.tif 000017
となるように、ラベルｌｔのシーケンスを見つけるために観察シーケンスｓｔを処理するステップであって、
Ｌは時間のラベルのシーケンスであり、ｓは観察のシーケンスであり、ｔはシーケンス内の位置であり、｛ｌｔ｝およびλｉはモデルパラメータであるステップと
を備えることを特徴とするコンピュータ読取り可能記憶媒体。
【請求項３２】
前記モデルパラメータは、前記モデルパラメータをトレーニング例内でラベルに収束するように調整することによって決定されることを特徴とする請求項３１に記載のコンピュータ読取り可能記憶媒体。
【請求項３３】
前記プログラムは、
【数８】
2006146894.tif 000018
となるように重みのセット｛λｉ｝を見つけることにより、トレーニング例｛Ｌｋ、ｓｋ｝を使用してモデルパラメータを決定するステップをさらに備えることを特徴とする請求項３１に記載のコンピュータ読取り可能記憶媒体。
【請求項３４】
各行は多数の特徴を含むように決定され、前記特徴はラベルを前記行に割り当てるために使用されることを特徴とする請求項３１に記載のコンピュータ読取り可能記憶媒体。
【請求項３５】
前記プログラムは、
各行についてのインデントレベルを推定するステップであって、前記インデントレベルは特徴であるステップ
をさらに備えることを特徴とする請求項３４に記載のコンピュータ読取り可能記憶媒体。
【請求項３６】
前記プログラムは、
黒丸が行内に存在するかどうかを判別するステップであって、前記黒丸の存在は特徴であるステップ
をさらに備えることを特徴とする請求項３４に記載のコンピュータ読取り可能記憶媒体。
【請求項３７】
受信情報およびストレージを有するコンピュータシステムにおいて、ディスプレイ上にレンダリングされるユーザインターフェースであって、
構文解析された前記情報を表示する第１の領域と、
前記構文解析された情報の階層レベルを指定するユーザ入力を受信する第２の領域と
を備え、
前記コンピュータシステムは、前記ユーザ入力と構文解析された前記情報との間の関連を格納すること
を特徴とするユーザインターフェース。
【請求項３８】
前記受信情報は非テキスト情報であることを特徴とする請求項３７に記載のユーザインターフェース。
【請求項３９】
前記受信情報は電子インクを含むことを特徴とする請求項３７に記載のユーザインターフェース。
【請求項４０】
前記コンピュータシステムは前記受信情報を構文解析したことを特徴とする請求項３７に記載のユーザインターフェース。
【請求項４１】
前記コンピュータシステムは以前構文解析された前記情報を受信したことを特徴とする請求項３７に記載のユーザインターフェース。
【請求項４２】
前記関連は、他の受信情報を分析するための条件付きランダムフィールドアルゴリズムに対してモデルパラメータをトレーニングするために使用されることを特徴とする請求項３７に記載のユーザインターフェース。
【請求項４３】
前記条件付きランダムフィールドアルゴリズムは、コリンズモデルアルゴリズムを含むことを特徴とする請求項４２に記載のユーザインターフェース。
【請求項４４】
対話する場合に、構文解析された前記情報をナビゲートする第３の領域をさらに備えることを特徴とする請求項３７に記載のユーザインターフェース。
【請求項４５】
対話する場合に、構文解析された前記情報の前記第１の領域内に、少なくとも１つの代替ビューを提供する第３の領域をさらに備えることを特徴とする請求項３７に記載のユーザインターフェース。
【請求項４６】
ユーザ入力を、構文解析された情報に関連付ける方法であって、
情報を受信するステップと、
前記受信した情報の行に関連付けられているユーザ入力を受信するステップと、
前記受信した情報の前記行に前記ユーザ入力を関連付けるステップと、
少なくとも前記関連を格納するステップと
を備えることを特徴とする方法。
【請求項４７】
前記格納された関連は、条件付きランダムフィールドアルゴリズムに対してトレーニング例として使用されることを特徴とする請求項４６に記載の方法。
【請求項４８】
前記条件付きランダムフィールドアルゴリズムは、コリンズモデルアルゴリズムを含むことを特徴とする請求項４７に記載の方法。
【請求項４９】
前記格納するステップは、
ユーザ入力を情報のそれぞれの行にリンクさせる複数の関連を格納するステップをさらに備えることを特徴とする請求項４６に記載の方法。
【請求項５０】
前記受信するステップは、ストレージから情報を受信することを特徴とする請求項４６に記載の方法。
【請求項５１】
前記受信するステップは、ユーザから情報を受信することを特徴とする請求項４６に記載の方法。
【請求項５２】
前記受信するステップは、コンピュータによって生成された情報を受信することを特徴とする請求項４６に記載の方法。
【請求項５３】
前記受信情報を、行に構文解析するステップをさらに備えることを特徴とする請求項４６に記載の方法。
【請求項５４】
前記受信するステップは、以前行に構文解析した情報を受信することを特徴とする請求項４６に記載の方法。
【請求項５５】
ユーザ入力を、構文解析された情報に関連付けるために格納されたプログラムを有するコンピュータ読取り可能記憶媒体であって、前記プログラムは、
情報を受信するステップと、
前記受信情報の行に関連付けられたユーザ入力を受信するステップと、
前記ユーザ入力を、前記受信情報の前記行に関連付けるステップと、
少なくとも前記関連を格納するステップと
を備えることを特徴とするコンピュータ読取り可能記憶媒体。
【請求項５６】
前記格納された関連は、条件付きランダムフィールドアルゴリズムに対してトレーニング例として使用されることを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項５７】
前記条件付きランダムフィールドアルゴリズムは、コリンズモデルアルゴリズムを含むことを特徴とする請求項５６に記載のコンピュータ読取り可能記憶媒体。
【請求項５８】
前記格納するステップは、
ユーザ入力を情報のそれぞれの行にリンクさせる複数の関連を格納するステップ
をさらに備えることを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項５９】
前記受信するステップは、ストレージから情報を受信することを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項６０】
前記受信するステップは、ユーザから情報を受信することを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項６１】
前記受信するステップは、コンピュータによって生成された情報を受信することを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項６２】
前記プログラムは、
前記受信情報を行に構文解析するステップ
をさらに備えることを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項６３】
前記受信するステップは、以前行に構文解析した情報を受信することを特徴とする請求項５５に記載のコンピュータ読取り可能記憶媒体。
【請求項６４】
ユーザ入力を構文解析された情報に関連付けるためのコンピュータであって、
情報を受信する手段と、
前記受信情報の行に関連付けられているユーザ入力を受信する手段と、
前記受信情報の前記行に前記ユーザ入力を関連付ける手段と、
少なくとも前記関連を格納する手段と
を備えることを特徴とするコンピュータ。
【請求項６５】
前記格納された関連は、条件付きランダムフィールドアルゴリズムに対してトレーニング例として使用されることを特徴とする請求項６４に記載のコンピュータ。
【請求項６６】
前記条件付きランダムフィールドアルゴリズムは、コリンズモデルアルゴリズムを含むことを特徴とする請求項６５に記載のコンピュータ。
【請求項６７】
前記格納する手段は、
ユーザ入力を、情報のそれぞれの行にリンクさせる複数の関連を格納する手段
をさらに備えることを特徴とする請求項６４に記載のコンピュータ。
【請求項６８】
前記受信する手段は、ストレージから情報を受信することを特徴とする請求項６４に記載のコンピュータ。
【請求項６９】
前記受信する手段は、ユーザから情報を受信することを特徴とする請求項６４に記載のコンピュータ。
【請求項７０】
前記受信する手段は、コンピュータによって生成された情報を受信することを特徴とする請求項６４に記載のコンピュータ。
【請求項７１】
前記プログラムは、
前記受信情報を行に構文解析する手段
をさらに備えることを特徴とする請求項６４に記載のコンピュータ。
【請求項７２】
前記受信する手段は、以前行に構文解析した情報を受信することを特徴とする請求項６４に記載のコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の態様は一般に、コンピューティングシステムに関する。より具体的には、本発明の態様は、受信された情報から階層リストおよびアウトラインを構文解析する方法に関する。
【背景技術】
【０００２】
人々は、情報をさまざまなフォーマットで記録する。時には、情報はパラグラフに記録される。場合によっては、パラグラフは、アウトライン形式または黒丸付き形式の階層フォーマットで記録される。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
コンピューティングシステムは、人々が情報を記録するフォーマットを認識しようと試みてきた。この手法は、情報を構文解析して、後に使用または変更できるように、その形式を複製しようと試みるコンピュータ認識システムをもたらした。現在のシステムは、受信した情報を要望どおり適切には構文解析しない。多くの場合、受信された情報は不正確に解析され、そのため、結果として得られた階層形式は、望ましい形式を得るためにユーザが編集する必要がある形式の場合、使用できなくなってしまう。
【０００４】
改良された構文解析システムおよび方法が必要とされる。
【課題を解決するための手段】
【０００５】
本発明の態様は、１つまたは複数の前述の問題に対処し、それにより階層情報を確実に構文解析するための方法を提供する。
【０００６】
本発明は、例示的に説明されており、同様の参照番号が同様の要素を示す添付の図に限定されることはない。
【発明を実施するための最良の形態】
【０００７】
本発明の態様は、階層情報を構文解析すること、および認識することに関する。認識を終えると、さまざまな階層レベルを表すために、ラベルを割り当てることができる。その後の処理は、ラベル割り当てに対応して、例えば、階層情報を変更することができる。
【０００８】
本明細書は、読みやすくするために複数の節に分割されている。これらの節は、階層情報、インクの特性、用語、汎用コンピューティング環境、階層情報の構文解析の方法、階層情報の構文解析の例、トレーニング例を含んでいる。
【０００９】
以下の説明において、さまざまな関連付けが要素間に示されることに留意されたい。これらの関連付けは一般に、特に定めのない限り、直接または間接であってもよく、本明細書ではこの点において限定することを意図してはいないことに留意されたい。
【００１０】
（階層情報）
階層情報は、注釈（notes）、概要（outlines）、すべきことのリスト（to-do lists）などを含む、多くの形態をとることができる。本発明の態様は、何らかの階層形式をとるものとして認識されるよう意図された、すべての情報に適用することができる。一部は、例えばタブレットＰＣまたは携帯情報端末（ＰＤＡ）にみられるデジタイジング面によって取り込まれるような、手書きの情報を含んでいる。ユーザが情報を階層形式で取得している場合は、ユーザは構文解析された情報を編集、更新、または他のプログラムにエクスポートすることもできる。ここで、ユーザが大幅な編集を行うことなく情報を使用できるように、情報の階層構造が自動的に決定されることが重要である。
【００１１】
条件付きランダムフィールドは、１−Ｄシーケンスをラベル付けするために使用することができる。本発明の態様は、これらのラベルを階層情報に適用する。特に、本発明の態様は、行のシーケンスに値（例えば｛１、１ｃ、２、２ｃ、．．．｝）を示すラベルを付ける。値は、行間に存在する階層関係を識別する。
【００１２】
本発明は、階層形式に構文解析される、すべての情報に適用できるものであるが、インク構造（ink structures）は階層であることが多い。メモを取る場合、ユーザは通常パラグラフを書き出すが、このパラグラフは行で構成され、行は単語で構成され、単語は文字（またはストローク）で構成されている。この階層構造の知識により、行の挿入、パラグラフ全体の移動、またはパラグラフの余白の変更など、複雑な構造の編集が行えるようになる。文法構造の階層分解へのインクの解釈は、ユーザインターフェースに基づくインクの範囲を構築する際に、関連する場合がある。自然なユーザノートのかなりの割合を占めるのは、リストの形式（買い物リスト、すべきことのリスト、概要など）である。これらのリストの多くは階層であり、しかも複数のレベルを備えている。例えば、「すべきことのリスト」の各項目が、手順または必須事項のリストで構成されることは珍しいことではない。これらの構造の自動解釈は、サブツリーを動的に移動または縮小表示できる改良されたユーザインターフェース、または適切なフォーマット設定による文書作成システムへのインポートをサポートすることができる。
【００１３】
（インクの特性）
インクペンを使用するユーザに知られているように、物理インク（インク筒を備えるペンを使用して紙に書き留められる種類のもの）は、線分によって結ばれた一連の座標よりも、多くの情報を伝達することができる。例えば、物理インクは、（インクの濃さによって）ペン筆圧、（直線または曲線の形状、および離散点の周囲のインクの作用によって）ペン角度、および（直角度、線幅、直線または曲線の経路にわたる線幅の変化によって）ペンのペン先の速度を反映することができる。さらにもう１つの例としては、インクが置かれた紙または他の表面の繊維に吸収される方法が含まれる。これらの微妙な特性もまた、上記であげた属性を伝達する際に役立つ。これらの追加の属性により、点間の均一な線幅よりも感情、個性、強調などをより瞬時に伝達できるようになる。
【００１４】
電子インク（またはインク）は、ユーザがスタイラスベースの入力装置を使用する場合に取り込まれる、電子情報の取り込みおよび表示に関連する。電子インクとは、ストロークのシーケンスまたは任意の集合を示し、各ストロークは一連の点で構成される。ストロークは、同時に描かれるかまたは収集されることも、または独自の時と場所および独自の理由により描かれるかまたは収集されることもある。点は、直交座標（Ｘ、Ｙ）、極座標（ｒ、θ）を含むさまざまな既知の技法、および当技術分野で既知の他の技法を使用して表すことができる。電子インクは、筆圧、角度、速度、色、スタイラスサイズ、およびインク不透明度を含む、実際のインクの属性の表示を含むことができる。電子インクはさらに、情報の中でも特に、ページ上にインクが置かれる順序（ほとんどの西洋語における左から右そして下へのラスターパターン）、タイムスタンプ（インクが置かれた時間を示す）、インクの筆者の指示、および作成装置（originating device）（インクが描かれたマシンの識別またはインクを配置するために使用されたペンの識別のうち少なくとも１つ）を含む、他の属性を含むことができる。
【００１５】
前述の特性の中で、一連の座標であるストロークの時間的な順序が、主として使用される。同様に、すべてのこれらの特性を使用することもできる。
【００１６】
【表１】
2006146894.tif 000003
【００１７】
（汎用コンピューティング環境）
図１は、本発明を実装できる適切なコンピューティングシステム環境１００の実装例を示している。コンピューティングシステム環境１００は、適切なコンピューティング環境の一例に過ぎず、本発明の使用の範囲または機能にいかなる制限を提示することも意図するものではない。さらに、コンピューティング環境１００は、例示的なオペレーティング環境１００において示された、１つのコンポーネントまたはその組み合わせに関して、いかなる依存関係または要件も有するものと解釈すべきではない。
【００１８】
本発明は、数多くの他の一般的用途または特殊用途のコンピューティングシステム環境または構成により動作可能である。本発明と共に使用するために最適な既知のコンピューティングシステム、環境、および／または構成の例としては、パーソナルコンピュータ、サーバーコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたは装置のいずれかを含む分散コンピューティング環境などがあげられるが、これらに限定されることはない。
【００１９】
本発明は、コンピュータによって実行されるプログラムモジュールなど、コンピュータ実行可能命令の一般的文脈に即して説明することができる。一般に、プログラムモジュールには、特定のタスクを実行するかまたは特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。本発明はさらに、タスクが通信ネットワークを通じてリンクされたリモート処理装置によって実行される、分散コンピューティング環境においても実施することができる。分散コンピューティング環境において、プログラムモジュールは、メモリ記憶装置を含むローカルおよびリモートのコンピュータストレージ媒体に配置される。
【００２０】
図１を参照すると、本発明を実装するための例示的なシステムは、コンピュータ１１０の形態をとる汎用コンピュータ装置を含んでいる。コンピュータ１１０のコンポーネントは、処理装置１２０、システムメモリ１３０、およびシステムメモリを含むさまざまなシステムコンポーネントを処理装置１２０に接続するシステムバス１２１を含むことができる。システムバス１２１は、メモリバスまたはメモリコントローラ、ペリフェラルバス、およびさまざまなバスアーキテクチャのいずれかを使用するローカルバスを含む、任意のタイプのバス構造であってもよい。限定ではなく例として、そのようなアーキテクチャには、ＩＳＡ（業界標準アーキテクチャ）バス、ＭＣＡ（マイクロチャネルアーキテクチャ）バス、ＥＩＳＡ（Enhanced ISA）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカルバス、およびメザニンバスとも呼ばれるＰＣＩ（Peripheral Component Interconnect）バスが含まれている。
【００２１】
コンピュータ１１０は通常、各種のコンピュータ読取り可能記憶媒体を含んでいる。コンピュータ読取り可能記憶媒体は、コンピュータ１１０がアクセスでき、揮発性および不揮発性記憶媒体、取外し可能および取外し可能な記憶媒体を含む任意の使用可能な記憶媒体であってもよい。一例として、コンピュータ読取り可能記憶媒体は、コンピュータ記憶媒体および通信媒体を備えることができるが、これらに限定されることはない。コンピュータ記憶媒体は、コンピュータ読取り可能命令、データ構造、プログラムモジュールおよびその他のデータなどの、情報の記憶のための任意の方法または技術において実装された揮発性および不揮発性の、取外し可能および取外し不可能な記憶媒体を含んでいる。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（デジタル多用途ディスク）またはその他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶装置、あるいは所望の情報を格納するために使用することができ、コンピュータ１１０によってアクセスすることができる他の媒体を含んでいるが、これらに限定されることはない。通信媒体は通常、コンピュータ読取り可能命令、データ構造、プログラムモジュール、またはその他のデータを、搬送波または搬送メカニズムのような被変調データ信号で組み入れ、任意の情報伝達媒体を含んでいる。「被変調データ信号」という用語は、１つまたは複数の特性セットを備える信号、または信号の情報を符号化するような方法で変更された信号を意味する。例えば、通信媒体は、有線ネットワークまたは直接配線接続のような有線媒体、および音響、無線周波数（ＲＦ）、赤外線など無線媒体を含んでいるが、これらに限定されることはない。上記の任意の組み合わせも、コンピュータ読取り可能記憶媒体の範囲に含まれる。
【００２２】
システムメモリ１３０は、読み取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２のような揮発性メモリおよび／または不揮発性メモリの形態でコンピュータ記憶媒体を含んでいる。起動時などにコンピュータ１１０内の構成要素間の情報の転送を支援する基本ルーチンを含むＢＩＯＳ（基本入出力システム）１３３は通常、ＲＯＭ１３１に格納される。ＲＡＭ１３２は通常、処理装置１２０によって即時アクセス可能および／または現在操作中のデータおよび／またはプログラムモジュールを含んでいる。限定ではなく例として、図１では、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７を示している。
【００２３】
コンピュータ１１０は、他の取外し可能／取外し不可能、揮発性／不揮発性のコンピュータ記憶媒体を含むこともできる。単なる一例として、図１では、取外し不可能な不揮発性磁気記憶媒体との間の読み取りまたは書き込みを行うハードディスクドライブ１４１、取外し可能な不揮発性磁気ディスク１５２との間の読み取りまたは書き込みを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭその他の光媒体などの取外し可能な不揮発性光ディスク１５６との間の読み取りまたは書き込みを行う光ディスクドライブ１５５を示している。例示的なオペレーティング環境において使用することができる他の取外し可能／取外し不可能、揮発性／不揮発性コンピュータ記憶媒体は、磁気テープカセット、フラッシュメモリカード、ＤＶＤ（デジタル多用途ディスク）、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどを含むが、これらに限定されることはない。ハードディスクドライブ１４１は通常、インターフェース１４０などの取外し不可能なメモリインターフェースを通じてシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は通常、インターフェース１５０などの取外し可能なメモリインターフェースによってシステムバス１２１に接続される。
【００２４】
図１に示されている前述のドライブおよびその関連するコンピュータ記憶媒体は、コンピュータ１１０についてのコンピュータ読取り可能命令、データ構造、プログラムモジュール、およびその他のデータの記憶領域を提供する。例えば、図１において、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するように示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７と同じものにすることも、または異なるものにすることもできることに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７は、少なくともそれらが異なるコピーであることを示すために、本明細書において異なる番号を付けてある。ユーザは、キーボード１６２および一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティングデバイス１６１などの入力装置を介してコンピュータ２０にコマンドおよび情報を入力することができる。その他の入力装置（図示せず）としては、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送用パラボラアンテナ、スキャナなどを含むことができる。上記およびその他の入力装置は、システムバスに接続されているユーザ入力インターフェース１６０を介して処理装置１２０に接続されることが多いが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）など他のインターフェースおよびバス構造によって接続することもできる。モニタ１９１またはその他の種類の表示装置も、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続することができる。モニタに加えて、コンピュータは、出力周辺インターフェース１９５を介して接続できるスピーカ１９７およびプリンタ１９６などの他の周辺出力装置を含むこともできる。
【００２５】
コンピュータ１１０は、リモートコンピュータ１８０など、１つまたは複数のリモートコンピュータへの論理接続を使用するネットワーク化された環境において動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバー、ルーター、ネットワークＰＣ、ピアデバイスまたはその他の一般的なネットワークノードであってもよく、通常は上記でパーソナルコンピュータ１１０に関連して説明されている要素の多くまたはすべてを含んでいるが、図１においては記憶装置１８１のみが示されている。図１に示されている論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含んでいるが、他のネットワークを含むこともできる。そのようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットで一般的である。
【００２６】
ＬＡＮネットワーク環境において使用される場合、コンピュータ１１０はネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境に使用される場合、コンピュータ１１０は通常、モデム１７２またはインターネットなどのＷＡＮ１７３にわたる通信を確立するための他の手段を含んでいる。モデム１７２は、内蔵または外付けであってもよく、ユーザ入力インターフェース１６０または他の適切な機構を介して、システムバス１２１に接続することができる。ネットワーク化された環境において、コンピュータ１１０に関連して示されるプログラムモジュール、またはその部分は、リモート記憶装置に格納することもできる。限定ではなく例として、図１では、リモートアプリケーションプログラム１８５を記憶装置１８１に常駐するものとして示している。示されているネットワーク接続が例示的なものであり、コンピュータ間の通信リンクを確立する他の手段も使用できることを理解されたい。
【００２７】
一部の態様において、ペンデジタイザ１６５および付属のペンまたはスタイラス１６６が、フリーハンド入力をデジタル処理で取り込むために提供される。ペンデジタイザ１６５とユーザ入力インターフェース１６０間の直接接続が示されているが、実際には、ペンデジタイザ１６５は、無線を含む任意の技法により、直接、処理装置１１０、パラレルポートまたは他のインターフェース、およびシステムバス１３０に接続することができる。さらに、ペン１６６は、ペン１６６に関連するカメラ、およびカメラによって取り込まれた画像情報をバス１２１を用いて対話するインターフェースに無線で送信するための送受信機を備えることができる。さらに、ペンは、電子インクのストロークを決定するために、カメラに加えて、あるいはカメラの代わりに、加速度計、磁力計、およびジャイロスコープを含む他の検出システムを備えることができる。
【００２８】
示されているネットワーク接続が例示的なものであり、コンピュータ間の通信リンクを確立するための他の技法も使用できることを理解されたい。ＴＣＰ／ＩＰ、イーサネット（登録商標）、ＦＴＰ、ＨＴＴＰなどのさまざまな既知のプロトコルの存在が想定され、システムは、ユーザがＷｅｂベースのサーバーからＷｅｂページを取り出せるように、クライアントサーバー構成において動作することができる。さまざまな従来のＷｅｂブラウザのいずれを使用しても、Ｗｅｂページ上でデータを表示し、操作することができる。
【００２９】
図２は、本発明のさまざまな態様に従って使用できる例示的タブレットＰＣ２０１を示す図である。図１のシステムにおける任意またはすべての特徴、サブシステム、および機能は、図２のコンピュータに含めることができる。タブレットＰＣ２０１は、例えば、好ましくは液晶ディスプレイ（ＬＣＤ）画面であるデジタイジングフラットパネルディスプレイなど、複数のウィンドウ２０３が表示される大型表示面２０２を含んでいる。スタイラス２０４を使用して、ユーザは、デジタイジング表示面２０２上で選択、強調表示、および／または書き込みを行うことができる。適切なデジタイジング表示面２０２の例には、ＭｕｔｏｈまたはＷａｃｏｍのペンデジタイザなど、電磁ペンデジタイザが含まれる。例えば光デジタイザなど、他のタイプのペンデジタイザを使用することもできる。タブレットＰＣ２０１は、データの操作、テキストの入力、図面の作成、および／またはスプレッドシート、ワード処理プログラムなどの標準的なコンピュータアプリケーションタスクの実行のために、スタイラス２０４を使用して行われたジェスチャを解釈する。
【００３０】
スタイラス２０４は、その選択能力を高めるために、１つまたは複数のボタンまたは他の機能を備えることができる。一実施形態において、スタイラス２０４は、一方の端部が書き込み部分を構成し、もう一方の端部が、ディスプレイ上を移動するとディスプレイの指示部分が消去される「消しゴム」端部を構成する、「ペンシル」または「ペン」として実装することができる。マウス、トラックボールなどのその他のタイプの入力装置も、使用することができる。さらに、ユーザ自身の指をスタイラス２０４にして、タッチセンシティブディスプレイまたは近接センシティブディスプレイ上で表示された画像の部分を選択または指示するために使用することができる。したがって、本明細書で使用されている「ユーザ入力装置」という用語は、幅広い定義を有することを意図し、スタイラス２０４のような既知の入力装置の数多くの変種を包含する。部位２０５は、ユーザが、表示面２０２に接触したスタイラス２０４の位置を判別できるようにする、フィードバック部位または接触部位を示している。
【００３１】
さまざまな実施形態において、システムは、アプリケーションがインクを取り込み、操作し、格納するために使用できる、ＣＯＭ（コンポーネントオブジェクトモデル）サービスのセットとしてインクプラットフォームを提供する。あるサービスにより、アプリケーションは、開示されたインクの表現を使用してインクを読み取り、書き込むことができる。インクプラットフォームはさらに、拡張マークアップ言語（ＸＭＬ）のような言語を含む、マークアップ言語も含むことができる。さらに、システムは、もう１つの実施態様としてＤＣＯＭを使用することができる。さらに他の実施形態では、Ｍｉｃｒｏｓｏｆｔ  ＣｏｒｐｏｒａｔｉｏｎのＷｉｎ３２プログラミングモデル、および．Ｎｅｔプログラミングモデルを含めて使用することができる。
【００３２】
（階層情報を構文解析するための方法）
図３から図５は、階層情報を構文解析することについてのさまざまな例を示している。図３において、階層情報は、それぞれお互いに分離していると見なされる行ごとに構文解析される。階層情報を見ているユーザは、アウトライン形式で表示される情報を書き留めることができるが、図３のパーサーは、各行３０１を別々にしか識別していない。このタイプの構文解析は、解析された内容を再利用するには不利である。ユーザは、ある行から次の行へ折り返される情報を瞬時に認識することができるが、パーサーは、各行が別個のパラグラフであると確信している。別個の行は、新たな行の折り返しが新しい行を作り出し、既存の行を再フォーマットすることはないので、変更または別の目的を持たせること（例えば、テキストに変換すること）を困難にする。
【００３３】
図４において、本実施例の構文解析システムは、行を、同じ階層レベルを有するグループ（例えば、グループ４０１、４０２、および４０４）に識別した。しかし、構文解析システムは、セクション４０１、４０２、および４０４の階層に関連するセクション４０３の内容を識別しなかった。ユーザは、セクション４０３の行がセクションの階層にどのように適合するかを容易に知ることができるが、図４のパーサーは、左インデントのない行をグループ分けしただけであった。左インデントのある行（グループ４０３内にある行）は、別個のものであり、グループ４０１、４０２、および４０４の階層の一部ではないと見なされる。
【００３４】
図５において、構文解析システムは、階層内の他の行に関連するものとして、各行を識別した。図５は、合計１８行を示し、そこには、各ノードが独立したパラグラフになっている、７つのノードがある。パラグラフの開始行は、行５０１、５０４、５０９、５１０、５１１、５１２、および５１４（これらの行は整数の識別子｛０、１、２、３、．．．Ｎ｝も含んでいる）である。残りの行は、後に「ｃ」を付けた前行の整数によって表される継続行である。もちろん、任意の他の識別方式も使用することができる。ここで、ラベル付け方式は、階層情報がどのように識別されるかを読み手に示すために使用される。
【００３５】
すべての階層情報は、ルートノードを含んでいる。その他のノードは、情報の階層的特質を表すツリーを形成する。ここで、ツリーの他のノードは、テキストのブロックを含み、複数の子を有することができる。アウトラインツリーのレンダリングは、図５に示されるように、観察されるテキストに何らかの複雑さを加える。各ノードには、黒丸、おそらくは記号、番号、文字、またはその組み合わせの何らかの形式が前に付く場合も、そうでない場合もある。ツリー内のノードの深さは、黒丸の選択およびノード内のテキストのフォーマット設定を決定する。ツリー内のより深いノードは通常、左余白からさらにインデントされる。さらに、単一行に収まらない長いテキストブロックは、折り返されて「継続」行を形成する。継続行は、黒丸付きではなく、最初の黒丸付き行とは異なる左インデントを持つ場合もある。同じアウトライン構造をレンダリングする多くの可能な方法があることを強調するのは重要である。ユーザは、さまざまなタイプの黒丸、またはさまざまなインデント方式を選択することができる。
【００３６】
実際の黒丸のセットは非常に大きく、ダッシュ、星、またはドットなどの記号、１、２、３、またはｉ、ｉｉ、ｉｉｉなどの数字、Ａ、Ｂ、ａ、ｂ、またはｃなどの文字、あるいは組み合わせ、または代替を含むことができる。黒丸タイプは各々、丸括弧、ピリオド、またはコロンなどの装飾を含む場合もある。場合によっては、リスト項目は全くラベルを持たない。
【００３７】
図６は、受信した情報を階層構造に構文解析するための方法を示している。いったん構造が決定されると、情報は他のアプリケーションおよび／またはユーザによって操作することができる。情報は、ステップ６０１において受け取られる。ステップ６０２において、受信した情報は、情報の行内におけるローテーションに合わせて調整するために、ローテーションする（rotate）ことができる。さらに、システムは、受信した情報およびセグメント内にグラフィック要素が存在するかどうか判別することができ、グラフィック要素であると想定される情報を除去する。受信した情報がインクである場合、ストロークはすでに単語および行にグループ化されていると想定される。次にシステムは、行をブロックにグループ化する。最後に、注釈（annotations）はセグメント化され、除去される。
【００３８】
ステップ６０３から６０６は、観察された情報の行から階層ツリー構造を決定することに関する。以下では、追加の例にラベル付けするために必要な、キー規則性（key regularities）に関する例のトレーニングセットからトレーニングされた、学習アプローチについて説明する。
【００３９】
２つの観察（observations）は、アウトライン構造の推定をさらに簡単にする。第１の観察は、各ブロック内の行がページ上で上部から下部へと自然に順序付けられており、ツリー内のノードが一次の同じ深さを有することである。第２の観察は、各行にラベルを割り当てることによって階層構造が効率的にエンコードできることである。ラベルは、ツリー内のノードの深さ、および行が直前の行の継続であるかどうかをエンコードする（図５を参照）。これら２つの観察を考慮し、アウトラインツリーの推定は、行分類問題として達成することができ、ここで各行はＮの深さの１つに、継続または非継続として分類される。各行についての分類から、ツリー構造は１回のパス（pass）で計算することができる。次いで問題は、各行をどのように分類するかである。
【００４０】
テキストの各ブロック内の行は、コリンズによって導入されたマルコフモデリングフレームワークを使用してラベル付けされる。これを本明細書ではコリンズモデルと呼ぶ。コリンズモデルは、隠れマルコフモデルのさらに強力な一般化である。隠れマルコフモデルと同様に、コリンズモデルのパラメータは、トレーニングデータのセットを使用して推定される。
【００４１】
前述のように、コリンズモデルは、インクを階層形式に構文解析するために使用することができる。また、他のモデルを使用することもできる。例として、代替モデルは、その行のみから計算された特徴に基づいて各行を分類することである。以下の例を使用して、複数の特徴を各行について計算することができる。例には、「左インデント」、「右インデント」、「直前行に対しての左インデント」、「黒丸あり」などが含まれる。これらの特徴を使用して、行の深さおよび継続を正しく分類する機能を学習するよう試みることができる。行どうしが独立しているため、この単純な方式には、行にラベル付けをする際に困難な問題がある。文脈が非常に重要であるからである。１つの単純拡大は、「スタッキング」と呼ばれる。この場合、現在行の特徴および周囲行の特徴が、各行についての分類子（classifier）への入力として使用される（特徴は単一の入力ベクトルに「スタック」される）。このことはパフォーマンスを向上させるが、ラベル間の依存関係はモデル化されない。
【００４２】
さらに強力なモデルは、入力の特徴をスタックし、ラベルの依存関係を伝搬するものである。隠れマルコフモデルはこの方法に適しているが、ある技術上の前提に反している、つまり、ある技術上の前提は、隠れ状態を与えられた観察の独立性である。入力の特徴はスタックされるので、同じ特徴値が異なる入力時に対して何度も発生する。これは、隠れマルコフモデル（hidden Markov model）に必要とされている独立性の重大な違反である。コリンズモデルは、これらの問題の一部に対処する。使用できる他の手法には、条件付きランダムフィールド（Conditional Random Fields）、および他の非生成（non-generative）マルコフプロセスが含まれる。
【００４３】
コリンズモデルおよび関連モデルは、この説明の範囲を超えている。モデルの動作およびトレーニングの理解に関連する詳細についてのみ説明する。
【００４４】
モデルは、以下のように機能する。観察のシーケンスｓｔを所与として、ラベルのシーケンスｌｔが要求される。コリンズモデルでは、特徴のセットｆｉ（ｌ’、ｌ”、ｓ、ｔ）を使用し、これはラベルのペア、観察のシーケンスｓ、および時間（またはシーケンス内の位置）のバイナリ関数である。ラベルシーケンスのコストは、以下のように定義される。
【００４５】
【数１】
2006146894.tif 000004
【００４６】
ここでＬは、時間｛ｌｔ｝内のラベルのシーケンスであり、λｉはモデルパラメータである。多くのラベル付きトレーニング例｛Ｌｋ、ｓｋ｝を考慮して、学習プロセスは重みのセット｛λｉ｝を以下のように見つけようと試みる。
【００４７】
【数２】
2006146894.tif 000005
【００４８】
各特徴は、隣接状態のペアにしか依存しないことに留意されたい。もちろん、これは、追加の状態を含めるように変更することができる。
【００４９】
その結果、合計からの条件を、独立したグループに分割することができる。このことは、動的プログラミングを使用して効率的な最小化を導く（アルゴリズムは、基本的にＨＭＭ（Hidden Markov Model）のビタビ復号（Viterbi decoding）と同等である）。上記で表される特徴は抽象的形態をとり、これは、その動作に多くの直観を提供しない。
【００５０】
目的および特徴の意味についてより深い理解をもたらすために、いくつかの例を検討することが有益である。観察および時間を共に無視する、特徴の特定の形態を検討することもできる。これらは、ｆｉ｛ｌｔ、ｌｔ−１｝と書き換えることもできる。ある特定の特徴、例えばｆＴ１４は、ｌｔ−１＝１かつｌｔ＝４である場合に値１を返し、それ以外の場合は０を返す（つまり、状態は深さ１の行から深さ４に推移した）。この推移は、アウトラインツリーの性質により不可能である。モデルが、不可能なラベルを出力することがないようにするため、学習プロセスは、対応する重みλＴ１４に非常に大きい正の値を割り当てることができる。その結果、この推移を含む仮説の（hypothetical）ラベルシーケンスには、高いコストが割り当てられる。逆に、ｆＴ１２（深さ１から２への推移をテストする）は頻繁に発生し、負の重みまたは小さい正の重みを割り当てることもできる。
【００５１】
他のタイプの特徴は、特定の状態を促進するために使用することができる。例えば、現在の状態が１であり現在行の左インデントが２０ミリメートル未満である場合、仮説の特徴ｆｓ１＿ｉｎｄｅｎｔ＜２０は１を返す。これはかなり頻繁に発生するものであり、これには負の重みを割り当てるべきである。特徴ｆｓ１＿ｉｎｄｅｎｔ＞５００は、まれにしか発生しないものであり、大きい正の重みを割り当てるべきである。
【００５２】
最も複雑なタイプの特徴は、観察の一部の属性が与えられた、２つのラベルに関連する。例えば、現在および直前のラベルが共に１であり、行間の相対インデントが２０ミリメートル未満である場合、ｆＴ１＿ｒｅｌｉｎｄｅｎｔ＜２０は１を返す。これもまた頻繁に発生するものであり、これには負の重みを割り当てるべきである。
【００５３】
もちろん、いずれの重みも手作業によって割り当てられる。特徴の大規模なセットおよび例の大規模なセットを所与として、コリンズモデルは、重みベクトルを収束まで徐々に調整することによって反復してトレーニングされる。
【００５４】
行の特徴を抽出することについて以下で説明する。特徴抽出器（feature extractor）への入力は、類似した配向であるが他の場合には任意の方向である、正しくグループ化された行のブロックである。第１の前処理ステップは、行回転角度を計算して、ブロック座標を定義することである。次に、回転角度を補正し、すべての行が水平かつ垂直であると想定して続行することができる。
【００５５】
本発明の態様は、最初に基本行特徴のセットを定義する。これらの基本行特徴は、未処理特徴と呼ぶことができる。未処理特徴には、左、右、上部および下部行境界、インデントレベル、および黒丸タイプが含まれる。行境界を計算することは、容易である（ただし、インク行がまっすぐではなく、アセンダおよびディセンダが非常に不ぞろいな可能性もあるため、上部および下部境界を計算する際には注意が必要である）。インデントレベル推定および黒丸検出の手順については、以下で説明する。
【００５６】
インデントレベル推定：インデントレベルは、量子化された左インデントである。インデントの長さは例ごとに大きく異なる場合があるが、インデントレベルは比較的安定しており、アウトラインの深さにおおむね対応している（図８から図１０を参照）。インデントレベル推定についての動機付けは、深さのおおよその測定を提供することである。この量子化の問題には、任意の標準的な方法を適用することができる。Ｋ平均法アルゴリズムを使用することもできる。Ｋ平均法アルゴリズムは、クラスタ重心の等距離配列で始まり、観察を最も近い重心に割り当て、新しい要素で重心を更新し、重心が変化しなくなるまで反復する。同じレベルのインデントの長さが徐々にページの下方にずれてゆくことは、インクノートにおいて観察されることが多い。そのような場合、絶対インデントを直接量子化することで、擬似検出において実際のレベルを覆い隠すこともできる。
【００５７】
この問題を多少なりとも解決するため、２つのパスで量子化を実行することができる。第１のパスにおいて、相対インデントを量子化し、ゼロの相対インデントを有する近隣行をグループ化することができる。第２のパスにおいて、行グループの平均絶対インデントを量子化することができる。あるいは、量子化を全く実行しないこともできる。
【００５８】
黒丸の検出：インクノートにおいて、リストは非常に一般的な構造である。黒丸はリスト項目（パラグラフ）の開始を知らせ、その存在はアウトラインのラベル付けの不確実性を大幅に軽減することができる。以下で、記号および記号装飾パターンの小規模なセットを認識し、検出の信頼性を高めるために黒丸間の整合性を活用する、ルールベースの黒丸検出器（bullet detector）について説明する。アルゴリズムは、４つのステップで構成される。第１に、各行に対して、行の始めにおいてストローククラスタからいくつかの黒丸候補を生成することができる。第２に、各候補に対して、特徴（幅、高さ、縦横比、他の行との空間および時間距離など）を計算し、それを「ダッシュ」または「丸括弧で終わる」（例えば「１．ａ）」）などのタイプの１つとして認識しようと試み、それに候補が黒丸である確信度を示す［０、１］のスコアを割り当てる。第３に、それらの間の類似度を示す候補の各ペアに対して［０、１］のスコアが計算される。各候補の最終スコアは、その自己スコアおよびそのすべてのペアスコアの加重和であり、候補が既知の黒丸タイプに類似するほど、およびそれに似ている他の候補の数が多くなればそれに応じて、この候補が実際の黒丸である可能性はより高くなるということを反映している。次に、すべての候補が処理されるか、または最高スコアが特定の値を下回るまで、候補を受け入れて、最高信頼性優先の方式で（in a highest-confidence-first fashion）その競合する候補のすべてを削除することができる。予備試験の結果は、この方法が、ダッシュ、ドット、英数字とドットの組み合わせ、および未知のタイプの黒丸などの、一般的なインク黒丸を検出する場合に効果的であることを示した。それが計算する特徴はさらに、学習ベースの黒丸認識にも活用することができる。
【００５９】
基本行の特徴について以下で説明する。以下の表は、テスト結果を生成するために使用できる基本行の特徴を示している。特徴は、０（＝Δｔは行ｔの未処理特徴のみが使用されることを意味する）、１（＝Δｔは前または次の近隣の未処理特徴も使用されることを意味する）というように、どれほど多くのコンテキストΔｔがその計算で使用されるかに応じて、３つのカテゴリに分類される。長さの特徴は、ブロック内の平均行高さなど、さまざまなグローバル統計によって正規化することができる。
【００６０】
【表２】
2006146894.tif 000006
【００６１】
【表３】
2006146894.tif 000007
【００６２】
【表４】
2006146894.tif 000008
【００６３】
各表について、正規化方式は次のものを含むことができる。正規化方式：０−正規化されず、１−平均行高さによる、２−最小行間距離による、３−中央行間距離による。特徴についてのすべてのリストされた方式が使用される。
【００６４】
未処理／派生の特徴を組み合わせる有意義な方法は数多くあり、表１で列挙しているのはほんの一部に過ぎないことは明らかである。さらに多くの特徴を手作業で処理する代わりに、以下ではこの問題に対して系統的な手法をとる。
【００６５】
基本特徴をコリンズモデル特徴と組み合わせる方法について以下で説明する。コリンズモデルでは、ｆｉ（ｌ’、ｌ”、ｓ、ｔ）の形式の特徴を必要とし、これは現在の状態（または状態のペア）および観察シーケンスの両方に依存することを思い出していただきたい。特徴は、トレーニングセットを使用して基本特徴から形成される。
【００６６】
組み合わせフィルタ。手作業で構築したフィルタの初期セットに基づいて、組み合わせフィルタのセットが構築される。各々が、手作業で構築されたフィルタのランダムサブセットのランダムな一次組み合わせを計算する。
【００６７】
バイナリ特徴。各継続値の特徴に対する平均および分散は、トレーニングセットから推定される。次に範囲は、幅が標準偏差１の６つのビンに分割される。合計６つのバイナリ特徴が各継続特徴から作成される。バイナリ特徴は、継続特徴が対応するビンに入る場合には値１をとり、それ以外の場合にはゼロをとる。
【００６８】
観察特徴。１つの特徴が、各三つの組み｛ｓ、ｉ、ｖ｝に対して生成される。特徴は、現在の状態がｓであり、バイナリ特徴がｉ＝ｖである場合に１を返す。トレーニングセット内の一部の例に対して１を返す特徴のみが保持される。
【００６９】
推移特徴。１つの特徴が、各四つの組み｛ｓ、ｓ’、ｉ、ｖ｝に対して生成される。特徴は、現在の状態がｓであり、前の状態がｓ’であり、バイナリ特徴がｉ＝ｖである場合に１を返す。トレーニングセット内の一部の例に対して１を返す特徴のみが保持される。
【００７０】
（階層情報の構文解析の例）
以下に、ＴａｂｌｅｔＰＣのＷｉｎｄｏｗｓ（登録商標）  Ｊｏｕｒｎａｌ（Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎ）で作成された５２２のインクファイルの集合による実験データの結果を示す。これらのすべてのファイルは、興味深いアウトライン構造を示す相当量の手書き筆記体活字を含んでいる。このセットからのブロック内の行の中央値および最大数は、それぞれ１５および６６である。各アウトラインブロック内のストロークは、単語および行に正しくグループ化されている。各行は、その深さを示すラベルが付けられ、これが継続である場合、タイトル行は０または０ｃとラベル付けされ、残りの行は１、１ｃ、２、２ｃというようにラベル付けされる。図８から図１２において、５つの例が示されている。
【００７１】
各行に対するグラウンドトゥルースラベル（ground truth label）は、各ラベルにおいて唯一または最初の値として示される。テーブルは、トレーニング用に３７１、評価用に７５（反復回数とともに精度が向上するかどうか観察）、および最終テスト用に７６という、おおむね５：１：１の比率による３つのセットに分割することができる。学習率０．２、減少率０．９、および反復回数１０のパラメータは、トレーニングにおいて使用される。コリンズモデルによって使用されるフィルタの合計数は６０５８であるが、この合計数には５７の未処理行特徴、２２８の「スタックされた」フィルタ、１１３５の２値化されたフィルタが含まれる。残りのフィルタは、観察と推移の間で同等に分割される。すべての実験は、２ＧＢのＲＡＭを備えるＩｎｔｅｌ  ３ＧＨｚのＰＣ上で行われた。トレーニングは、４４６例に対して約２８分を要する。デコーディングは高速で、最大ファイル（６６行）に対して０．９秒を要する。トレーニングおよびデコーディングプログラムのいずれも速度について最適化されておらず、いずれのパラメータも微調整されていない。
【００７２】
アウトラインラベルの推定は、１つの側面は深さでありもう１つは継続状態である、２つのコンポーネントの分類問題として考慮することができる。継続の側面のみが考慮される場合、問題はパラグラフセグメンテーション、つまり１（パラグラフ開始）または１ｃ（パラグラフ継続）として各行にラベル付けすることに帰着する。パラグラフを見つけることはそれ自体が重要な問題であり、パラグラフ特徴はアウトライン分類に非常に有用になる可能性があるため、パラグラフセグメンテーションは最初に実行される。良好なパラグラフセグメンテーション結果が使用可能であれば、「リスト項目の行継続であるか」（上記の表１）のようなアウトライン特徴は、さらにいっそう確実に計算することができる。さらに、アウトラインラベルのセット｛０、０ｃ、１、１ｃ、２、２ｃ、．．．｝に何らかの相関が存在する、つまり３ｃの行は３の行の後に続くので３ｃとなるが、それ以外については他の継続クラスと大きな相異はない。そのような相関は、アウトライン分類の結果に、ある程度のあいまいさをもたらす。パラグラフセグメンテーションの結果は相関によって影響を受けることはなく、それらをアウトライン分類に組み込むことで、あいまいさを軽減するのに役立つ。
【００７３】
最後に、アウトライン推定と比較すると、パラグラフセグメンテーションはアルゴリズムのフレームワークにさらに適したテストベッドである。ラベル付けのあいまいさがはるかに少なく、クラスの数に関連してより多くのデータがあるので、結果がより忠実にアルゴリズムのパフォーマンスを表すからである。
【００７４】
パラグラフセグメンテーションについて以下で説明する。アウトライン分類コードは、｛０、０ｃ、１、１ｃ、２、２ｃ、．．．｝から｛１、１ｃ｝にグラウンドトゥルースラベルをマッピングした後、パラグラフセグメンテーションに直接作用することができる。分類を誤った行の割合によって、各例のエラーを測定することができる。表２にエラー統計の３つのタイプがまとめられている。図７は、１５１の評価およびテスト例について格納されたエラーのプロットである。曲線は、終わりに近づくにつれて急激な上昇をみせている以外は、低く平坦であり、非常に小規模な事例の集合に注目すると、注釈およびエラーの大多数において、アルゴリズムが良好に機能することを意味している。
【００７５】
【表５】
2006146894.tif 000009
【００７６】
失敗事例を調べると、３つの要因がエラーの主要原因として明らかになった。第１は、黒丸検出エラーである。図９における唯一の誤分類は、矢印黒丸が認識されなかったためである。第２の原因は、アウトライン構造とページの残りの部分の間の相互関係を、現在システムが考慮しないことである。図１０における中央セクション周辺のエラーは、主に（破線多角形内の）グラフィックストロークの除去および横の注釈が原因である。第３の原因は、十分に認識されないあいまいさである。この技法は主として幾何学的特徴に依存し、注意深く内容を読み込むことなくインクノートを拾い読みする場合と同様に行うことができるだけである。例えば、図８はエラーのない例を示している。一見して、結果は正しく見える。しかし、文章を読むと、第５行および第６行が実際には１とラベル付けされなければいけないことが明らかになる。そのようなあいまいな事例は、ラベル付けすることも推定することも難しい。特徴を詳細化してさらに多くのトレーニングデータを収集することは、事例の一部のあいまいさをなくす上で役立つ。
【００７７】
潜在的にエラーパターンを、構文解析の精度および端と端をつなぐインキングエクスペリエンスを向上するために、ＵＩ設計およびユーザ適応に組み入れることもできる。図７は、評価に対する分類されたエラーおよびテスト例の関係を示す図である。８２％（１５１のうち１２４）の例は、誤分類された行が２０％以下である。
【００７８】
アウトラインのラベル付けについて以下で説明する。最初にパラグラフセグメンテーションアルゴリズムを実行することにより、一部のパラグラフ特徴をアウトラインのラベル付けシステムに追加することができ（表１）、その後同じトレーニングおよびデコーディングプログラムが適用される。含めることのできる１つの基本パラグラフ特徴は、「この行はパラグラフ開始であるか」である。この場合もやはり、エラーは、分類を誤った行の割合によって各例について測定することができ、表３のエラー統計を報告する。
【００７９】
【表６】
2006146894.tif 000010
【００８０】
図１１および図１２は、アウトライン推定の例を示している。グラウンドトゥルースラベルは、第１または唯一の値として示されている。予想されたラベルは、グラウンドトゥルースと異なる場合、たとえそうであるとしても、グラウンドトゥルース値の直後に示される。
【００８１】
アウトライン構造には多くのあいまいさがある。このことは、データのラベル付け、トレーニングおよびパフォーマンス評価を、パラグラフセグメンテーションの問題におけるよりもさらに困難にする。グラウンドトゥルースデータは手でラベル付けすることができるので、主観的であり、大きなばらつきを含んでいる。異なる例に対するそのような選択的な決定の間でばらつきが存在する。このことは、クラス間の境界を分かりにくくして、トレーニングの効果をさらに弱める。図１１はほぼ正しい例であり、図１２はほぼ完全に誤っている例である。しかし、厳密な検査により、これらの２つのファイルが実際には類似した構造および類似した推定結果を備えていることが明らかになる。エラー率の不一致は、ラベル付けのあいまいさによるところが大きい。（ｉ）図１２のタイトル行に０ではなく１をラベル付けすることにより、ほとんどの結果はグラウンドトゥルースから深さ１レベルはずれる。（ｉｉ）図１１の第３行では、正しく構文解析するために内容の理解が必要である。（ｉｉｉ）第５行および第６行のユーザの意図は、注意深く読んだ後であっても不明瞭である。グラウンドトゥルースおよび推定結果は、いずれももっともらしく思われる。
【００８２】
ユーザインターフェースを通じて公開された場合、（ｉ）のような多くの「エラー」は、ユーザが気づくことすらない。これは、保持されるラベルによって確立された関係だけで、ラベルが表示にない可能性があるためである。さらに、エラーに対するユーザの許容度も、あいまいさの度合いと共に高まる。（ｉｉ）および（ｉｉｉ）のようなエラーが大きな不快感をもたらす可能性は低い。表３の数値を生成するために使用できる単純化したエラーメトリックは、ユーザエクスペリエンスを十分に反映しないので、慎重に解釈されるべきである。
【００８３】
階層アウトライン構造は一般に、ユーザノートにおいて生じる。ユーザは、これらのアウトラインの構造を編集するための、おそらくはこれらをワード処理プログラムにエクスポートするための方式を必要としている。前述の説明では、手書きのアウトラインを解釈して、高い信頼性を備える正しい構造を自動的に抽出するシステムについて説明している。
【００８４】
説明されているシステムは、テキストのブロック内の各行に、アウトラインツリー内のその「深さ」を示すラベルを付けようと試み、同じツリーノードの一部であるこれらの行に、フラグを立てる。コリンズによって導入されたマルコフモデルは、行を分類するために使用される。このモデルは、インデントおよび長さなど、使用可能な行特徴を組み合わせて、グローバルに整合した行ラベルの割り当てを見つけだす。コリンズモデルのパラメータは、トレーニングデータのセットから学習される。その結果、システムは、手作業で設計されたシステムに比べて堅固である。最後に、行ラベルの計算は高速であり、通常のインクページに要するのは０．１秒未満である。
【００８５】
（トレーニング例）
図１３および図１４は、トレーニング例の作成に関連している。図１３は、トレーニング例を作成するために使用できる例示的なユーザインターフェースを示している。ここでトレーニング例は、前述のアルゴリズムのモデルパラメータを調整する上で役立つ。
【００８６】
図１３を参照すると、ユーザは、提示された情報にラベルを追加できるようにする、インターフェースを使用することができる。ラベルは、望ましい構文解析システムの結果と類似するように意図されている。ユーザインターフェースは、ディスプレイ１３０１として示されている。ディスプレイ１３０１は、情報１３０２を表示する。ここで、情報１３０２は、手書きのインクである。構文解析システムは、情報のさまざまな行を構文解析し、ユーザが行のラベルを追加できるようにする。例えば、情報１３０２の第１行が選択されている。選択は、強調表示することも、強調表示しないこともでき、ユーザの選択を示すように視覚的に変更することもできる。ここで、情報１３０２の第１行は、境界ボックスおよび強調されるインクに囲まれている。次にユーザは、階層ラベル１３０４を入力する。ユーザを補助するため、領域１３１７は、情報の行に並置して表示することもしないこともできる。領域１３１７は、ユーザの入力階層情報が現在選択されている行に関連付けられることを示す、視覚的指示をユーザに提供することができる。次にユーザは、情報の他の行へ（マウス、ペン、キーボード、トラックボールその他の入力装置を使用して）移動し、追加の階層ラベル（例えばラベル１３０５から１３０７）を入力することができる。ハードウェア入力装置に加えて、ユーザは、ソフトウェア生成の（software-generated）矢印キー１３０８、または他のソフトウェアナビゲーション技法を使用して、受信した情報１３０２の行をナビゲートすることができる。
【００８７】
図１３は、情報１３０２のアウトラインモード１３０９を反映する。他のモードには、ラベル付けモード１３１０、黒丸モード１３１１、および／または読み取り順序および読み取り方向モード１３１２を含めることができる。図１３はさらに、システムが情報の行をどのように強調表示するか、または強調表示しないかを示している。例えば、第１行は境界ボックス１３１３で強調表示されている。他の境界ボックス（１３１４から１３１６）は、他の行に関連付けられている。
【００８８】
図１４は、トレーニング例を作成するために、受信した情報にラベルを追加する例示的な方法を示している。トレーニング例はその後、ラベル付けアルゴリズムのモデルパラメータを調整するために使用することができる。ステップ１４０４において、情報が受け取られる。情報は、インク、図面、またはグラフィカル情報（非ＡＳＣＩＩ）の情報であってもよい。情報は、ストレージ１４０１（ローカルまたはリモート）から、直接ユーザ１４０２から、またはコンピュータ１４０３によって生成されて（例えば、システムは、ユーザが生成された情報を階層形式に構文解析できるように、ランダムな情報を生成することができる）供給することができる。
【００８９】
ステップ１４０５において、構文解析システムは、受信した情報を行に構文解析する。ステップ１４０５は、情報の行への構文解析が、受信ステップ１４０４の前または後に発生する可能性があることを強調するために、破線ボックスで示されている。例えば、ステップ１４０４で受信した情報は、以前構文解析されてストレージ１４０１に格納されたか、ステップ１４０２において情報を入力するユーザによって以前構文解析されたか、あるいはステップ１４０３において別個の行として生成された可能性もある。
【００９０】
ステップ１４０６において、方法はユーザの入力を受信する。この入力は、受信した情報の行の階層レベルを指定するラベルである。ステップ１４０７において、方法は、割り当てられたラベルを情報のそれぞれの行に関連付ける。次に、ステップ１４０８において、方法は、少なくとも結果として生じた関連を、トレーニング例の少なくとも部分として格納する。ステップ１４０８は、ステップ１４０７内の各関連に従うか、またはステップ１４０７の多くの関連に従うことができる。一部の実施形態において、方法は、受信した情報内の各行がラベル付けされるまで、ステップ１４０７を完了した後、ステップ１４０６に戻る。個々に格納される場合に比べて、関連のグループを一括して格納できることが容易に理解されよう。
【００９１】
ステップ１４０８において作成されたトレーニング例（またはステップ１４０８から作成されたトレーニング例の集合）は次に、階層情報をより正確にラベル付けするようアルゴリズムをトレーニングするために使用することができる。
【００９２】
本発明を、その好ましく、例示的な実施形態に関して説明してきた。本明細書の検討により、当業者には、添付の特許請求の範囲の範囲、および趣旨の範囲内で他のさまざまな実施形態、変更および変形が考えられるであろう。
【図面の簡単な説明】
【００９３】
【図１】本発明の態様による汎用コンピューティング環境の例を示す図である。
【図２】本発明の態様によるタブレットコンピュータの例を示す図である。
【図３】階層情報を構文解析するためのさまざまな技法を示す図である。
【図４】階層情報を構文解析するためのさまざまな技法を示す図である。
【図５】本発明の態様による階層情報を構文解析するための他の技法を示す図である。
【図６】本発明の態様による階層情報にラベルを割り当てるための方法を示す図である。
【図７】本発明の態様によるエラーの割合対実現エラー率の比較を示す図である。
【図８】本発明の態様による階層情報のさまざまな例を示す図である。
【図９】本発明の態様による階層情報のさまざまな例を示す図である。
【図１０】本発明の態様による階層情報のさまざまな例を示す図である。
【図１１】本発明の態様による階層情報のさまざまな例を示す図である。
【図１２】本発明の態様による階層情報のさまざまな例を示す図である。
【図１３】本発明の態様によるトレーニング例を作成するためのユーザインターフェースを示す図である。
【図１４】本発明の態様によるトレーニング例を作成するための方法を示す図である。
【図１】
2006146894.tif 000019
【図２】
2006146894.tif 000020
【図３】
2006146894.tif 000021
【図４】
2006146894.tif 000022
【図５】
2006146894.tif 000023
【図６】
2006146894.tif 000024
【図７】
2006146894.tif 000025
【図８】
2006146894.tif 000026
【図９】
2006146894.tif 000027
【図１０】
2006146894.tif 000028
【図１１】
2006146894.tif 000029
【図１２】
2006146894.tif 000030
【図１３】
2006146894.tif 000031
【図１４】
2006146894.tif 000032
【外国語明細書】
2006146894000001.pdf