対象とされる広告で使用するためのユーザ情報の生成
【課題】ユーザプロファイルにより適合した広告を提供する。
【解決手段】ユーザプロファイル情報は、（ａ）初期ユーザプロファイル情報を決定し、（ｂ）ユーザプロファイル情報を推測し、（ｃ）該初期ユーザプロファイル情報と該推測されたユーザプロファイル情報の両方を使用して、決定される。初期ユーザプロファイル情報は、ユーザによって提出された過去の検索クエリーを使用して決定される。ユーザプロファィルの推測は、（ａ）多くの文書とユーザのそれぞれにノードを定義し、（ｂ）グラフを定義するためにノード間の関連がある場合にはノード間にエッジを追加し、（ｃ）グラフのトポロジーを使用することによって行われる。
【解決手段】ユーザプロファイル情報は、（ａ）初期ユーザプロファイル情報を決定し、（ｂ）ユーザプロファイル情報を推測し、（ｃ）該初期ユーザプロファイル情報と該推測されたユーザプロファイル情報の両方を使用して、決定される。初期ユーザプロファイル情報は、ユーザによって提出された過去の検索クエリーを使用して決定される。ユーザプロファィルの推測は、（ａ）多くの文書とユーザのそれぞれにノードを定義し、（ｂ）グラフを定義するためにノード間の関連がある場合にはノード間にエッジを追加し、（ｃ）グラフのトポロジーを使用することによって行われる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は広告に関する。特に、本発明は、例えば検索クエリー又は文書要求等のユーザの要求に役立つための、特に関連性のある広告又は広告クリエーティブ（ｃｒｅａｔｉｖｅｓ）を決定することに関する。
【背景技術】
【０００２】
テレビ、ラジオ、新聞及び雑誌等の、従来の媒体を使用する広告は周知である。残念なことに、人口学的な研究及び多様な報道発信源の典型的な視聴者についてのまったく妥当な前提で準備していても、広告主は自分の広告予算の大半が単に無駄にされていることを認識している。さらに、このような無駄を特定し、排除することは非常に困難である。
【０００３】
最近では、より双方向性の媒体での広告が一般的になってきた。例えば、インターネットを使用する人の数が爆発的に伸びるにつれ、広告主はインターネット上で提供される媒体とサービスを、広告を行うための潜在的に強力な方法として捉えるようになった。
【０００４】
広告主は、このような広告の価値を最大限にする目的で複数の戦略を作成してきた。１つの戦略では、広告主は、（一般性を失うことなく本明細書中で「ウェブサイト」と呼ばれる）双方向性の媒体又はサービスを提供するための一般的な存在又は手段を、多数の消費者へのパイプとして使用する。この第１の手法を使用して、広告主は、例えばニューヨークタイムズのウェブサイト（Ｎｅｗ Ｙｏｒｋ Ｔｉｍｅｓ Ｗｅｂｓｉｔｅ）又はＵＳＡトゥデイのウェブサイト（ＵＳＡ Ｔｏｄａｙ Ｗｅｂｓｉｔｅ）のホームページ上に、広告を掲載してよい。別の戦略では、広告主はより狭いニッチ視聴者をその広告の対象とし、それにより視聴者の前向きの反応の尤度を高めようと試みる可能性がある。例えば、コスタリカの熱帯雨林での観光を奨励している官庁は、ヤフー（登録商標）ウェブサイト（Ｙａｈｏｏ Ｗｅｂｓｉｔｅ）のエコツーリズム−旅行のサブディレクトリに広告を掲載する可能性がある。広告主は通常はこのような対象の設定を手作業で決定する。
【０００５】
戦略に関係なく、ウェブベースの広告（「ウェブ広告」とも呼ばれる）は、通常、「バナー広告」−つまり、グラフィック要素を含む矩形のボックス−の形で、その広告視聴者に提示される。広告視聴者の一員（一般性を失うことなく本明細書中では「視聴者」又は「ユーザ」と呼ばれる）が、これらのバナー広告のうち１つをクリックすることにより選択すると、通常、埋め込まれているハイパーテキストリンクが視聴者を広告主のウェブサイトに案内する。視聴者が広告を選択するこのプロセスが、一般的に「クリックスルー」（「クリックスルー」は、任意のユーザの選択をカバーすることを目的としている）と呼ばれている。広告のインプレッション数（つまり広告が表示される回数）に対するクリックスルー数の割合が、一般的に広告の「クリックスルー率」と呼ばれる。
【０００６】
ユーザが過去に供給された広告に関連したトランザクションを完了すると、「コンバージョン」が発生すると言われている。コンバージョンを構成している内容は場合によって異なり、種々の方法で決定できる。それは例えば、ユーザが広告主のウェブページと呼ばれる広告をクリックし、そのウェブページを離れる前にそこで購入を完了すると、コンバージョンが発生するケースである可能性がある。代わりに、コンバージョンは、ユーザが広告を見てから、所定の時間（例えば７日間）内に広告主のウェブページで購入することとして定義される場合がある。さらに別の代替策では、コンバージョンは、例えばホワイトペーパーをダウンロードする、ウェブサイトの少なくとも既定の深部まで進む、少なくとも特定数のウェブページを表示する、ウェブサイト又はウェブページで少なくとも所定の時間量を費やす、ウェブサイトで登録する等の、測定可能／観察可能なユーザアクションであるとして、広告主に定義されてよい。コンバージョンを構成するユーザアクションはこれに限られていないが、多くの場合、ユーザアクションが購入の完了を示さない場合、それらが販売の手がかりを示すことがある。実際に、何がコンバージョンを構成するのかについて、他の多くの定義が考えられる。広告インプレッション数（つまり広告が表示される回数）に対するコンバージョン数の割合は、一般にはコンバージョン率と呼ばれる。コンバージョンが広告が供給されてから所定の時間内に発生し得ると定義される場合、コンバージョン率の１つの考えられる定義が、過去の所定の時間より多く供給された広告を考慮するにすぎない可能性がある。
【０００７】
ウェブサイトベースの広告の当初の展望にも関わらず、既存の手法にはいくつかの問題が残されている。広告主は大きな客層に到達できるが、しばしば自分の広告投資からの収益に満足していない。
【０００８】
同様に、（「ウェブサイトホスト」、又は「広告消費者」と呼ばれる）広告が提示されるウェブサイトホストは、ユーザの経験を損なうことなく広告収入を最大限にするという課題を抱えている。ユーザの利益を超えて広告収入を位置づけるウェブサイトホストもいる。このような１つのウェブサイトが、ユーザのクエリーに応えて「検索結果」を装う広告を返すいわゆる「検索エンジン」サービスを主催する「Ｏｖｅｒｔｕｒｅ．ｃｏｍ」である。Ｏｖｅｒｔｕｒｅ．ｃｏｍウェブサイトは、広告主が金を支払って、検索結果と称するもののリストの上の方に自分のウェブサイト（又は対象のウェブサイト）の広告を配置できるようにしている。ユーザが広告をクリックした場合にだけ広告主が支払いをする（つまりコストパークリック）ような方式が実現されている場合、対象設定がうまく行われていない広告はクリックされず、したがって支払いを必要としないために、広告主は自らの広告の対象を効果的に設定する意欲をなくしてしまう。その結果、高いコストパークリックの広告がトップの近くに、又はトップに表示されるが、視聴者はそれらをクリックしないため、必ずしも広告発行元にとっての本当の収入にはならない。さらに、視聴者がクリックするであろう広告は、リストのさらに下のほうにある、あるいはリストには載っていないために、広告の関連性は損なわれる。
【０００９】
例えばグーグル（登録商標）（Ｇｏｏｇｌｅ（登録商標））等の検索エンジンは、広告主が自らの広告が検索結果のページとともに表示されるように、及びそれらが検索結果ページを表示するように指示したクエリーにおそらく関連性があるように、広告の対象を設定できるようにした。ｅ−メール情報に基づいて広告の対象を設定するもの（例えば、２００３年６月２日に出願された、Ｊｅｆｆｒｅｙ Ａ．Ｄｅａｎ、Ｇｅｏｒｇｅｓ Ｒ．Ｈａｒｉｋ及びＰａｕｌ Ｂｕｃｈｅｉｔを発明者として示す「Ｅメールに関連した情報を使用して広告を提供すること（ＳＥＲＶＩＮＧ ＡＤＶＥＲＴＩＳＥＭＥＮＴＳ ＵＳＩＮＧ ＩＮＦＯＲＭＡＴＩＯＮ ＡＳＳＯＣＩＡＴＥＤ ＷＩＴＨ Ｅ−ＭＡＩＬ）」と題される（参照してここに組み込まれる）米国特許出願第１０／４５２，８３０号に説明されているシステム）、あるいはコンテンツに基づいたターゲット広告（２００３年２月２６日に出願された、Ｄａｒｒｅｌ Ａｎｄｅｒｓｏｎ、Ｐａｕｌ Ｂｕｃｈｅｉｔ、Ａｌｅｘ Ｃａｒｏｂｕｓ、Ｃｌａｉｒｅ Ｃｕｉ、Ｊｅｆｆｒｅｙ Ａ．Ｄｅａｎ、Ｇｅｏｒｇｅｓ Ｒ．Ｈａｒｉｋ、Ｄｅｅｐａｋ Ｊｉｎｄａｌ及びＮａｒａｙａｎａｎ Ｓｈｉｖａｋｕｍａｒを発明者として示す「コンテンツに基づいて広告を供給すること（ＳＥＲＶＩＮＧ ＡＤＶＥＲＴＩＳＥＭＥＮＴＳ ＢＡＳＥＤ ＯＮ ＣＯＮＴＥＮＴ）」と題される（参照してここに組み込まれる）米国特許出願第１０／３７５，９００号を参照されたい）等の、他の対象が設定された広告システムも、同様の課題を抱えている可能性がある。すなわち、広告システムは、ユーザ要求情報に概して関連性のある、特に現在のユーザの関心に関係する広告を提示しようとする。
【００１０】
前記から理解できるように、キーワード対象設定（ｋｅｙｗｏｒｄ−ｔａｒｇｅｔｅｄ）広告又はコンテンツ対象設定（ｃｏｎｔｅｎｔ−ｔａｒｇｅｔｅｄ）広告等の対象設定広告システムは、非常に有用な形式の広告を提供する。ただし、通常、関連性のある広告を供給できるオンライン広告システムも、多くの場合、特定のユーザに最も適した関連性のある広告を選択することはできない。
【００１１】
したがって、オンライン広告の性能を改善する必要性がある。さらに具体的には、要求を提出したユーザに対する、例えば検索クエリー又は文書要求等の、何らかのユーザ要求のために供給される広告の関連性を高める必要性がある。
【発明の概要】
【００１２】
本発明は、広告を採点するために使用される一致を決定するための方法及び装置を説明する。このような方法及び装置は、（ａ）（ｉ）広告の広告待ち受けページのユーザプロファイル情報及び／又は広告の対象を設定するために使用されるユーザプロファイル情報、及び（ｉｉ）広告が表現される先のユーザのユーザプロファイル情報を使用して、第１の一致値を求めてよく、（ｂ）（ｉ）広告の待ち受けページのユーザプロファイル情報及び／又は広告の対象を設定するために使用されるユーザプロファイル情報、及び（ｉｉ）広告が供給される文書のユーザプロファイル情報を使用して、第２の一致値を求めてよく、（ｃ）第１の一致値と第２の一致値を使用して広告を採点するために使用される一致を決定してよい。
【００１３】
本発明は、前記のような方法及び装置において、あるいはユーザプロファイル情報を使用して広告の対象を設定するための他の方法及び装置において、広告の広告待ち受けページのユーザプロファイル情報の少なくとも一部、広告の対象設定に使用されるユーザプロファイル情報の少なくとも一部、ユーザのユーザプロファイル情報の少なくとも一部、及び／又は文書のユーザプロファイル情報の少なくとも一部が、推測されてよいことも教示する。
【００１４】
本発明の一実施形態では、ユーザのためのユーザプロファイル情報は、（ａ）ユーザのために初期ユーザプロファイル情報を決定すること、（ｂ）ユーザのためにユーザプロファイル情報を推測すること、及び（ｃ）初期ユーザプロファイル情報と推測されたユーザプロファイル情報の両方を使用して、ユーザのためのユーザプロファイル情報を決定することによって、決定されてよい。ユーザのための初期ユーザプロファイル情報は、ユーザによって提出された過去の検索クエリー、及び／又はユーザによる過去の文書の選択を使用して決定されてよい。
【００１５】
本発明の一実施形態では、ユーザのためのユーザプロファイル情報は、（ａ）多くの文書のそれぞれとユーザのためのノードを定義すること、（ｂ）グラフを定義するためにノード間に関連がある場合にノード間でエッジを追加すること、及び（ｃ）グラフのトポロジー及び他の文書のユーザプロファイル情報を使用してユーザのためのユーザプロファイル情報を推測することによって、推測されてよい。
【００１６】
本発明の一実施形態では、文書のためのユーザプロファイル情報は、（ａ）文書のための初期ユーザプロファイル情報を決定すること、（ｂ）文書のためのユーザプロファイル情報を推測すること、及び（ｃ）初期ユーザプロファイル情報と推測されたユーザプロファイル情報の両方を使用して、文書のためのユーザプロファイル情報を決定することによって、決定されてよい。文書のための初期ユーザプロファイル情報は、文書からのコンテンツ情報、及び／又は文書メタ情報を使用して決定されてよい。
【００１７】
本発明の一実施形態では、文書のためのユーザプロファイル情報は、（ａ）多くの文書のそれぞれのための、及び多くのユーザのそれぞれのためのノードを定義すること、（ｂ）グラフを定義するためにノード間に関連がある場合にノード間にエッジを追加すること、（ｃ）グラフのトポロジー、及びユーザの、及び他の文書のユーザプロファイル情報を使用して文書のためのユーザプロファイル情報を推測することによって、推測されてよい。
【図面の簡単な説明】
【００１８】
【図１】広告システムと対話できる関係者又はエンティティを示す高水準図である。
【図２】本発明が中で又は用いて動作してよい、例示的な広告環境のバブルチャートである。
【図３】図２に示されたようなオンライン広告環境の中で、あるいは図２に示されたようなオンライン広告環境を用いて使用されてよい、本発明にしたがった動作のバブルチャートである。
【図４】本発明にしたがった方法で生成され、更新され、及び／又は使用されてよい、ユーザプロファイル情報を記憶するための、例示的なデータ構造を示す。
【図５】広告スコア（ｓｏｒｅ）の係数であってよい全体的な一致値の考えられる成分を示す。
【図６】本発明にしたがった方法で文書ＵＰＩを決定するために使用されてよい、例示的な方法６００のフロー図である。
【図７】本発明にしたがった方法でユーザＵＰＩを決定するために使用されてよい、例示的な方法７００のフロー図である。
【図８】本発明にしたがった方法で初期のＵＰＩ又はベースライン文書ＵＰＩを決定するために使用されてよい、例示的な方法８００のフロー図である。
【図９】本発明にしたがった方法で初期のＵＰＩ又はベースラインユーザＵＰＩを決定するために使用されてよい、例示的な方法９００のフロー図である。
【図１０】ユーザと文書がどのように関連付けられるのかを示す。
【図１１】本発明にしたがった方法でユーザ及び／又は文書を関連付けるために使用されてよい、例示的な方法１１００のフロー図である。
【図１２】実行されてよい多様な動作の少なくともいくつかを達成するために、及び本発明にしたがった方法で使用及び／又は生成されてよい情報を記憶するために、使用されてよい装置のブロック図である。
【発明を実施するための形態】
【００１９】
本発明は、ユーザプロファイル情報を決定し、このような決定されたユーザプロファイル情報を広告供給のために使用するための、新規の方法、装置、メッセージフォーマット、及び／又はデータ構造を含んでよい。以下の説明は、当業者が本発明を作り、使用できるようにするために提示され、特定の応用例及びそれらの要件との関連で提供される。開示される実施形態に対する多様な変形は当業者に明らかとなり、以下に述べられる一般的な原則は他の実施形態及び応用例に適用されてよい。したがって、本発明は示されている実施形態に制限されることを意図せず、発明者は自らの発明を、説明されている任意の特許性がある主題と見なす。
【００２０】
広告対象設定を改善するための１つの考えられる方法は、広告対象設定システムがユーザプロファイルを取得し、使用することである。例えば、ユーザプロファイルは、（例えばユーザがサービスに加入しているとき等）ユーザが自発的に与える情報を使用して決定されてよい。このユーザ属性情報は、次に広告の広告主指定属性（例えば対象設定基準）と突き合わされてよい。残念なことに、多くのウェブサイト（例えば検索エンジン）は加入又はユーザ登録を必要としないため、ユーザプロファイル情報は必ずしもいつも入手できない。さらに、たとえ入手できるときも、ユーザプロファイルは不完全である場合がある（例えば、加入時に与えられる情報は、プライバシーの考慮等のためにサービスに必要とされるものに限定され、したがって包括的ではない可能性があるからである）。さらに、広告主はユーザプロファイル対象設定情報を手作業で設定する必要がある場合がある。さらに、ユーザプロファイル情報が入手できる場合でも、広告主が効果的に広告の対象を設定するためにこの情報を使用できない可能性がある。
【００２１】
以下では、本発明が中で動作してよい環境、又は本発明が用いて動作してよい環境が第４．１項に説明される。本発明の例示的な実施形態は第４．２項に説明される。いくつかの代替策及び改良版は第４．３項に説明される。最後に、本発明に関するいくつかの結論は第４．４項に述べられている。
【００２２】
第４．１項 本発明が中で動作してよい、又は本発明が用いて動作してよい環境
第４．１．１項 例示的な広告環境
図１は、広告環境の高水準図である。該環境は広告入力保持及び配信システム１２０を含んでよい。広告主１１０は、システム１２０に広告情報を直接的に又は間接的に入力、保持、及び追跡調査してよい。広告は、いわゆるバナー広告等のグラフィック広告、テキストのみの広告、画像広告、音声広告、ビデオ広告、このような構成要素のうち１つ以上（ｏｎｅ ｏｆ ｍｏｒｅ）を組み合わせた広告の形をとってよい。広告は、リンク等の埋め込まれた情報、及び／又は機械実行可能な命令を含んでもよい。広告消費者１３０は、彼らの要求に応える広告をシステム１２０から受け入れ、システム１２０に使用情報を提供するために、広告に対する要求を提出してよい。図示されていないが、他のエンティティは、システム１２０に（広告と関連したコンバージョン又はクリックスルーが発生したかどうか等の）使用情報を提供してよい。この使用情報は、供給された広告に関連した、測定された又は観察されたユーザ動作を含んでよい。
【００２３】
広告消費者１３０の１つの例は、コンテンツ（例えば、記事、議論スレッド、音楽、ビデオ、グラフィックス、検索結果、ウェブページのリスト等）に対する要求を受信し、要求に応えて要求されたコンテンツを取り出す、あるいはそれ以外の場合提供する、一般コンテンツサーバである。コンテンツサーバは、システム１２０に広告に対する要求を提出してよい。このような広告要求は、所望される多くの広告を含んでよい。広告要求はまた、コンテンツ要求情報を含んでよい。この情報は、コンテンツ自体（例えばページ）、コンテンツ又はコンテンツ要求に対応するカテゴリ（例えば、アート、ビジネス、コンピュータ、アート−映画、アート−音楽等）、コンテンツ要求の一部又はすべて、コンテンツ寿命、コンテンツタイプ（例えば、テキスト、グラフィックス、ビデオ、音声、混合媒体等）、ジオロケーション情報等を含んでよい。
【００２４】
コンテンツサーバは、システム１２０によって提供される広告の１つ以上と、要求されたコンテンツを組み合わせてよい。コンテンツと広告（複数の場合がある）を含むこの組み合わされた情報は、次に、ユーザに提示するために、コンテンツを要求したエンドユーザに向かって転送される。最後に、コンテンツサーバは広告に関する情報、及びどのようにして、いつ、及び／又はどこで広告を表示しなければならないのか（例えば、場所、クリックスルーか否か、インプレッション時間、インプレッション日付、サイズ、コンバージョンか否か等）についての情報を、システム１２０に送り返してよい。代わりに、又はさらに、このような情報は何らかの手段によってシステム１２０に提供し直されてよい。
【００２５】
広告消費者１３０の別の例が検索エンジンである。検索エンジンは検索結果のためのクエリーを受け取ってよい。それに応じて、検索エンジンは関連する検索結果を（例えばウェブページのインデックスから）取り出してよい。例示的な検索エンジンは、Ｓ．Ｂｒｉｎ及びＬ．Ｐａｇｅの記事、「大規模ハイパーテキスト検索エンジンの解剖（Ｔｈｅ Ａｎａｔｏｍｙ ｏｆ ａ Ｌａｒｇｅ−Ｓｃａｌｅ Ｈｙｐｅｒｔｅｘｔｕａｌ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ）」、第７回国際ワールドワイドウェブ会議（Ｓｅｖｅｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ Ｃｏｎｆｅｒｅｎｃｅ）、オーストラリア、ブリスベン（Ｂｒｉｓｂａｎｅ，Ａｕｓｔｒａｌｉａ）及び米国特許第６，２８５，９９９号（ともに参照してここに組み込まれる）に説明されている。このような検索結果は、例えばウェブページのタイトルリスト、それらのウェブページから抽出されたテキストの抜粋、及びそれらのウェブページへのハイパーテキストリンクを含んでよく、所定数の（例えば１０の）検索結果に分類されてよい。
【００２６】
検索エンジンは、システム１２０に広告に対する要求を提出してよい。要求は所望される多数の広告を含んでよい。この数は、検索結果、検索結果によって占められる画面又はページ空間の量、広告の大きさと形状等に依存してよい。一実施形態では、所望される広告の数は１から１０、好ましくは３から５となるであろう。広告に対する要求は（入力又は構文分析されたとおりの）クエリー、（クエリーが関係者及びこのような関係者の識別子からきたのかに関係なく、ジオロケーション情報等の）クエリーに基づいた情報、及び／又は検索結果と関連付けられた又は検索結果に基づいた情報を含んでもよい。このような情報は、例えば検索結果に関連した識別子（例えば文書識別子、つまり「ｄｏｃＩＤ」）、検索結果に関連したスコア（例えば、クエリー及び文書、ページランクスコア、及び／又はＩＲスコアとページランクスコアの組み合わせに対応する特徴ベクトルのドット積のような情報検索（「ＩＲ」）スコア）、特定された文書から抽出されるテキストの抜粋（例えばウェブページ）、特定された文書の全文、特定された文書の特徴ベクトル等を含んでよい。
【００２７】
検索エンジンは、システム１２０によって提供される広告の１つ以上と検索結果を結合してよい。検索結果と広告（複数の場合がある）を含むこの結合された情報は、次にユーザに提示するために、コンテンツを要求したユーザに向かって転送される。好ましくは、検索結果は、有料広告とおそらくは中立の検索結果の間でユーザを惑わせないように、広告と区別して保持される。
【００２８】
最後に検索エンジンは、広告に関する情報、及び広告がいつ、どこで、及び／又はどのようにして表示されるべきであったのか（例えば、位置、クリックスルーか否か、インプレッション時間、インプレッション日付、コンバージョンか否か等）についての情報を、システム１２０に送り返してよい。代わりに、又はさらに、このような情報は何らかの手段によってシステム１２０に提供し直されてよい。
【００２９】
第４．１２章 例示的な広告入力保持および配信環境
図２は、本発明が中で使用されてよい、あるいは本発明がともに使用されてよい、例示的な広告システム１２０’を示す。例示的な広告システム１２０’は在庫システム２１０を含んでよく、広告情報２０５と使用情報２４５を記憶してよい。例示的なシステム１２０’は、広告情報入力管理動作２１５、キャンペーン（例えば対象設定）支援動作２２０、会計及び請求書作成発行動作２２５、広告供給動作２３０、関連性決定動作２３５、最適化動作２４０、相対提示属性割り当て（例えば、位置順序付け）動作２５０、不正検出動作２５５、及び結果インタフェース動作２６０を支援してよい。
【００３０】
広告主１１０は、インタフェース２１６によって示されるように、広告情報入力管理動作２１５を介してシステム１２０’と接続してよい。広告消費者１３０は、インタフェース２３１によって示されるように広告供給動作２３０を介してシステム１２０’と接続してよい。広告消費者１３０及び／又は他のエンティティ（図示せず）は、インタフェース２６１によって示されるように結果インタフェース動作２６０を介してシステム１２０’と接続してもよい。
【００３１】
広告プログラムは、アカウント、キャンペーン、クリエーティブ、対象設定等に関する情報を含んでよい。用語「アカウント」は、既定の広告主についての情報（例えば、一意のｅメールアドレス、パスワード、請求書作成発行情報等）に関する。「キャンペーン」又は「広告キャンペーン」は、１つ以上の広告のうちの１つ以上のグループに関し、開始日、終了日、予約情報、ジオターゲティング情報、シンジケート情報等を含んでよい。例えば、ホンダ（登録商標）（Ｈｏｎｄａ）は、その自動車取扱商品のための１つの広告キャンペーンと、そのオートバイ取扱商品のための別個の広告キャンペーンを有してよい。その自動車取扱商品のためのキャンペーンは、それぞれが１つ以上の広告を含む１つ以上の広告グループを有してよい。各広告グループは、キーワードの集合、及び最大費用付け値（ｂｉｄ）（クリックスルーあたり費用、コンバージョンあたり費用等）を含んでよい。代わりに、あるいは加えて、各広告グループは平均費用付け値（例えば、クリックスルーあたり平均費用、コンバージョンあたり平均費用等）を含んでよい。したがって、単一の最大費用付け値及び／又は単一の平均費用付け値は１つ以上のキーワードと関連付けられてよい。このように、各広告グループは１つ以上の広告つまり「クリエーティブ」（すなわち、最終的にエンドユーザに表示される広告コンテンツ）を有してよい。当然、広告情報２０５は多かれ少なかれ情報を有してよく、多くの異なる方法で編成されてよい。
【００３２】
広告情報２０５は、該広告情報入力管理動作２１５を介して入力、管理できる。キャンペーン（例えば対象設定）支援動作２２０は、広告主１１０が効果的な広告キャンペーンを作成するのを手助けするために利用できる。例えば、キャンペーン支援動作２２０は、検索エンジンとともに使用するための広告の関連で、すべての考えられる広告インプレッション、すでに予約されている広告インプレッション、及び既定のキーワードについて利用可能な広告インプレッションを追跡調査してよい、在庫システム２１０によって提供される情報を使用できる。
【００３３】
広告供給動作２３０は、広告消費者１３０からの広告に対する要求を果たしてよい。広告供給動作２３０は、既定の要求のための候補広告を決定するために関連性決定動作２３５を使用してよい。広告供給動作２３０は、次に候補広告のうち１つ以上の最終的な集合を選択するために最適化動作２４０を使用してよい。広告供給動作２３０は、次に返される広告の提示を順序付けるために、相対提示属性割り当て動作２５０を使用してよい。会計及び請求書作成発行動作２２５は、広告の供給に関連する料金を追跡調査するため、及び広告主に請求書を送るために使用されてよい。不正検出動作２５５は、盗まれたクレジットカードの使用による等、広告システムの（例えば広告主による）不正な使用を削減するために使用できる。最後に、結果インタフェース動作２６０は、クリックスルーが発生したかどうか、コンバージョンが発生したかどうか（例えば、広告された商品又はサービスの販売が開始されたか、あるいは広告の表示から所定の時間内に完了されたか）等の、実際に供給された広告について（消費者１３０又は他の何らかのエンティティからの）結果情報を受け入れるために使用されてよい。このような結果情報はインタフェース２６１に受け入れられ、関連付けられた結果だけではなく、広告及び広告が供給された時刻を特定するための情報も含んでよい。
【００３４】
本発明の多様な態様は、関連性決定動作２３５、相対的な提示属性順序付け動作２５０、及び／又は広告供給動作２３０とともに使用されてよい。
【００３５】
第４．１．３項 例示的なネットワーク環境
図３は、本発明が使用されてよい例示的なネットワーク環境３００を示す。例示的なネットワーク環境３００は、それぞれがブラウザ３２０（又は何らかの他の情報要求表示手段）を有する、１台以上のクライアントデバイス３１０を含んでよい。クライアントデバイス３１０は、１台以上のコンテンツサーバ３２０によって供給される文書３３５を要求し、１つ以上の検索エンジン３４０を使用してそれらの又は他の文書に含まれるコンテンツを検索できる。広告サーバ３５０は、１つ以上の広告３５５を供給できる。供給された該１つ以上の広告３５５は、コンテンツサーバ３３０によって供給される文書（及び／又はこのような文書に対する要求）に関連性があってよい、及び／又は検索エンジン３４０によって生じる検索結果（及び／又は検索クエリー）に関連性があってよい。（例えば、１台以上のクライアントデバイス３１０と関連付けられる個々のユーザ又はユーザのグループについての）ユーザ情報３６５は、１台以上の情報サーバ３６０に記憶されてよい。代わりに、又は加えて、ユーザ情報（図示せず）は、１台以上のコンテンツサーバ３３０、１つ以上の検索エンジン３４０、及び／又は１つ以上の広告サーバ３５０に記憶されてよい。１台以上のクライアントデバイス３１０、コンテンツサーバ３３０、検索エンジン３４０、広告サーバ３５０、及び／又はユーザ情報サーバ３６０は、１つ以上のネットワーク３７０を介して互いと情報を交換してよい。該１つ以上のネットワーク３７０はインターネット及びサーバであってよく、検索エンジンはコンピュータであってよい。ユーザ情報（例えば、ユーザプロファイルデータベース）、情報インデックス、及び広告インデックスは、別のレポジトリである必要はない。それらは、単一のレポジトリに記憶されてよい。さらに、データのこれらの形式はインタリーブ化されてよい（例えば、広告データベースは、いくつかの部分集合だけが特定のタイプのユーザのために取り出されるように、広告上に「ユーザ特徴タグ」を含んでよい）。
【００３６】
第４．１．４項 定義
図１、図２、図３を参照して前述された例示的なシステム及び任意の他のシステムで使用されるようなオンライン広告は、多様な固有の特徴を有してよい。このような特徴は、アプリケーション及び／又は広告主によって指定されてよい。これらの特徴は以下で「広告特徴」と呼ばれている。例えば、テキスト広告のケースでは、広告特徴は、タイトル行、広告テキスト、及び埋め込まれているリンクを含んでよい。画像広告のケースでは、広告特徴は、画像、実行可能なコード、及び埋め込まれているリンクを含んでよい。オンライン広告のタイプに応じて、広告特徴は、テキスト、リンク、音声ファイル、ビデオファイル、画像ファイル、実行可能コード、埋め込まれている情報等のうち、１つ以上を含んでよい。
【００３７】
オンライン広告が供給されるときには、該広告がどのようにして、いつ、及び／又はどこで供給されたのかを説明するために、１つ以上のパラメータが使用されてよい。これらのパラメータは以下で「供給パラメータ」と呼ばれる。供給パラメータは、例えば、広告が供給されたページ（上の情報を含む）の特徴、広告の供給と関連付けられた検索クエリー又は検索結果、ユーザ特性（例えば、彼らのジオロケーション、ユーザにより使用されている言語、使用されているブラウザのタイプ、過去のページ表示、過去の動作）、要求を開始したホスト又は関係者のサイト（例えば、アメリカオンライン（Ａｍｅｒｉｃａ Ｏｎｌｉｎｅ）、グーグル（Ｇｏｏｇｌｅ）、ヤフー（Ｙａｈｏｏ））、広告が供給されていたページにおける広告の絶対位置、他の供給される広告を基準にした広告の位置（空間的又は時間的）、広告の絶対サイズ、他の広告を基準にした広告のサイズ、広告の色、他の供給される広告の数、供給される他の広告のタイプ、供給される時刻、広告される曜日（ｔｉｍｅ ｏｆ ｗｅｅｋ）、広告される季節（ｔｉｍｅ ｏｆ ｙｅａｒ）等のうち１つ以上を含んでよい。当然ながら、本発明に関連して使用されてよい、他の供給パラメータもある。
【００３８】
供給パラメータは広告特徴にとって付帯的であってよいが、それらは供給条件又は制約として広告と関連付けられてよい。供給条件又は制約として使用されるとき、このような供給パラメータは単に「供給制約」（つまり「対象設定基準」）と呼ばれる。例えば、いくつかのシステムでは、広告主は、それが平日だけに、特定の位置より下ではなく、特定のジオロケーションのユーザに対してだけ供給されなければならない等を指定することによって、その広告の供給の対象を設定できてよい。別の例として、いくつかのシステムでは、広告主は、ページ又は検索クエリーが特定のキーワード又は句を含む場合にだけ、その広告が供給されなければならないと指定してよい。さらに別の例として、いくつかのシステムでは、広告主が、供給されている文書が特定のトピック又は概念を含む、あるいは特定の１つ以上のクラスタ、又は何らかの他の１つ以上の分類に該当する場合にだけ、その広告が供給されなければならないと指定してよい。「ジオロケーション」情報は、１つ以上の国、１つ以上の（国間の）地方、１つ以上の州、１つ以上の首都圏、１つ以上の都市、１つ以上の町、１つ以上の区、共通の郵便番号が付いた１つ以上の地域、共通の電話局番の付いた１つ以上の地域、共通のケーブル電波中継局により供給される１つ以上の地域、共通ネットワークアクセスポイント又はノードによって供給される１つ以上の領域等のうち１つ以上を指定する情報を含んでよい。それは緯度及び／又は経度、あるいはこれらの範囲を含んでよい。それはユーザの位置が推定できるＩＰアドレス等の情報を含んでよい。
【００３９】
「広告情報」は、このような情報の拡張部（例えば、広告関連情報から引き出された情報）だけではなく、広告特徴、広告供給制約、（「広告導出情報」と呼ばれる）広告特徴又は広告供給制約から引き出すことができる情報、及び／又は（「広告関連情報」と呼ばれる）広告に関連した情報の任意の組み合わせも含んでよい。
【００４０】
「文書」は、コンピュータが解読できる、又はコンピュータが記憶できる任意の作業生産物を含むように広義に解釈されるべきである。文書は、ファイル、ファイルの組み合わせ、他のファイルに対する埋め込みリンクのある１つ以上のファイル等であってよい。ファイルは、テキスト、音声、画像、ビデオ等の任意のタイプであってよい。エンドユーザに表示される文書の部分を、文書の「コンテンツ」と見なすことができる。文書は、コンテンツ（ワード、ピクチャ等）及びそのコンテンツの意味の何らかの表示（例えば、ｅメールフィールド及び関連付けられたデータ、ＨＴＭＬタグ及び関連データ等）の両方を含む、「構造化データ」を含んでよい。文書中の広告スポットは、埋め込まれた情報又は命令によって定義されてよい。インターネットの関連では、共通の文書はウェブページである。ウェブページは多くの場合、コンテンツを含み、（メタ情報、ハイパーリンク等の）埋め込まれた情報、及び／又は（Ｊａｖａ（登録商標）ｓｃｒｉｐｔ等の）埋め込まれた命令を含んでよい。多くのケースでは、文書は一意の、アドレス指定可能な記憶位置を有し、したがってこのアドレス指定可能な位置によって一意に識別できる。ユニバーサルリソースロケータ（ＵＲＬ）は、インターネット上で情報にアクセスするために使用される一意のアドレスである。
【００４１】
「文書情報」は、（例えば、関連情報から引き出される情報等の）このような情報の拡張だけではなく、文書に含まれる任意の情報、（「文書導出情報」と呼ばれる）文書に含まれる情報から引き出すことのできる情報、及び／又は（「文書関連情報」と呼ばれる）文書に関連する情報も含んでよい。文書導出情報の例は、文書のテキストコンテンツに基づいた分類である。文書関連情報の例は、当該の文書がリンクする他の文書からの文書情報だけではなく、当該の文書へのリンクのある他の文書からの文書情報も含む。
【００４２】
「ｅメール情報」は、（例えば、関連情報から引き出される情報等の）このような情報の拡張部だけではなく、（「内部ｅメール情報」と呼ばれることもある）ｅメールに含まれる任意の情報、ｅメール情報に含まれる情報から引き出すことのできる情報、及び／又はｅメールに関連する情報も含んでよい。ｅメール情報から引き出される情報の例は、ｅメールの件名の行から抽出される用語から構成される検索クエリーに応えて返される検索結果から、抽出される、あるいはそれ以外の場合引き出される情報である。ｅメール情報に関連する情報の例は、既定のｅメールの同じ送信者によって送信される１つ以上の他のｅメールについてのｅメール情報、又はｅメール受取人についてのユーザ情報を含む。ｅメール情報から引き出される、あるいはｅメール情報に関連する情報は、「外部ｅメール情報」と呼ばれてよい。
【００４３】
文書からのコンテンツは、「コンテンツレンダリングアプリケーション又はデバイス」で表示されてよい。コンテンツレンダリングアプリケーションの例は、インターネットブラウザ（例えば、エクスプローラ（Ｅｘｐｌｏｒｅｒ）又はネットスケープ（Ｎｅｔｓｃａｐｅ）、メディアプレーヤ（例えば、ＭＰ３プレーヤ、リアルネットワークス（Ｒｅａｌｎｅｔｗｏｒｋｓ）ストリーミング音声ファイルプレーヤ等）、ビューワ（例えば、アドビアクロバット（Ａｄｏｂｅ（登録商標） Ａｃｒｏｂａｔ）ｐｄｆリーダ）等を含む。
【００４４】
「コンテンツオーナ」とは、文書のコンテンツに何らかの所有権を有する人物又はエンティティである。コンテンツオーナはコンテンツの作者であってよい。加えて、又は代わりに、コンテンツオーナは、コンテンツを複製する権利、コンテンツの派生著作物を作成する権利、コンテンツを公に表示する又は実行する権利、及び／又はコンテンツの他の所定の権利を有してよい。コンテンツサーバが、それが供給する文書のコンテンツにおいてコンテンツオーナである可能性があるが、これは必須ではない。
【００４５】
（「ＵＰＩ」とも呼ばれる）「ユーザプロファイル情報」は、個人ユーザ又はユーザのグループについての任意の情報を含んでよい。このような情報は、ユーザによって提供されてよく、ユーザ情報を公開することを許可されているサードパーティによって提供されてよく、及び／又はユーザアクションから引き出されてよい。特定のユーザ情報は、同じユーザの他のユーザ情報及び／又は他のユーザのユーザ情報を使用して演繹又は推測できる。ＵＰＩは多様なエンティティと関連付けられてよい。「ユーザＵＰＩ」は特定のユーザ又はユーザのグループと関連付けられるユーザプロファイル情報である。「文書ＵＰＩ」は、文書と関連付けられるユーザプロファイル情報である。例えば、文書ＵＰＩは、文書を要求した又は文書にアクセスしたユーザの多様なユーザＵＰＩの複合表現であってよい。「広告待ち受けページＵＰＩ」は特定のタイプの文書ＵＰＩであり、おそらく彼らが広告を選択した（例えばクリックした）ことに応じて、ある特定のウェブページにアクセスした、あるいはある特定のウェブページで購入を完了した多様なユーザの複合表現であってよい。「対象設定ＵＰＩ」は、ユーザプロファイル供給制約を含んでよい。例えば、前立腺がん検診のための広告は、属性「男性」及び「年齢４５歳以上」を有するユーザプロファイルに限定される可能性がある。
【００４６】
本発明の多様な例示的な実施形態は、ここで第４．２項に説明される。
【００４７】
第４．２項 例示的な実施形態
第４．２．１項 例示的なユーザ情報
図４は、本発明にしたがった方法でユーザプロファイル情報（ＵＰＩ）を記憶するために使用されてよい、例示的なデータ構造４００である。図示されていないが、そのデータ構造４００は識別子を含んでよい。このような識別子は、ある特定のユーザ、ユーザのグループ、文書、広告、広告待ち受けページ等と、ＵＰＩとを関連付けるために使用されてよい。ＵＰＩは、１つ以上のＵＰＩ属性４２０に関連する情報４１０の１つ以上の集合体を含んでよい。各属性４２０は、関連付けられた値４３０とスコア４４０を有してよい。
【００４８】
ＵＰＩ属性４２０は、例えば、地理情報、年齢又は年齢層、関心のある話題、読書レベル、収入、及び広告の対象を設定するために適した他の人口統計データ等の、ユーザの背景及び関心に関する情報を含んでよい。ＵＰＩ属性４２０と関連付けられた値４３０は、量的（離散値又は連続値、例えば年齢＝５８歳、年収＝５５，０００ドル、居住都市＝サンフランシスコ、カリフォルニア州（Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ）又は質的（集合の中、又は集合の中ではない、例えば、給料が＄５０，０００−＄１００，０００？＝イエス；米国在住か？＝イエス）であってよい。各ＵＰＩ属性４２０及び値４３０は、属性の値が正しい確率に関連する関連スコア４４０を有してよい。ＵＰＩ属性の例は以下の１つ以上を含んでよい。
【００４９】
−ユーザがアクセスした（又は特定の期間内にアクセスした）ウェブサイトのコンテンツ（例えば、ワード、Ａｎｃｈｏｒｔｅｘｔ等）
−人口学的情報、
−地理情報、
−心理情報、
−ユーザが行った過去のクエリー（及び／又は関連情報）、
−ユーザに表示され、選択した、及び／又は見た後に購入した、過去の広告についての情報、
−ユーザによって表示された／要求された及び／又は編集された文書（例えばワードプロセッサ）についての情報、
−ユーザの関心、
−ユーザからの個人的な結果に関する、明示的又は暗示的なフィードバック（例えば、結果を選択する、結果を選択しない、結果に関して費やされる時間の量等）、
−ブラウジング活動、及び、
−過去の購入動作。
【００５０】
このような情報は、個人単位で記憶されてよい（プライバシーの問題から個人識別可能な情報を含まない可能性がある）、あるいは個人の多様な集団の中で種々の方法で集められてよい。このような情報は複合プロファイルを得るために結合されてよい。
【００５１】
第４．２．２項 ＵＰＩを使用するための例示的なアプリケーション
ユーザプロファイル情報（ＵＰＩ）を使用するための多くのアプリケーションがある。３つの例示的なアプリケーション−強化広告対象設定、広告クリエーティブ選択と生成、及びクエリー両義性解決−が後述される。
【００５２】
第４．２．２．１項 ＵＰＩを使用する広告採点
広告の対象設定されたＵＰＩ（及び／又は広告の待ち受けページのＵＰＩ）が文書ＵＰＩに一致する（例えば、文書を要求したユーザの平均的なＵＰＩ）に一致するホストサイト又はページに広告を掲載すること、及び／又はＵＰＩが広告（及び／又は広告の待ち受けページのＵＰＩ）のターゲットＵＰＩに一致するユーザに広告を供給することが望ましい場合がある。
【００５３】
ＵＰＩを使用する強化広告対象を用いると、複数の広告のそれぞれのスコアは、ユーザのＵＰＩ、文書のＵＰＩ、広告待ち受けページのＵＰＩ、及び／又は広告対象設定ＵＰＩの少なくともいくつかを使用して決定されてよい。少なくとも１つの広告は順位で順序付けられ、フィルタリングされ、及び／又は少なくとも決定されたスコアを使用して複数の広告から選択されてよい。
【００５４】
例えば、広告スコアはＵＰＩ一致値の関数であってよい。図５を参照すると、このようなＵＰＩ一致値は、（ｉ）ユーザ（又はユーザグループ）５１２と関連付けられたＵＰＩ情報５１４と、ユーザ５１２によって要求される（又はアクセスされる）文書（例えば、ウェブページ）と関連付けられたＵＰＩ情報５１４との一致値（一致値１）、（ｉｉ）ユーザ（又はユーザグループ）５１２と関連付けられたＵＰＩ情報５１４と、検討中の広告の待ち受けページ５３２と関連付けられたＵＰＩ情報５３４との一致値（一致値２）、（ｉｉｉ）ユーザによって要求される（又はアクセスされる）文書５２２と関連付けられたＵＰＩ情報５２４と、検討中の待ち受けページ５３２と関連付けられるＵＰＩ情報５３４との一致値（一致値３）、（ｉｖ）ユーザ（又はユーザグループ）５１２と関連付けられたＵＰＩ情報５１４と、検討中の広告５４２と関連付けられたＵＰＩ広告対象設定情報５４４との一致値（一致値４）、及び（ｖ）ユーザによって要求される又はアクセスされている文書５２２と関連付けられたＵＰＩ情報５２４と、検討中の広告５４２と関連付けられたＵＰＩ広告対象設定情報５４４の一致値（一致値５）のうち、１つ以上の関数であってよい。
【００５５】
このようにして、本発明の一実施形態では、全体的な一致は以下のように定義されてよい。
【００５６】
ＵＰＩ一致＝ａ＊一致値１＋ｂ＊一致値２＋ｃ＊一致値３＋ｄ＊一致値４＋ｅ＊一致値５
ここで、ａ、ｂ、ｃ、ｄ及びｅは定数である（例えば、ａ＝０．０２５、ｂ＝０．２７５、ｃ＝０．３、ｄ＝０．２、及びｅ＝０．２）。ユーザＵＰＩと文書ＵＰＩの間の一致は、広告にどれか１つがどれほどよく一致するのかには関係ない可能性があるため、「ａ」がゼロに設定されてよいことに留意されたい。多項式又は指数関数を含む他の関数が代わりに使用されてよい。
【００５７】
一般的には、優れた一致のためには、ユーザのＵＰＩはホストページＵＰＩに一致し、おそらくさらに重要なことには、広告待ち受けページのＵＰＩにも一致しなければならない。２つのプロファイルの一致は、ベクトル空間一致等の２つの用語のベクトルを一致させるための標準的な情報検索技法を使用して計算できる（例えば、記事、Ｇ．Ｓａｌｔｏｎ及びＣ．Ｂｕｃｋｌｅｙ、「自動テキスト検索における用語加重手法（Ｔｅｒｍ−Ｗｅｉｇｈｔｉｎｇ Ａｐｐｒｏａｃｈｅｓ ｉｎ Ａｕｔｏｍａｔｉｃ Ｔｅｘｔ Ｒｅｔｒｉｅｖａｌ）」、情報処理及び管理（Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ ａｎｄ Ｍａｎａｇｅｍｅｎｔ）、２４（５）、５１３−５２３ページ（１９８８年）、及びＧｅｒａｒｄ Ｓａｌｔｏｎ、Ａ．Ｗｏｎｇ、Ｃ．Ｓ．Ｙａｎｇ、「自動索引付けのためのベクトル空間モデル（Ａ Ｖｅｃｔｏｒ Ｓｐａｃｅ Ｍｏｄｅｌ ｆｏｒ Ａｕｔｏｍａｔｉｃ Ｉｎｄｅｘｉｎｇ）」、ＡＣＭの通信（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ）、１８（１１）、６１３−６２０ページ（１９７５年）を参照されたい）。
【００５８】
地形、話題、ユーザ年齢範囲、言語等の幅広い属性は、例えば機械学習分類子を使用して文書とユーザについて計算できる。また、このような幅広い属性は、マッチングにおいて単語と句のようなより狭い属性とも一緒に使用できる。
【００５９】
当然、広告のスコアは、例えば、検索クエリーに、又は文書のコンテンツに対するその関連性、既定の結果（例えば、インプレッション、選択、コンバージョン等）について広告主が支払う、あるいは支払う用意がある金額、広告の性能の測度（例えば、クリックスルー率、コンバージョン率、ユーザ定格等）、広告主の品質の測度等の、ＵＰＩ一致に加えて他の要因の関数である場合がある。さらに、異なる中間広告スコアは異なる目的で（例えば、関連性、位置、相対的なレンダリング属性等）使用されてよい。
【００６０】
第４．２．２．２項 ＵＰＩを使用する広告クリエーティブ選択
ＵＰＩを使用する広告クリエーティブ選択及び／又は生成を用いると、広告クリエーティブは（例えば、ユーザ、文書等の）ＵＰＩに合わせて調整されてよい。
【００６１】
第４．２．２．３項 ＵＰＩを使用するクエリー両義性解決
適切な広告つまり広告クリエーティブを選択することに加えて、ＵＰＩは不明瞭な検索用語を含む検索クエリーを明確にするために使用されてよい。例えば、検索クエリー「ジャガー」を提出するユーザは、（Ａ）車ジャガー（Ｊａｇｕａｒ）についての情報、（Ｂ）動物についての情報、（Ｃ）アップルジャガー（Ａｐｐｌｅ Ｊａｇｕａｒ）オペレーティングシステムについての情報、又は（Ｄ）ジャクソンビルジャガー（Ｊａｃｋｓｏｎｖｉｌｌｅ Ｊａｇｕａｒ）ＮＦＬフットボールチームについての情報のどれかを必要とする可能性がある。ユーザのＵＰＩは、「ジャガー」検索用語を明確にするために使用できるであろう。この例では、ユーザの以前のブラウジング活動からの情報が、曖昧なクエリー「ジャガー」を明確にするのに役立つ、あるいはユーザにとってほとんど又はまったく重要ではない広告が表示されないようにしてよい。例えば、ユーザが最近「アップルコンピュータ」と「オペレーティングシステム」についてクエリーを行っており、その後検索クエリー「ジャガー」を提出した場合、ユーザの以前のクエリー履歴は、クエリーがアップル（Ａｐｐｌｅ）コンピュータ用のオペレーティングシステムを参照しており、車、動物又はＮＦＬチームを参照していない可能性が高かった。その結果、広告はこのような情報を利用することによってユーザに対象を設定できるであろう。
【００６２】
他だけではなく、ＵＰＩを使用するためのこれらの前記アプリケーションは、ＵＰＩが入手可能であると仮定する。しかしながら、これが当てはまらない場合、このようなＵＰＩが生成及び／又は更新される必要がある。ＵＰＩを決定する、及び／又は更新するための例示的な方法は、以下の第４．２．３項に説明される。
【００６３】
第４．２．３項 ＵＰＩを決定する、及び／又は更新すること
ユーザプロファイル情報（ＵＰＩ）が、サービスに加入するときにユーザが提供した情報を使用して決定できることを想起されたい。しかしながら、多くのケースでは、ユーザは自らについての情報を進んで開示しない（ｖｏｌｕｎｔｅｅｒ）、あるいは単にこのような情報を進んで開示しないように頼まれる。さらにユーザがたとえこのような情報を進んで開示しても、（例えば、加入の時点で与えられた情報がサービスに必要とされていることに限定されてよく、したがって包括的ではないために）それは不完全である可能性がある、それは意図的に又は無意図的に不正確である可能性がある、それは陳腐になる可能性がある等である。
【００６４】
同様に、ＵＰＩ情報はユーザが要求した、あるいはアクセスしている文書について入手できない可能性がある。
【００６５】
広告は、広告主にＵＰＩ情報を供給させることができるが、このようにすることは広告主にとっては重荷となる可能性がある。
【００６６】
後述されるように、ユーザ、文書等のＵＰＩは、明示的な情報がシステムに与えられていなくても決定できる（あるいは更新できる、あるいは拡張できる）。以下では、初期の（又はベースライン）ＵＰＩが、ブートストラップ段階の間に決定されてよい。このような初期ＵＰＩは、ユーザ又は文書に、あるいはＵＰＩが関連付けられる広告に固有の情報を使用してよい。初期ＵＰＩは、明示的に入力された何らかのＵＰＩ情報を含んでもよいし、含まなくてもよい。
【００６７】
広告採点、広告クリエーティブ選択、クエリー両義性解決等の応用例に、このような初期ＵＰＩ又はベースラインＵＰＩを使用するだけで十分な場合がある。しかしながら、拡大及び／又は強化段階の間に、初期ＵＰＩ又はベースラインＵＰＩを補足することが所望されてよい。例えば図４を参照し直すと、（例えばユーザの、又は文書の、又は広告の、又は広告待ち受けページの）ＵＰＩ４１０は、過去に存在しなかった、又は値を有していなかったかのいずれかである属性４２０に値４３０を追加することによって拡大されてよい。代わりに、又は加えて、ＵＰＩ４１０の属性４２０の値４３０の４４０のスコアは、修正又は強化されてよい。したがって、例えば、値＝男性を有する属性＝性別の確率は、規定の追加情報を増加又は減少してよい。初期ＵＰＩを拡大又は補足するために使用される情報は、推測された情報と見なされてよい。
【００６８】
図６は、本発明にしたがった方法で文書ＵＰＩを決定するために使用されてよい例示的な方法６００のフロー図である。文書のための初期ＵＰＩが決定される。（ブロック６１０）これは、文書コンテンツ等の文書に固有の情報を使用して行われてよい。この行為を実行するための例示的な方法は図８に関して後述される。文書のための追加ＵＰＩ情報が推測される。（ブロック６２０）これは、アクセスしているユーザ、リンクされている文書等から推測される情報を使用して行われてよい。次に、新しい（例えば、拡大された及び／又は強化された）文書ＵＰＩは、初期文書ＵＰＩ及び推測された文書ＵＰＩを使用して決定される。（ブロック６３０）行為６２０と６３０は、方法６００が終了される前に一回以上実行されてよい。（ノード６４０）。行為６２０と６３０が、仮想分岐戻り線によって示されるように繰り返される場合、新しい文書ＵＰＩは、以前の文書ＵＰＩ及びさらに多くの推測文書ＵＰＩを使用して決定されてよい。
【００６９】
図７は、本発明にしたがった方法で（個人又はグループとしての）ユーザＵＰＩを決定するために使用されてよい、例示的な方法７００のフロー図である。ユーザのための初期ＵＰＩが決定される。（ブロック７１０）これはユーザによって提出される過去の検索クエリー等のユーザに固有な情報を使用して行われてよい。この行為を実行するための例示的な方法は図９を参照して後述される。ユーザのための追加のＵＰＩ情報が推測される。（ブロック７２０）これは検索結果、選択された検索結果等から推測される情報を使用して実行されてよい。次に、新しい（例えば、拡大された、及び／又は強化された）ユーザＵＰＩは、初期ユーザＵＰＩ及び推測されたユーザＵＰＩを使用して決定される。（ブロック７３０）行為７２０と７３０は、方法７００が終了される前に一回以上実行されてよい。（ノード７４０）。行為７２０と７３０が、仮想分岐戻り線によって示されるように、繰り返される場合、新しいユーザＵＰＩは、以前のユーザＵＰＩとさらに多くの推測されたユーザＵＰＩを使用して決定されてよい。
【００７０】
図６のブロック６１０から、初期文書ＵＰＩが決定されてよいことを想起されたい。図８は、本発明にしたがった方法で初期ＵＰＩ又はベースライン文書ＵＰＩを決定するために使用されてよい、例示的な方法８００のフロー図である。示されているように、文書ＵＰＩ属性値は（例えば、文書のコンテンツ、文書のメタ情報等を使用して）投入されてよい。（ブロック８１０）
図７のブロック７１０から、初期ユーザＵＰＩが決定されてよいことを想起されたい。図９は、本発明にしたがった方法で初期ＵＰＩ又はベースラインユーザＵＰＩを決定するために使用されてよい、例示的な方法９００のフロー図である。図示されるように、ユーザＵＰＩ属性値は（例えば、ユーザの過去のクエリー情報、ユーザによって明示的に入力される情報等を使用して）投入されてよい（ブロック９１０）。
【００７１】
第４．２．４項 ユーザ情報がどのようにして取得されるのかの例
ユーザ情報を取得する多くの代替方法がある。例えば、属性４２０と値４３０のスコア４４０は、以前に実施されたクエリーの単語を使用して、プロファイルの中のＵＰＩ属性４２０の値４３０を予測する機械学習分類子を用いて決定できる。例えば、以前の検索クエリーの中の「女性の健康」に関連するキーワードを考えると、分類子はユーザが０．８という確率で女性であると推測してよい。さらに、以前の検索クエリーで日本語の単語が使用されたことを考えると、分類子はユーザが０．９の確率で日本人であると推測してよい等である。２つのＵＰＩのスコア４４０は、それらが一致するかどうかに影響を及ぼす可能性がある。属性４２０は、１つのＵＰＩでは「サンフランシスコ」で、もう１つでは「サンホセ」である場合がある。これらの未処理の属性は一致しないが、機械学習分類子は両方のケースで地理的なカテゴリ＝「カリフォルニア」を割り当ててよく、一般化されるプロファイル属性は一致するであろう。したがって、機械学習分類子は、ユーザと文書を、地理、話題、民族性、又は読書レベルに関する幅広いカテゴリに分類するために使用されてよい。
【００７２】
ＵＰＩ情報が推測されてよいことを、図６のブロック６２０と図７の７２０の両方から想起されたい。ユーザＵＰＩは、何らかの方法でユーザと関連付けられる他のユーザ及び／又は文書のＵＰＩから推測されてよい。同様に、文書ＵＰＩは他の文書のＵＰＩから推測されてよい、及び／又はユーザは、文書と何らかの方法で関連付けられてよい。図１０は、ユーザと文書がどのようにして関連付けられるのかを示す。
【００７３】
図１０に示されるように、ユーザ／文書関連動作１０１０は、一人以上のユーザのユーザ情報１０２０、１つ以上の文書の文書情報１０３０、文書リンク（例えば、ウェブトポロジー）情報１０４０、（代わりにユーザ情報１０２０として提供されてよい）ユーザクエリー１０５０の検索結果、及び（代わりにユーザ情報１０３０として提供されてよい）ユーザ文書選択１０６０のうち１つ以上を使用して、ユーザ及び／又は文書（ユーザ対ユーザ、ユーザ対文書、文書対文書、及び／又は（示されているもののような無向グラフでのユーザ対文書の関連と同じであってよい）文書対ユーザ）を関連付ける、情報１０７０を生成してよい。
【００７４】
本発明の例示的な一実施形態では、関連情報１０７０は、ユーザと文書がそれぞれノード１０７２と１０７６として表されるグラフであってよい。図１１は、本発明にしたがった方法でユーザ及び／又は文書を関連付けるために使用されてよい、例示的な方法１１００のフロー図である。図示されるように、ノードは各ユーザと文書に定められてよい。（ブロック１１１０）ユーザノード１０７２のそれぞれに、ユーザが提出した検索クエリーに応えて検索エンジンによって戻された一番上のウェブページのために、（関連を示す）エッジ１０７４がユーザノードと文書ノードの間に描画されてよい。（変形では、エッジ１０７４は、ユーザが選択した（例えばクリックした）ウェブページだけで描画できるであろう）。さらに、エッジ１０７８がそれらの間にリンク（例えばハイパーリンク）を有する文書の組の間に描画されてよい。（ブロック１１２０）図示されていないが、ユーザ対ユーザの関連も生成されてよい。例えば、エッジは同じ文書の１つ以上にアクセスしたユーザ間で追加されてよい。
【００７５】
図７を参照し直すと、このグラフ１０７０を考えると、ユーザのための新しいＵＰＩが、その初期のＵＰＩ、及び推測されたユーザＵＰＩとして、ユーザノード１０７２がリンクされるノード１０７６に対応する文書のＵＰＩを使用して、決定されてよい。同様に、図６を参照し直すと、文書の新しいＵＰＩは、このグラフ１０７０を考えて、その初期のＵＰＩ、及び推測される文書ＵＰＩとして、文書ノード１０７６がリンクされる、それぞれノード１０７２と１０７６に対応するユーザＵＰＩと文書のＵＰＩを使用して、決定されてよい。
【００７６】
本発明の一実施形態において、それぞれ図６と図７のブロック６３０と７３０を参照し直すと、
ｕｐｄａｔｅｄ＿ＵＰＩ＝ｉｎｉｔｉａｌ＿ＵＰＩ＊ａｌｐｈａ＋ｎｅｉｇｈｂｏｒｈｏｏｄ＿ＵＰＩ＊ｂｅｔａ
であり、アルファとベータは定数（例えば、アルファ＝０．７、ベータ＝０．３）であり、ｎｅｉｇｈｂｏｒｈｏｏｄ＿ＵＰＩはグラフ内の近傍のノードのＵＰＩの平均である。ＵＰＩを更新するための他の関数が考えられる。このプロセスは反復を多数回（例えば、５０）繰り返されてよい。
【００７７】
平均ＵＰＩを決定するために、個々の属性４２０の値４３０が平均され、場合によってはスコア４４０で加重されてよい。
【００７８】
さらに多くの離れたノード（例えば、２エッジ以上離れた）も検討されてよいが、より少なく加重されなければならない。
【００７９】
ユーザＵＰＩと文書ＵＰＩの両方とも更新されてよいが、一方又は他方だけを更新することが可能である。
【００８０】
代替実施形態では、ユーザノード１０７２は、ユーザの集団を表してよい。同様に文書ノード１０７６は（例えば、多くのウェブページを含むウェブサイト等）文書の集合体を表してよい。
【００８１】
代替実施形態では、グラフエッジには関連重みが割り当てられる。したがって、例えば、文書がユーザ検索クエリーに応えて返された検索結果リストに単に含まれていた場合より、ユーザが検索結果リストから文書を選択した場合には、ユーザノード１０７２から文書ノード１０７６へのエッジ１０７４には、より大きな重みが与えられてよい。
【００８２】
第４．２．５項 例示的な装置
図１２は、前述された動作の１つ以上を達成してよい機械１２００の高水準ブロック図である（例えば、エンドユーザシステム又はクライアントデバイスによって実行される動作、コンテンツサーバによって実行される動作、検索エンジンによって実行される動作、あるいは広告サーバによって実行される動作）。機械１２００は、基本的に、１台以上のプロセッサ１２１０、１台以上の入力／出力インタフェース装置１２３０、１台以上の記憶装置１２２０、結合された要素の間の情報の通信を容易にするための１つ以上のシステムバス及び／又はネットワーク１２４０を含む。１台以上の入力装置１２３２及び１台以上の出力装置１２３４は、１つ以上の入力／出力インタフェース１２３０と結合されてよい。
【００８３】
該１台以上のプロセッサ１２１０は、本発明の１つ以上の態様を達成するために機械実行可能な命令（例えば、カリフォルニア州パロアルト（Ｐａｌｏ Ａｌｔｏ，Ｃａｌｉｆｏｒｎｉａ）のサンマイクロシステムズ社（Ｓｕｎ Ｍｉｃｒｏｓｙｓｔｅｍｓ Ｉｎｃ．）から入手可能なソラリス（Ｓｏｌａｒｉｓ）オペレーティングシステム、あるいはノースカロライナ州ダーハム（Ｄｕｒｈａｍ，Ｎｏｒｔｈ Ｃａｒｏｌｉｎａ）のレッドハット社（Ｒｅｄ Ｈａｔ，Ｉｎｃ．）等の多くのベンダから広範囲に入手可能なリナックス（登録商標）（Ｌｉｎｕｘ（登録商標））オペレーティングシステムで実行する、Ｃ又はＣ＋＋）を実行してよい。機械実行可能命令の少なくとも一部は、該１台以上の記憶装置１２２０上に（一時的に、又はより恒久的に）記憶されてよい、及び／又は１台以上の入力インタフェース装置１２３０を介して外部ソースから受け取られてよい。
【００８４】
一実施形態では、機械１２００は１台以上の従来のパーソナルコンピュータであってよい。このケースでは、該処理装置１２１０は１台以上のマイクロプロセッサであってよい。該バス１２４０はシステムバスを含んでよい。該記憶装置１２２０は、読み取り専用メモリ（ＲＯＭ）及び／又はランダムアクセスメモリ（ＲＡＭ）等のシステムメモリを含んでよい。記憶装置１２２０は、ハードディスクに読み書きするためのハードディスクドライブ、（例えばリムーバブル）磁気ディスクに読み書きするための磁気ディスクドライブ、及びコンパクトディスク又は他の（磁気）光学媒体等のリムーバブル（磁気）光学ディスクに読み書きするための光学ディスクドライブを含んでよい。
【００８５】
ユーザは、例えば、キーボードとポインティングデバイス（例えばマウス）等の入力装置１２３２を通して、パーソナルコンピュータにコマンドと情報を入力してよい。マイク、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ等の他の入力装置もまた、（あるいは代わりに）含まれてよい。これらの及び他の入力装置は多くの場合、システムバス１２４０に結合されている適切なインタフェース１２３０を通して処理装置（複数の場合がある）１２１０に接続されている。出力装置１２３４は、適切なインタフェースを介してシステムバス１２４０にも接続されてよいモニタ、又は他のタイプのディスプレイ装置を含んでよい。モニタに加えて（あるいは代わりに）パーソナルコンピュータは、例えばスピーカ及びプリンタ等の他の（周辺）出力装置（図示せず）を含んでよい。
【００８６】
第４．３項 改良版及び代替策
第４．３．１項 決定技法
マッチング（つまり類似性）決定は、多くの方法で実行できる。例えば、以下の類似性決定技法の１つ以上が使用されてよい。（ａ）（例えば後述されるような）ベクトルベース、（ｂ）（例えば後述されるような）規則ベース、（ｃ）一致の確率又は尤度を推測するための確率的推論、及び（ｄ）ファジー論理マッチングである。他の類似性技法は、本発明の元でも使用されてよい。
【００８７】
上で触れたように、類似性を決定する１つの方法はＵＰＩベクトルを形成することである。複数の広告のそれぞれは代表的な対象設定ＵＰＩベクトルを有してもよい。このようなＵＰＩベクトルは、履歴データから決定される追加情報も含んでよいことに留意されたい。例えば、どの人口グループがある広告をクリックする傾向があるかについての推論は、データマイニング技法を使用して決定されてよい。この（例えばオフラインの）分析の結果は、次に広告のＵＰＩ対象設定ベクトルの１つ以上の属性として使用されてよい。ＵＰＩベクトルは、ベクトル間のコサイン距離、ハミング距離、及び／又は種々の他のベクトル距離基準等の採点関数を使用して一致できる。次に広告は、このような関数により生じるスコアを使用して（例えばスコアに従って）ランクを付けることができる。
【００８８】
また前記に示されたように、ＵＰＩをマッチさせるための別の技法は、ユーザＵＰＩ、文書ＵＰＩ、広告ＵＰＩ、及び広告待ち受けページＵＰＩの１つ以上の組の類似性を定める規則及び／又は関数の集合を適用することを含む。このような規則及び／又は式をベースにしたシステムは、加重スコアを出すために（例えば、加重して）論理規則の任意の組み合わせを使用できる。
【００８９】
このように、ベクトルベースの技法及び規則及び／又は公式ベースの技法は、一致決定を生成するためにいっせいに使用されてよい。
【００９０】
本発明の一実施形態では、属性頻度−反転文書（又はユーザ）頻度積（ａｔｔｒｉｂｕｔｅ ｆｒｅｑｕｅｎｃｙ−ｉｎｖｅｒｓｅ ｄｏｃｕｍｅｎｔ（ｏｒ ｕｓｅｒ）ｆｒｅｑｕｅｎｃｙ ｐｒｏｄｕｃｔ）（ＴＦ−ＩＤＦ）基準は、類似性スコアを生じさせるためにＵＰＩを使用して決定される。
【００９１】
第４．３．１．１項 類似性決定技法の改良版
ＵＰＩを一致させるプロセスを効率的に保つために、属性選択、属性汎用化及び／又は属性集約の技法が、比較されているベクトルのサイズを縮小するために使用されてよい。例えば、属性選択は、ＵＰＩの間の一致プロセスの一部として使用される属性の数及び／又はサイズを削減するために使用されてよい。このような属性選択技法は、（絶対項及び／又は相対項の中で）高いスコア（例えば、確率又は重要性重み）を有する何らかの数の属性だけを、ＵＰＩのベクトル表現で保つことを含んでよい。別の属性選択技法は、うまく機能する（例えばクリックされる）可能性が高い１つ以上の一致を生成するために、他よりどの属性がより指標となるかを決定するために、「相互情報」、カイ二乗適合（Ｃｈｉ−ｓｑｕａｒｅｄ ｆｉｔ）、又は例えば相関等の、統計基準を使用することを含んでよい。さらに別の属性選択技法は、最も有用であると考えられるそれらの属性を単に手作業で選択することである。これらの又は他の属性選択技法の２つ以上がいっせいに使用されてよい。
【００９２】
同様に、ＵＰＩベクトルは、残っている広告ＵＰＩベクトルの小さい部分集合だけがユーザＵＰＩと文書ＵＰＩに関してランク付けされる必要があるように、（例えば、特定の特徴を正確に一致させる等の）何らかの初期基準の集合を使用して、前置フィルタにかけられてよい。この技法は、結合された規則ベースの類似性決定技法と、ベクトル距離類似性決定技法を示している。この技法を使用すると、ＵＰＩ間の全体的な一致プロセスの効率を高めるのに役立つという追加の利点がある。
【００９３】
例えば、ユーザ及び／又は文書に関連性のある１つ以上の広告の第１の集合が先に決定されてよい。１つ以上の広告の第１の集合は広告の最終的な集合を決定するためにＵＰＩ情報動作をさらに使用して処理されてよい（例えば、ＵＰＩを使用して決定される第２の類似性スコアに基づいて順序付けられる、及び／又はフィルタリングされる）。このような実施形態は、ＵＰＩ（の一部）がクライアントに記憶されるときに有用であり得る。例えば、広告サーバは、ユーザ要求（例えば検索クエリー又は文書要求）のために上位Ｎの（例えばＮ＝１００）の広告をクライアントに送信してよい。クライアントは、次にこれらの供給された広告に、ローカルユーザ情報に基づいて順序を付け直すことができる。
【００９４】
第４．３．２項 どのように及びどこにＵＰＩが記憶されるのかの例
本発明の一実施形態では、ＵＰＩは、関連付けられたソース（例えば、ｎグラムは表示されるウェブページ、クエリー等からである）、ＵＲＬ、又は異なる種類の情報（例えば、ユーザは特定のウェブブラウザを使用している、あるいはユーザは特定の緯度と軽度に位置している等）の特定の値が付いた、ｎグラム（長さ１からほぼ最大、例えば３までの単語のシーケンス）として記憶される。
【００９５】
ＵＰＩの記憶及び使用は、（ａ）（例えば、ブラウザクッキー、ローカルファイル、非表示形式フィールド、又はＵＲＬ符号化等の形をとる）クライアント側記憶装置、（ｂ）（例えば、プロファイル／動作情報を記憶し、検索するための記録のデータベース、フラットファイル、又は独自仕様の構造等の）サーバ側記憶装置、及び／又は（ｃ）サードパーティの記憶装置を含む、多様な異なる形式を取ってよい。このようにして、ＵＰＩはサーバ側のレポジトリに常駐する必要はないが、実際にはクライアント及び／又はサードパーティで記憶され、ユーザの要求とともに情報サーバに送信されてよい（例えば、検索クエリー又は文書要求）。ＵＰＩは例えば、ウェブブラウザクッキーで送信できる。
【００９６】
図３の例示的なネットワーク環境を参照し直すと、ＵＰＩは、１台以上のクライアントデバイス３２０、１台以上のコンテンツサーバ３３０、１つ以上の検索エンジン３４０、１台以上の広告サーバ３５０、及び／又は１台以上のユーザ情報サーバ３６０に記憶されてよい。いずれにせよ、ユーザ情報は、何らかのデータ管理方式（例えば、データベース、フラットファイル、独自仕様データ管理システム、ウェブブラウザクッキー等）を使用することにより保持されてよい。ユーザ情報のさまざまな項目（例えば異なるユーザ特徴）がさまざまなデバイスに記憶されてよい。
【００９７】
第４．３．２．１項 情報記憶に対する改良版
実践的なシステムを達成するために、対象設定広告で使用されるＵＰＩの量を削減する、及び／又はＵＰＩを順序付けることが所望されるようになる、又は必要になる。本発明は、情報と精度の最小限の損失でこのような削減を可能にする。さらに、広告の供給における、ひいてはＵＰＩの検索における待ち時間を制約することが、望ましい又は必要である可能性があるので、広告サーバは限られたＵＰＩで、あるいはＵＰＩなしで動作する必要がある場合もある。本発明にしたがった方法で優先順位を設定することにより、広告サーバは対象設定プロセス中に使用可能な貴重な（例えば最も貴重な）情報に焦点を当てることができる。データ削減及び処理優先順位の設定のための例示的な技法が後述される。
【００９８】
本発明の一実施形態では、少なくともいくつかのＵＰＩ属性のそれぞれが、関連付けられたスコア（重要性重み、確率等）を有する。複数のＵＰＩ属性の重要性重みは、何らかの方法でともに分類されるあるいは集約されてよい。
【００９９】
当初、ＵＰＩ属性に割り当てられる重要性重みは、おそらく特に一種の情報を使用して決定されてよい。例えば、検索クエリーは、ユーザが表示したウェブページから抽出されるｎグラムより高い初期重みを有してよい。
【０１００】
ＵＰＩ属性の重要性重みは、特定のユーザの、又はユーザのグループのアクションに基づいて更新されてよい。例えば、（参照してここに組み込まれ、「第７９１号出願」と呼ばれる）２００３年６月２日に出願された、Ｓｔｅｖｅ Ｌａｗｒｅｎｃｅ、Ｍｅｈｒａｎ Ｓａｈａｍｉ及びＡｍｉｔ Ｓｉｎｇｈａｌを発明者として示す「ユーザ要求情報とユーザ情報を使用して広告を供給すること（ＳＥＲＶＩＮＧ ＡＤＶＥＲＴＩＳＥＭＥＮＴＳ ＵＳＩＮＧ ＵＳＥＲ ＲＥＱＵＥＳＴ ＩＮＦＯＲＭＡＴＩＯＮ ＡＮＤ ＵＳＥＲ ＩＮＦＯＲＭＡＴＩＯＮ）」と題される米国特許出願第１０／４５２，７９１号の図９は、本発明にしたがった方法で広告ＵＰＩ又はユーザＵＰＩを管理するために使用されてよい例示的な方法を示す。例えば、その例示的な方法では、ユーザが広告を選択すると、推奨されているこの広告につながったユーザＵＰＩ属性の重要性重みが増加してよい。重要性重み（複数の場合がある）が増す量（絶対又は相対）は、各ＵＰＩ属性が広告推奨スコアにどの程度貢献したのかに少なくとも部分的に依存してよい。同様に、関連性のあるＵＰＩ属性の重要性重みは、ユーザが広告を選択しないときには削減されてよい。本発明の一実施形態では、重み削減係数は重み増加係数より小さい。
【０１０１】
本発明の一実施形態では、重要性重みは随意的に、ＵＰＩ属性が全ユーザ全体で（絶対的及び／又は相対的に）どの程度頻繁に優れた推奨策を生じさせたのかに基づいて大局的な重みを使用して（例えば結合されて）調整されてよい。代わりに、又は加えて、重要性重みは、ＵＰＩ属性が随意的に（例えばすべての類似した）ユーザのグループ全体で（絶対的に及び／又は相対的に）どの程度頻繁に優れた推奨策を生じさせたのかに基づいて、同一性重みを使用して（例えば結合されて）調整されてよい。
【０１０２】
本発明の一実施形態では、ＵＰＩは特定のサイズに達すると、それは少なくとも重要性重みを使用して情報のあまり重要でない項目を削除することによって削減されてよい。ＵＰＩ属性の記憶要件も検討されてよい。このようにして、多くの記憶域を必要とするが、低い重要性重みを有するＵＰＩ属性は削除の第一の候補となるであろう。
【０１０３】
本発明の一実施形態は、個々のＵＰＩ属性をその重要性重みを使用して順序付けることが（そして記憶することも）できる。このような実施形態では、既定のユーザＵＰＩに対する要求は（重要性重みという点で）最も重要な属性だけを含む不完全なＵＰＩを供給されることがある、あるいは十分な情報が取得されるまで、及び／又は追加の処理が望ましくない又は可能ではなくなるまで断片的に供給されてよい。したがって、例えば、ＵＰＩ属性を使用して処理することは、その重要性重みの順序で行われてよい。これにより、（例えば、効率のために、何らかの待ち時間制約を満たし、処理が特定の期限内に完了されることを確実にするために等）処理を早期に終了することができる。
【０１０４】
新しいＵＰＩ属性が追加されるにつれ、既存の属性の重要性重みが変更される可能性がある。その結果、（例えば既定のユーザの）ＵＰＩ属性の順序は重要性重み順序と異なる可能性がある。したがって、本発明は、それぞれの重要性重みを使用して（例えば、これに従って）ＵＰＩ属性を周期的に順序付けし直すために使用されてよい。
【０１０５】
いくつかのケースでは、ＵＰＩの転送又は処理は、（例えば既定のユーザの）ＵＰＩが重要性重みを使用して（例えば、これに従って）順序付け直される前に概算の順序で実行されてよい。少なくともいくつかの例及び／又はいくつかの実施形態では、その順序で効率的に転送及び／又は処理されるこのような情報のそれぞれの重要性重みの順序で、ＵＰＩ属性を物理的に記憶することが必要ではない可能性があることに留意されたい。実際に、少なくともいくつかの例及び／又はいくつかの実施形態では、重要性順序でＵＰＩ属性を転送する及び／又は処理することが必要ではない可能性がある。例えば、条件によっては、すべての情報は転送される、及び／又は処理されてよい。
【０１０６】
第４．４項 結論
前記開示から理解できるように、本発明はキーワード対象設定広告システムだけではなく、コンテンツ対象設定広告システムも改善するために使用できる。ユーザ、文書、広告及び／又は広告待ち受けページのユーザプロファイル情報は、受け入れることができる、及び／又は推測できる。
【技術分野】
【０００１】
本発明は広告に関する。特に、本発明は、例えば検索クエリー又は文書要求等のユーザの要求に役立つための、特に関連性のある広告又は広告クリエーティブ（ｃｒｅａｔｉｖｅｓ）を決定することに関する。
【背景技術】
【０００２】
テレビ、ラジオ、新聞及び雑誌等の、従来の媒体を使用する広告は周知である。残念なことに、人口学的な研究及び多様な報道発信源の典型的な視聴者についてのまったく妥当な前提で準備していても、広告主は自分の広告予算の大半が単に無駄にされていることを認識している。さらに、このような無駄を特定し、排除することは非常に困難である。
【０００３】
最近では、より双方向性の媒体での広告が一般的になってきた。例えば、インターネットを使用する人の数が爆発的に伸びるにつれ、広告主はインターネット上で提供される媒体とサービスを、広告を行うための潜在的に強力な方法として捉えるようになった。
【０００４】
広告主は、このような広告の価値を最大限にする目的で複数の戦略を作成してきた。１つの戦略では、広告主は、（一般性を失うことなく本明細書中で「ウェブサイト」と呼ばれる）双方向性の媒体又はサービスを提供するための一般的な存在又は手段を、多数の消費者へのパイプとして使用する。この第１の手法を使用して、広告主は、例えばニューヨークタイムズのウェブサイト（Ｎｅｗ Ｙｏｒｋ Ｔｉｍｅｓ Ｗｅｂｓｉｔｅ）又はＵＳＡトゥデイのウェブサイト（ＵＳＡ Ｔｏｄａｙ Ｗｅｂｓｉｔｅ）のホームページ上に、広告を掲載してよい。別の戦略では、広告主はより狭いニッチ視聴者をその広告の対象とし、それにより視聴者の前向きの反応の尤度を高めようと試みる可能性がある。例えば、コスタリカの熱帯雨林での観光を奨励している官庁は、ヤフー（登録商標）ウェブサイト（Ｙａｈｏｏ Ｗｅｂｓｉｔｅ）のエコツーリズム−旅行のサブディレクトリに広告を掲載する可能性がある。広告主は通常はこのような対象の設定を手作業で決定する。
【０００５】
戦略に関係なく、ウェブベースの広告（「ウェブ広告」とも呼ばれる）は、通常、「バナー広告」−つまり、グラフィック要素を含む矩形のボックス−の形で、その広告視聴者に提示される。広告視聴者の一員（一般性を失うことなく本明細書中では「視聴者」又は「ユーザ」と呼ばれる）が、これらのバナー広告のうち１つをクリックすることにより選択すると、通常、埋め込まれているハイパーテキストリンクが視聴者を広告主のウェブサイトに案内する。視聴者が広告を選択するこのプロセスが、一般的に「クリックスルー」（「クリックスルー」は、任意のユーザの選択をカバーすることを目的としている）と呼ばれている。広告のインプレッション数（つまり広告が表示される回数）に対するクリックスルー数の割合が、一般的に広告の「クリックスルー率」と呼ばれる。
【０００６】
ユーザが過去に供給された広告に関連したトランザクションを完了すると、「コンバージョン」が発生すると言われている。コンバージョンを構成している内容は場合によって異なり、種々の方法で決定できる。それは例えば、ユーザが広告主のウェブページと呼ばれる広告をクリックし、そのウェブページを離れる前にそこで購入を完了すると、コンバージョンが発生するケースである可能性がある。代わりに、コンバージョンは、ユーザが広告を見てから、所定の時間（例えば７日間）内に広告主のウェブページで購入することとして定義される場合がある。さらに別の代替策では、コンバージョンは、例えばホワイトペーパーをダウンロードする、ウェブサイトの少なくとも既定の深部まで進む、少なくとも特定数のウェブページを表示する、ウェブサイト又はウェブページで少なくとも所定の時間量を費やす、ウェブサイトで登録する等の、測定可能／観察可能なユーザアクションであるとして、広告主に定義されてよい。コンバージョンを構成するユーザアクションはこれに限られていないが、多くの場合、ユーザアクションが購入の完了を示さない場合、それらが販売の手がかりを示すことがある。実際に、何がコンバージョンを構成するのかについて、他の多くの定義が考えられる。広告インプレッション数（つまり広告が表示される回数）に対するコンバージョン数の割合は、一般にはコンバージョン率と呼ばれる。コンバージョンが広告が供給されてから所定の時間内に発生し得ると定義される場合、コンバージョン率の１つの考えられる定義が、過去の所定の時間より多く供給された広告を考慮するにすぎない可能性がある。
【０００７】
ウェブサイトベースの広告の当初の展望にも関わらず、既存の手法にはいくつかの問題が残されている。広告主は大きな客層に到達できるが、しばしば自分の広告投資からの収益に満足していない。
【０００８】
同様に、（「ウェブサイトホスト」、又は「広告消費者」と呼ばれる）広告が提示されるウェブサイトホストは、ユーザの経験を損なうことなく広告収入を最大限にするという課題を抱えている。ユーザの利益を超えて広告収入を位置づけるウェブサイトホストもいる。このような１つのウェブサイトが、ユーザのクエリーに応えて「検索結果」を装う広告を返すいわゆる「検索エンジン」サービスを主催する「Ｏｖｅｒｔｕｒｅ．ｃｏｍ」である。Ｏｖｅｒｔｕｒｅ．ｃｏｍウェブサイトは、広告主が金を支払って、検索結果と称するもののリストの上の方に自分のウェブサイト（又は対象のウェブサイト）の広告を配置できるようにしている。ユーザが広告をクリックした場合にだけ広告主が支払いをする（つまりコストパークリック）ような方式が実現されている場合、対象設定がうまく行われていない広告はクリックされず、したがって支払いを必要としないために、広告主は自らの広告の対象を効果的に設定する意欲をなくしてしまう。その結果、高いコストパークリックの広告がトップの近くに、又はトップに表示されるが、視聴者はそれらをクリックしないため、必ずしも広告発行元にとっての本当の収入にはならない。さらに、視聴者がクリックするであろう広告は、リストのさらに下のほうにある、あるいはリストには載っていないために、広告の関連性は損なわれる。
【０００９】
例えばグーグル（登録商標）（Ｇｏｏｇｌｅ（登録商標））等の検索エンジンは、広告主が自らの広告が検索結果のページとともに表示されるように、及びそれらが検索結果ページを表示するように指示したクエリーにおそらく関連性があるように、広告の対象を設定できるようにした。ｅ−メール情報に基づいて広告の対象を設定するもの（例えば、２００３年６月２日に出願された、Ｊｅｆｆｒｅｙ Ａ．Ｄｅａｎ、Ｇｅｏｒｇｅｓ Ｒ．Ｈａｒｉｋ及びＰａｕｌ Ｂｕｃｈｅｉｔを発明者として示す「Ｅメールに関連した情報を使用して広告を提供すること（ＳＥＲＶＩＮＧ ＡＤＶＥＲＴＩＳＥＭＥＮＴＳ ＵＳＩＮＧ ＩＮＦＯＲＭＡＴＩＯＮ ＡＳＳＯＣＩＡＴＥＤ ＷＩＴＨ Ｅ−ＭＡＩＬ）」と題される（参照してここに組み込まれる）米国特許出願第１０／４５２，８３０号に説明されているシステム）、あるいはコンテンツに基づいたターゲット広告（２００３年２月２６日に出願された、Ｄａｒｒｅｌ Ａｎｄｅｒｓｏｎ、Ｐａｕｌ Ｂｕｃｈｅｉｔ、Ａｌｅｘ Ｃａｒｏｂｕｓ、Ｃｌａｉｒｅ Ｃｕｉ、Ｊｅｆｆｒｅｙ Ａ．Ｄｅａｎ、Ｇｅｏｒｇｅｓ Ｒ．Ｈａｒｉｋ、Ｄｅｅｐａｋ Ｊｉｎｄａｌ及びＮａｒａｙａｎａｎ Ｓｈｉｖａｋｕｍａｒを発明者として示す「コンテンツに基づいて広告を供給すること（ＳＥＲＶＩＮＧ ＡＤＶＥＲＴＩＳＥＭＥＮＴＳ ＢＡＳＥＤ ＯＮ ＣＯＮＴＥＮＴ）」と題される（参照してここに組み込まれる）米国特許出願第１０／３７５，９００号を参照されたい）等の、他の対象が設定された広告システムも、同様の課題を抱えている可能性がある。すなわち、広告システムは、ユーザ要求情報に概して関連性のある、特に現在のユーザの関心に関係する広告を提示しようとする。
【００１０】
前記から理解できるように、キーワード対象設定（ｋｅｙｗｏｒｄ−ｔａｒｇｅｔｅｄ）広告又はコンテンツ対象設定（ｃｏｎｔｅｎｔ−ｔａｒｇｅｔｅｄ）広告等の対象設定広告システムは、非常に有用な形式の広告を提供する。ただし、通常、関連性のある広告を供給できるオンライン広告システムも、多くの場合、特定のユーザに最も適した関連性のある広告を選択することはできない。
【００１１】
したがって、オンライン広告の性能を改善する必要性がある。さらに具体的には、要求を提出したユーザに対する、例えば検索クエリー又は文書要求等の、何らかのユーザ要求のために供給される広告の関連性を高める必要性がある。
【発明の概要】
【００１２】
本発明は、広告を採点するために使用される一致を決定するための方法及び装置を説明する。このような方法及び装置は、（ａ）（ｉ）広告の広告待ち受けページのユーザプロファイル情報及び／又は広告の対象を設定するために使用されるユーザプロファイル情報、及び（ｉｉ）広告が表現される先のユーザのユーザプロファイル情報を使用して、第１の一致値を求めてよく、（ｂ）（ｉ）広告の待ち受けページのユーザプロファイル情報及び／又は広告の対象を設定するために使用されるユーザプロファイル情報、及び（ｉｉ）広告が供給される文書のユーザプロファイル情報を使用して、第２の一致値を求めてよく、（ｃ）第１の一致値と第２の一致値を使用して広告を採点するために使用される一致を決定してよい。
【００１３】
本発明は、前記のような方法及び装置において、あるいはユーザプロファイル情報を使用して広告の対象を設定するための他の方法及び装置において、広告の広告待ち受けページのユーザプロファイル情報の少なくとも一部、広告の対象設定に使用されるユーザプロファイル情報の少なくとも一部、ユーザのユーザプロファイル情報の少なくとも一部、及び／又は文書のユーザプロファイル情報の少なくとも一部が、推測されてよいことも教示する。
【００１４】
本発明の一実施形態では、ユーザのためのユーザプロファイル情報は、（ａ）ユーザのために初期ユーザプロファイル情報を決定すること、（ｂ）ユーザのためにユーザプロファイル情報を推測すること、及び（ｃ）初期ユーザプロファイル情報と推測されたユーザプロファイル情報の両方を使用して、ユーザのためのユーザプロファイル情報を決定することによって、決定されてよい。ユーザのための初期ユーザプロファイル情報は、ユーザによって提出された過去の検索クエリー、及び／又はユーザによる過去の文書の選択を使用して決定されてよい。
【００１５】
本発明の一実施形態では、ユーザのためのユーザプロファイル情報は、（ａ）多くの文書のそれぞれとユーザのためのノードを定義すること、（ｂ）グラフを定義するためにノード間に関連がある場合にノード間でエッジを追加すること、及び（ｃ）グラフのトポロジー及び他の文書のユーザプロファイル情報を使用してユーザのためのユーザプロファイル情報を推測することによって、推測されてよい。
【００１６】
本発明の一実施形態では、文書のためのユーザプロファイル情報は、（ａ）文書のための初期ユーザプロファイル情報を決定すること、（ｂ）文書のためのユーザプロファイル情報を推測すること、及び（ｃ）初期ユーザプロファイル情報と推測されたユーザプロファイル情報の両方を使用して、文書のためのユーザプロファイル情報を決定することによって、決定されてよい。文書のための初期ユーザプロファイル情報は、文書からのコンテンツ情報、及び／又は文書メタ情報を使用して決定されてよい。
【００１７】
本発明の一実施形態では、文書のためのユーザプロファイル情報は、（ａ）多くの文書のそれぞれのための、及び多くのユーザのそれぞれのためのノードを定義すること、（ｂ）グラフを定義するためにノード間に関連がある場合にノード間にエッジを追加すること、（ｃ）グラフのトポロジー、及びユーザの、及び他の文書のユーザプロファイル情報を使用して文書のためのユーザプロファイル情報を推測することによって、推測されてよい。
【図面の簡単な説明】
【００１８】
【図１】広告システムと対話できる関係者又はエンティティを示す高水準図である。
【図２】本発明が中で又は用いて動作してよい、例示的な広告環境のバブルチャートである。
【図３】図２に示されたようなオンライン広告環境の中で、あるいは図２に示されたようなオンライン広告環境を用いて使用されてよい、本発明にしたがった動作のバブルチャートである。
【図４】本発明にしたがった方法で生成され、更新され、及び／又は使用されてよい、ユーザプロファイル情報を記憶するための、例示的なデータ構造を示す。
【図５】広告スコア（ｓｏｒｅ）の係数であってよい全体的な一致値の考えられる成分を示す。
【図６】本発明にしたがった方法で文書ＵＰＩを決定するために使用されてよい、例示的な方法６００のフロー図である。
【図７】本発明にしたがった方法でユーザＵＰＩを決定するために使用されてよい、例示的な方法７００のフロー図である。
【図８】本発明にしたがった方法で初期のＵＰＩ又はベースライン文書ＵＰＩを決定するために使用されてよい、例示的な方法８００のフロー図である。
【図９】本発明にしたがった方法で初期のＵＰＩ又はベースラインユーザＵＰＩを決定するために使用されてよい、例示的な方法９００のフロー図である。
【図１０】ユーザと文書がどのように関連付けられるのかを示す。
【図１１】本発明にしたがった方法でユーザ及び／又は文書を関連付けるために使用されてよい、例示的な方法１１００のフロー図である。
【図１２】実行されてよい多様な動作の少なくともいくつかを達成するために、及び本発明にしたがった方法で使用及び／又は生成されてよい情報を記憶するために、使用されてよい装置のブロック図である。
【発明を実施するための形態】
【００１９】
本発明は、ユーザプロファイル情報を決定し、このような決定されたユーザプロファイル情報を広告供給のために使用するための、新規の方法、装置、メッセージフォーマット、及び／又はデータ構造を含んでよい。以下の説明は、当業者が本発明を作り、使用できるようにするために提示され、特定の応用例及びそれらの要件との関連で提供される。開示される実施形態に対する多様な変形は当業者に明らかとなり、以下に述べられる一般的な原則は他の実施形態及び応用例に適用されてよい。したがって、本発明は示されている実施形態に制限されることを意図せず、発明者は自らの発明を、説明されている任意の特許性がある主題と見なす。
【００２０】
広告対象設定を改善するための１つの考えられる方法は、広告対象設定システムがユーザプロファイルを取得し、使用することである。例えば、ユーザプロファイルは、（例えばユーザがサービスに加入しているとき等）ユーザが自発的に与える情報を使用して決定されてよい。このユーザ属性情報は、次に広告の広告主指定属性（例えば対象設定基準）と突き合わされてよい。残念なことに、多くのウェブサイト（例えば検索エンジン）は加入又はユーザ登録を必要としないため、ユーザプロファイル情報は必ずしもいつも入手できない。さらに、たとえ入手できるときも、ユーザプロファイルは不完全である場合がある（例えば、加入時に与えられる情報は、プライバシーの考慮等のためにサービスに必要とされるものに限定され、したがって包括的ではない可能性があるからである）。さらに、広告主はユーザプロファイル対象設定情報を手作業で設定する必要がある場合がある。さらに、ユーザプロファイル情報が入手できる場合でも、広告主が効果的に広告の対象を設定するためにこの情報を使用できない可能性がある。
【００２１】
以下では、本発明が中で動作してよい環境、又は本発明が用いて動作してよい環境が第４．１項に説明される。本発明の例示的な実施形態は第４．２項に説明される。いくつかの代替策及び改良版は第４．３項に説明される。最後に、本発明に関するいくつかの結論は第４．４項に述べられている。
【００２２】
第４．１項 本発明が中で動作してよい、又は本発明が用いて動作してよい環境
第４．１．１項 例示的な広告環境
図１は、広告環境の高水準図である。該環境は広告入力保持及び配信システム１２０を含んでよい。広告主１１０は、システム１２０に広告情報を直接的に又は間接的に入力、保持、及び追跡調査してよい。広告は、いわゆるバナー広告等のグラフィック広告、テキストのみの広告、画像広告、音声広告、ビデオ広告、このような構成要素のうち１つ以上（ｏｎｅ ｏｆ ｍｏｒｅ）を組み合わせた広告の形をとってよい。広告は、リンク等の埋め込まれた情報、及び／又は機械実行可能な命令を含んでもよい。広告消費者１３０は、彼らの要求に応える広告をシステム１２０から受け入れ、システム１２０に使用情報を提供するために、広告に対する要求を提出してよい。図示されていないが、他のエンティティは、システム１２０に（広告と関連したコンバージョン又はクリックスルーが発生したかどうか等の）使用情報を提供してよい。この使用情報は、供給された広告に関連した、測定された又は観察されたユーザ動作を含んでよい。
【００２３】
広告消費者１３０の１つの例は、コンテンツ（例えば、記事、議論スレッド、音楽、ビデオ、グラフィックス、検索結果、ウェブページのリスト等）に対する要求を受信し、要求に応えて要求されたコンテンツを取り出す、あるいはそれ以外の場合提供する、一般コンテンツサーバである。コンテンツサーバは、システム１２０に広告に対する要求を提出してよい。このような広告要求は、所望される多くの広告を含んでよい。広告要求はまた、コンテンツ要求情報を含んでよい。この情報は、コンテンツ自体（例えばページ）、コンテンツ又はコンテンツ要求に対応するカテゴリ（例えば、アート、ビジネス、コンピュータ、アート−映画、アート−音楽等）、コンテンツ要求の一部又はすべて、コンテンツ寿命、コンテンツタイプ（例えば、テキスト、グラフィックス、ビデオ、音声、混合媒体等）、ジオロケーション情報等を含んでよい。
【００２４】
コンテンツサーバは、システム１２０によって提供される広告の１つ以上と、要求されたコンテンツを組み合わせてよい。コンテンツと広告（複数の場合がある）を含むこの組み合わされた情報は、次に、ユーザに提示するために、コンテンツを要求したエンドユーザに向かって転送される。最後に、コンテンツサーバは広告に関する情報、及びどのようにして、いつ、及び／又はどこで広告を表示しなければならないのか（例えば、場所、クリックスルーか否か、インプレッション時間、インプレッション日付、サイズ、コンバージョンか否か等）についての情報を、システム１２０に送り返してよい。代わりに、又はさらに、このような情報は何らかの手段によってシステム１２０に提供し直されてよい。
【００２５】
広告消費者１３０の別の例が検索エンジンである。検索エンジンは検索結果のためのクエリーを受け取ってよい。それに応じて、検索エンジンは関連する検索結果を（例えばウェブページのインデックスから）取り出してよい。例示的な検索エンジンは、Ｓ．Ｂｒｉｎ及びＬ．Ｐａｇｅの記事、「大規模ハイパーテキスト検索エンジンの解剖（Ｔｈｅ Ａｎａｔｏｍｙ ｏｆ ａ Ｌａｒｇｅ−Ｓｃａｌｅ Ｈｙｐｅｒｔｅｘｔｕａｌ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ）」、第７回国際ワールドワイドウェブ会議（Ｓｅｖｅｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ Ｃｏｎｆｅｒｅｎｃｅ）、オーストラリア、ブリスベン（Ｂｒｉｓｂａｎｅ，Ａｕｓｔｒａｌｉａ）及び米国特許第６，２８５，９９９号（ともに参照してここに組み込まれる）に説明されている。このような検索結果は、例えばウェブページのタイトルリスト、それらのウェブページから抽出されたテキストの抜粋、及びそれらのウェブページへのハイパーテキストリンクを含んでよく、所定数の（例えば１０の）検索結果に分類されてよい。
【００２６】
検索エンジンは、システム１２０に広告に対する要求を提出してよい。要求は所望される多数の広告を含んでよい。この数は、検索結果、検索結果によって占められる画面又はページ空間の量、広告の大きさと形状等に依存してよい。一実施形態では、所望される広告の数は１から１０、好ましくは３から５となるであろう。広告に対する要求は（入力又は構文分析されたとおりの）クエリー、（クエリーが関係者及びこのような関係者の識別子からきたのかに関係なく、ジオロケーション情報等の）クエリーに基づいた情報、及び／又は検索結果と関連付けられた又は検索結果に基づいた情報を含んでもよい。このような情報は、例えば検索結果に関連した識別子（例えば文書識別子、つまり「ｄｏｃＩＤ」）、検索結果に関連したスコア（例えば、クエリー及び文書、ページランクスコア、及び／又はＩＲスコアとページランクスコアの組み合わせに対応する特徴ベクトルのドット積のような情報検索（「ＩＲ」）スコア）、特定された文書から抽出されるテキストの抜粋（例えばウェブページ）、特定された文書の全文、特定された文書の特徴ベクトル等を含んでよい。
【００２７】
検索エンジンは、システム１２０によって提供される広告の１つ以上と検索結果を結合してよい。検索結果と広告（複数の場合がある）を含むこの結合された情報は、次にユーザに提示するために、コンテンツを要求したユーザに向かって転送される。好ましくは、検索結果は、有料広告とおそらくは中立の検索結果の間でユーザを惑わせないように、広告と区別して保持される。
【００２８】
最後に検索エンジンは、広告に関する情報、及び広告がいつ、どこで、及び／又はどのようにして表示されるべきであったのか（例えば、位置、クリックスルーか否か、インプレッション時間、インプレッション日付、コンバージョンか否か等）についての情報を、システム１２０に送り返してよい。代わりに、又はさらに、このような情報は何らかの手段によってシステム１２０に提供し直されてよい。
【００２９】
第４．１２章 例示的な広告入力保持および配信環境
図２は、本発明が中で使用されてよい、あるいは本発明がともに使用されてよい、例示的な広告システム１２０’を示す。例示的な広告システム１２０’は在庫システム２１０を含んでよく、広告情報２０５と使用情報２４５を記憶してよい。例示的なシステム１２０’は、広告情報入力管理動作２１５、キャンペーン（例えば対象設定）支援動作２２０、会計及び請求書作成発行動作２２５、広告供給動作２３０、関連性決定動作２３５、最適化動作２４０、相対提示属性割り当て（例えば、位置順序付け）動作２５０、不正検出動作２５５、及び結果インタフェース動作２６０を支援してよい。
【００３０】
広告主１１０は、インタフェース２１６によって示されるように、広告情報入力管理動作２１５を介してシステム１２０’と接続してよい。広告消費者１３０は、インタフェース２３１によって示されるように広告供給動作２３０を介してシステム１２０’と接続してよい。広告消費者１３０及び／又は他のエンティティ（図示せず）は、インタフェース２６１によって示されるように結果インタフェース動作２６０を介してシステム１２０’と接続してもよい。
【００３１】
広告プログラムは、アカウント、キャンペーン、クリエーティブ、対象設定等に関する情報を含んでよい。用語「アカウント」は、既定の広告主についての情報（例えば、一意のｅメールアドレス、パスワード、請求書作成発行情報等）に関する。「キャンペーン」又は「広告キャンペーン」は、１つ以上の広告のうちの１つ以上のグループに関し、開始日、終了日、予約情報、ジオターゲティング情報、シンジケート情報等を含んでよい。例えば、ホンダ（登録商標）（Ｈｏｎｄａ）は、その自動車取扱商品のための１つの広告キャンペーンと、そのオートバイ取扱商品のための別個の広告キャンペーンを有してよい。その自動車取扱商品のためのキャンペーンは、それぞれが１つ以上の広告を含む１つ以上の広告グループを有してよい。各広告グループは、キーワードの集合、及び最大費用付け値（ｂｉｄ）（クリックスルーあたり費用、コンバージョンあたり費用等）を含んでよい。代わりに、あるいは加えて、各広告グループは平均費用付け値（例えば、クリックスルーあたり平均費用、コンバージョンあたり平均費用等）を含んでよい。したがって、単一の最大費用付け値及び／又は単一の平均費用付け値は１つ以上のキーワードと関連付けられてよい。このように、各広告グループは１つ以上の広告つまり「クリエーティブ」（すなわち、最終的にエンドユーザに表示される広告コンテンツ）を有してよい。当然、広告情報２０５は多かれ少なかれ情報を有してよく、多くの異なる方法で編成されてよい。
【００３２】
広告情報２０５は、該広告情報入力管理動作２１５を介して入力、管理できる。キャンペーン（例えば対象設定）支援動作２２０は、広告主１１０が効果的な広告キャンペーンを作成するのを手助けするために利用できる。例えば、キャンペーン支援動作２２０は、検索エンジンとともに使用するための広告の関連で、すべての考えられる広告インプレッション、すでに予約されている広告インプレッション、及び既定のキーワードについて利用可能な広告インプレッションを追跡調査してよい、在庫システム２１０によって提供される情報を使用できる。
【００３３】
広告供給動作２３０は、広告消費者１３０からの広告に対する要求を果たしてよい。広告供給動作２３０は、既定の要求のための候補広告を決定するために関連性決定動作２３５を使用してよい。広告供給動作２３０は、次に候補広告のうち１つ以上の最終的な集合を選択するために最適化動作２４０を使用してよい。広告供給動作２３０は、次に返される広告の提示を順序付けるために、相対提示属性割り当て動作２５０を使用してよい。会計及び請求書作成発行動作２２５は、広告の供給に関連する料金を追跡調査するため、及び広告主に請求書を送るために使用されてよい。不正検出動作２５５は、盗まれたクレジットカードの使用による等、広告システムの（例えば広告主による）不正な使用を削減するために使用できる。最後に、結果インタフェース動作２６０は、クリックスルーが発生したかどうか、コンバージョンが発生したかどうか（例えば、広告された商品又はサービスの販売が開始されたか、あるいは広告の表示から所定の時間内に完了されたか）等の、実際に供給された広告について（消費者１３０又は他の何らかのエンティティからの）結果情報を受け入れるために使用されてよい。このような結果情報はインタフェース２６１に受け入れられ、関連付けられた結果だけではなく、広告及び広告が供給された時刻を特定するための情報も含んでよい。
【００３４】
本発明の多様な態様は、関連性決定動作２３５、相対的な提示属性順序付け動作２５０、及び／又は広告供給動作２３０とともに使用されてよい。
【００３５】
第４．１．３項 例示的なネットワーク環境
図３は、本発明が使用されてよい例示的なネットワーク環境３００を示す。例示的なネットワーク環境３００は、それぞれがブラウザ３２０（又は何らかの他の情報要求表示手段）を有する、１台以上のクライアントデバイス３１０を含んでよい。クライアントデバイス３１０は、１台以上のコンテンツサーバ３２０によって供給される文書３３５を要求し、１つ以上の検索エンジン３４０を使用してそれらの又は他の文書に含まれるコンテンツを検索できる。広告サーバ３５０は、１つ以上の広告３５５を供給できる。供給された該１つ以上の広告３５５は、コンテンツサーバ３３０によって供給される文書（及び／又はこのような文書に対する要求）に関連性があってよい、及び／又は検索エンジン３４０によって生じる検索結果（及び／又は検索クエリー）に関連性があってよい。（例えば、１台以上のクライアントデバイス３１０と関連付けられる個々のユーザ又はユーザのグループについての）ユーザ情報３６５は、１台以上の情報サーバ３６０に記憶されてよい。代わりに、又は加えて、ユーザ情報（図示せず）は、１台以上のコンテンツサーバ３３０、１つ以上の検索エンジン３４０、及び／又は１つ以上の広告サーバ３５０に記憶されてよい。１台以上のクライアントデバイス３１０、コンテンツサーバ３３０、検索エンジン３４０、広告サーバ３５０、及び／又はユーザ情報サーバ３６０は、１つ以上のネットワーク３７０を介して互いと情報を交換してよい。該１つ以上のネットワーク３７０はインターネット及びサーバであってよく、検索エンジンはコンピュータであってよい。ユーザ情報（例えば、ユーザプロファイルデータベース）、情報インデックス、及び広告インデックスは、別のレポジトリである必要はない。それらは、単一のレポジトリに記憶されてよい。さらに、データのこれらの形式はインタリーブ化されてよい（例えば、広告データベースは、いくつかの部分集合だけが特定のタイプのユーザのために取り出されるように、広告上に「ユーザ特徴タグ」を含んでよい）。
【００３６】
第４．１．４項 定義
図１、図２、図３を参照して前述された例示的なシステム及び任意の他のシステムで使用されるようなオンライン広告は、多様な固有の特徴を有してよい。このような特徴は、アプリケーション及び／又は広告主によって指定されてよい。これらの特徴は以下で「広告特徴」と呼ばれている。例えば、テキスト広告のケースでは、広告特徴は、タイトル行、広告テキスト、及び埋め込まれているリンクを含んでよい。画像広告のケースでは、広告特徴は、画像、実行可能なコード、及び埋め込まれているリンクを含んでよい。オンライン広告のタイプに応じて、広告特徴は、テキスト、リンク、音声ファイル、ビデオファイル、画像ファイル、実行可能コード、埋め込まれている情報等のうち、１つ以上を含んでよい。
【００３７】
オンライン広告が供給されるときには、該広告がどのようにして、いつ、及び／又はどこで供給されたのかを説明するために、１つ以上のパラメータが使用されてよい。これらのパラメータは以下で「供給パラメータ」と呼ばれる。供給パラメータは、例えば、広告が供給されたページ（上の情報を含む）の特徴、広告の供給と関連付けられた検索クエリー又は検索結果、ユーザ特性（例えば、彼らのジオロケーション、ユーザにより使用されている言語、使用されているブラウザのタイプ、過去のページ表示、過去の動作）、要求を開始したホスト又は関係者のサイト（例えば、アメリカオンライン（Ａｍｅｒｉｃａ Ｏｎｌｉｎｅ）、グーグル（Ｇｏｏｇｌｅ）、ヤフー（Ｙａｈｏｏ））、広告が供給されていたページにおける広告の絶対位置、他の供給される広告を基準にした広告の位置（空間的又は時間的）、広告の絶対サイズ、他の広告を基準にした広告のサイズ、広告の色、他の供給される広告の数、供給される他の広告のタイプ、供給される時刻、広告される曜日（ｔｉｍｅ ｏｆ ｗｅｅｋ）、広告される季節（ｔｉｍｅ ｏｆ ｙｅａｒ）等のうち１つ以上を含んでよい。当然ながら、本発明に関連して使用されてよい、他の供給パラメータもある。
【００３８】
供給パラメータは広告特徴にとって付帯的であってよいが、それらは供給条件又は制約として広告と関連付けられてよい。供給条件又は制約として使用されるとき、このような供給パラメータは単に「供給制約」（つまり「対象設定基準」）と呼ばれる。例えば、いくつかのシステムでは、広告主は、それが平日だけに、特定の位置より下ではなく、特定のジオロケーションのユーザに対してだけ供給されなければならない等を指定することによって、その広告の供給の対象を設定できてよい。別の例として、いくつかのシステムでは、広告主は、ページ又は検索クエリーが特定のキーワード又は句を含む場合にだけ、その広告が供給されなければならないと指定してよい。さらに別の例として、いくつかのシステムでは、広告主が、供給されている文書が特定のトピック又は概念を含む、あるいは特定の１つ以上のクラスタ、又は何らかの他の１つ以上の分類に該当する場合にだけ、その広告が供給されなければならないと指定してよい。「ジオロケーション」情報は、１つ以上の国、１つ以上の（国間の）地方、１つ以上の州、１つ以上の首都圏、１つ以上の都市、１つ以上の町、１つ以上の区、共通の郵便番号が付いた１つ以上の地域、共通の電話局番の付いた１つ以上の地域、共通のケーブル電波中継局により供給される１つ以上の地域、共通ネットワークアクセスポイント又はノードによって供給される１つ以上の領域等のうち１つ以上を指定する情報を含んでよい。それは緯度及び／又は経度、あるいはこれらの範囲を含んでよい。それはユーザの位置が推定できるＩＰアドレス等の情報を含んでよい。
【００３９】
「広告情報」は、このような情報の拡張部（例えば、広告関連情報から引き出された情報）だけではなく、広告特徴、広告供給制約、（「広告導出情報」と呼ばれる）広告特徴又は広告供給制約から引き出すことができる情報、及び／又は（「広告関連情報」と呼ばれる）広告に関連した情報の任意の組み合わせも含んでよい。
【００４０】
「文書」は、コンピュータが解読できる、又はコンピュータが記憶できる任意の作業生産物を含むように広義に解釈されるべきである。文書は、ファイル、ファイルの組み合わせ、他のファイルに対する埋め込みリンクのある１つ以上のファイル等であってよい。ファイルは、テキスト、音声、画像、ビデオ等の任意のタイプであってよい。エンドユーザに表示される文書の部分を、文書の「コンテンツ」と見なすことができる。文書は、コンテンツ（ワード、ピクチャ等）及びそのコンテンツの意味の何らかの表示（例えば、ｅメールフィールド及び関連付けられたデータ、ＨＴＭＬタグ及び関連データ等）の両方を含む、「構造化データ」を含んでよい。文書中の広告スポットは、埋め込まれた情報又は命令によって定義されてよい。インターネットの関連では、共通の文書はウェブページである。ウェブページは多くの場合、コンテンツを含み、（メタ情報、ハイパーリンク等の）埋め込まれた情報、及び／又は（Ｊａｖａ（登録商標）ｓｃｒｉｐｔ等の）埋め込まれた命令を含んでよい。多くのケースでは、文書は一意の、アドレス指定可能な記憶位置を有し、したがってこのアドレス指定可能な位置によって一意に識別できる。ユニバーサルリソースロケータ（ＵＲＬ）は、インターネット上で情報にアクセスするために使用される一意のアドレスである。
【００４１】
「文書情報」は、（例えば、関連情報から引き出される情報等の）このような情報の拡張だけではなく、文書に含まれる任意の情報、（「文書導出情報」と呼ばれる）文書に含まれる情報から引き出すことのできる情報、及び／又は（「文書関連情報」と呼ばれる）文書に関連する情報も含んでよい。文書導出情報の例は、文書のテキストコンテンツに基づいた分類である。文書関連情報の例は、当該の文書がリンクする他の文書からの文書情報だけではなく、当該の文書へのリンクのある他の文書からの文書情報も含む。
【００４２】
「ｅメール情報」は、（例えば、関連情報から引き出される情報等の）このような情報の拡張部だけではなく、（「内部ｅメール情報」と呼ばれることもある）ｅメールに含まれる任意の情報、ｅメール情報に含まれる情報から引き出すことのできる情報、及び／又はｅメールに関連する情報も含んでよい。ｅメール情報から引き出される情報の例は、ｅメールの件名の行から抽出される用語から構成される検索クエリーに応えて返される検索結果から、抽出される、あるいはそれ以外の場合引き出される情報である。ｅメール情報に関連する情報の例は、既定のｅメールの同じ送信者によって送信される１つ以上の他のｅメールについてのｅメール情報、又はｅメール受取人についてのユーザ情報を含む。ｅメール情報から引き出される、あるいはｅメール情報に関連する情報は、「外部ｅメール情報」と呼ばれてよい。
【００４３】
文書からのコンテンツは、「コンテンツレンダリングアプリケーション又はデバイス」で表示されてよい。コンテンツレンダリングアプリケーションの例は、インターネットブラウザ（例えば、エクスプローラ（Ｅｘｐｌｏｒｅｒ）又はネットスケープ（Ｎｅｔｓｃａｐｅ）、メディアプレーヤ（例えば、ＭＰ３プレーヤ、リアルネットワークス（Ｒｅａｌｎｅｔｗｏｒｋｓ）ストリーミング音声ファイルプレーヤ等）、ビューワ（例えば、アドビアクロバット（Ａｄｏｂｅ（登録商標） Ａｃｒｏｂａｔ）ｐｄｆリーダ）等を含む。
【００４４】
「コンテンツオーナ」とは、文書のコンテンツに何らかの所有権を有する人物又はエンティティである。コンテンツオーナはコンテンツの作者であってよい。加えて、又は代わりに、コンテンツオーナは、コンテンツを複製する権利、コンテンツの派生著作物を作成する権利、コンテンツを公に表示する又は実行する権利、及び／又はコンテンツの他の所定の権利を有してよい。コンテンツサーバが、それが供給する文書のコンテンツにおいてコンテンツオーナである可能性があるが、これは必須ではない。
【００４５】
（「ＵＰＩ」とも呼ばれる）「ユーザプロファイル情報」は、個人ユーザ又はユーザのグループについての任意の情報を含んでよい。このような情報は、ユーザによって提供されてよく、ユーザ情報を公開することを許可されているサードパーティによって提供されてよく、及び／又はユーザアクションから引き出されてよい。特定のユーザ情報は、同じユーザの他のユーザ情報及び／又は他のユーザのユーザ情報を使用して演繹又は推測できる。ＵＰＩは多様なエンティティと関連付けられてよい。「ユーザＵＰＩ」は特定のユーザ又はユーザのグループと関連付けられるユーザプロファイル情報である。「文書ＵＰＩ」は、文書と関連付けられるユーザプロファイル情報である。例えば、文書ＵＰＩは、文書を要求した又は文書にアクセスしたユーザの多様なユーザＵＰＩの複合表現であってよい。「広告待ち受けページＵＰＩ」は特定のタイプの文書ＵＰＩであり、おそらく彼らが広告を選択した（例えばクリックした）ことに応じて、ある特定のウェブページにアクセスした、あるいはある特定のウェブページで購入を完了した多様なユーザの複合表現であってよい。「対象設定ＵＰＩ」は、ユーザプロファイル供給制約を含んでよい。例えば、前立腺がん検診のための広告は、属性「男性」及び「年齢４５歳以上」を有するユーザプロファイルに限定される可能性がある。
【００４６】
本発明の多様な例示的な実施形態は、ここで第４．２項に説明される。
【００４７】
第４．２項 例示的な実施形態
第４．２．１項 例示的なユーザ情報
図４は、本発明にしたがった方法でユーザプロファイル情報（ＵＰＩ）を記憶するために使用されてよい、例示的なデータ構造４００である。図示されていないが、そのデータ構造４００は識別子を含んでよい。このような識別子は、ある特定のユーザ、ユーザのグループ、文書、広告、広告待ち受けページ等と、ＵＰＩとを関連付けるために使用されてよい。ＵＰＩは、１つ以上のＵＰＩ属性４２０に関連する情報４１０の１つ以上の集合体を含んでよい。各属性４２０は、関連付けられた値４３０とスコア４４０を有してよい。
【００４８】
ＵＰＩ属性４２０は、例えば、地理情報、年齢又は年齢層、関心のある話題、読書レベル、収入、及び広告の対象を設定するために適した他の人口統計データ等の、ユーザの背景及び関心に関する情報を含んでよい。ＵＰＩ属性４２０と関連付けられた値４３０は、量的（離散値又は連続値、例えば年齢＝５８歳、年収＝５５，０００ドル、居住都市＝サンフランシスコ、カリフォルニア州（Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ）又は質的（集合の中、又は集合の中ではない、例えば、給料が＄５０，０００−＄１００，０００？＝イエス；米国在住か？＝イエス）であってよい。各ＵＰＩ属性４２０及び値４３０は、属性の値が正しい確率に関連する関連スコア４４０を有してよい。ＵＰＩ属性の例は以下の１つ以上を含んでよい。
【００４９】
−ユーザがアクセスした（又は特定の期間内にアクセスした）ウェブサイトのコンテンツ（例えば、ワード、Ａｎｃｈｏｒｔｅｘｔ等）
−人口学的情報、
−地理情報、
−心理情報、
−ユーザが行った過去のクエリー（及び／又は関連情報）、
−ユーザに表示され、選択した、及び／又は見た後に購入した、過去の広告についての情報、
−ユーザによって表示された／要求された及び／又は編集された文書（例えばワードプロセッサ）についての情報、
−ユーザの関心、
−ユーザからの個人的な結果に関する、明示的又は暗示的なフィードバック（例えば、結果を選択する、結果を選択しない、結果に関して費やされる時間の量等）、
−ブラウジング活動、及び、
−過去の購入動作。
【００５０】
このような情報は、個人単位で記憶されてよい（プライバシーの問題から個人識別可能な情報を含まない可能性がある）、あるいは個人の多様な集団の中で種々の方法で集められてよい。このような情報は複合プロファイルを得るために結合されてよい。
【００５１】
第４．２．２項 ＵＰＩを使用するための例示的なアプリケーション
ユーザプロファイル情報（ＵＰＩ）を使用するための多くのアプリケーションがある。３つの例示的なアプリケーション−強化広告対象設定、広告クリエーティブ選択と生成、及びクエリー両義性解決−が後述される。
【００５２】
第４．２．２．１項 ＵＰＩを使用する広告採点
広告の対象設定されたＵＰＩ（及び／又は広告の待ち受けページのＵＰＩ）が文書ＵＰＩに一致する（例えば、文書を要求したユーザの平均的なＵＰＩ）に一致するホストサイト又はページに広告を掲載すること、及び／又はＵＰＩが広告（及び／又は広告の待ち受けページのＵＰＩ）のターゲットＵＰＩに一致するユーザに広告を供給することが望ましい場合がある。
【００５３】
ＵＰＩを使用する強化広告対象を用いると、複数の広告のそれぞれのスコアは、ユーザのＵＰＩ、文書のＵＰＩ、広告待ち受けページのＵＰＩ、及び／又は広告対象設定ＵＰＩの少なくともいくつかを使用して決定されてよい。少なくとも１つの広告は順位で順序付けられ、フィルタリングされ、及び／又は少なくとも決定されたスコアを使用して複数の広告から選択されてよい。
【００５４】
例えば、広告スコアはＵＰＩ一致値の関数であってよい。図５を参照すると、このようなＵＰＩ一致値は、（ｉ）ユーザ（又はユーザグループ）５１２と関連付けられたＵＰＩ情報５１４と、ユーザ５１２によって要求される（又はアクセスされる）文書（例えば、ウェブページ）と関連付けられたＵＰＩ情報５１４との一致値（一致値１）、（ｉｉ）ユーザ（又はユーザグループ）５１２と関連付けられたＵＰＩ情報５１４と、検討中の広告の待ち受けページ５３２と関連付けられたＵＰＩ情報５３４との一致値（一致値２）、（ｉｉｉ）ユーザによって要求される（又はアクセスされる）文書５２２と関連付けられたＵＰＩ情報５２４と、検討中の待ち受けページ５３２と関連付けられるＵＰＩ情報５３４との一致値（一致値３）、（ｉｖ）ユーザ（又はユーザグループ）５１２と関連付けられたＵＰＩ情報５１４と、検討中の広告５４２と関連付けられたＵＰＩ広告対象設定情報５４４との一致値（一致値４）、及び（ｖ）ユーザによって要求される又はアクセスされている文書５２２と関連付けられたＵＰＩ情報５２４と、検討中の広告５４２と関連付けられたＵＰＩ広告対象設定情報５４４の一致値（一致値５）のうち、１つ以上の関数であってよい。
【００５５】
このようにして、本発明の一実施形態では、全体的な一致は以下のように定義されてよい。
【００５６】
ＵＰＩ一致＝ａ＊一致値１＋ｂ＊一致値２＋ｃ＊一致値３＋ｄ＊一致値４＋ｅ＊一致値５
ここで、ａ、ｂ、ｃ、ｄ及びｅは定数である（例えば、ａ＝０．０２５、ｂ＝０．２７５、ｃ＝０．３、ｄ＝０．２、及びｅ＝０．２）。ユーザＵＰＩと文書ＵＰＩの間の一致は、広告にどれか１つがどれほどよく一致するのかには関係ない可能性があるため、「ａ」がゼロに設定されてよいことに留意されたい。多項式又は指数関数を含む他の関数が代わりに使用されてよい。
【００５７】
一般的には、優れた一致のためには、ユーザのＵＰＩはホストページＵＰＩに一致し、おそらくさらに重要なことには、広告待ち受けページのＵＰＩにも一致しなければならない。２つのプロファイルの一致は、ベクトル空間一致等の２つの用語のベクトルを一致させるための標準的な情報検索技法を使用して計算できる（例えば、記事、Ｇ．Ｓａｌｔｏｎ及びＣ．Ｂｕｃｋｌｅｙ、「自動テキスト検索における用語加重手法（Ｔｅｒｍ−Ｗｅｉｇｈｔｉｎｇ Ａｐｐｒｏａｃｈｅｓ ｉｎ Ａｕｔｏｍａｔｉｃ Ｔｅｘｔ Ｒｅｔｒｉｅｖａｌ）」、情報処理及び管理（Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ ａｎｄ Ｍａｎａｇｅｍｅｎｔ）、２４（５）、５１３−５２３ページ（１９８８年）、及びＧｅｒａｒｄ Ｓａｌｔｏｎ、Ａ．Ｗｏｎｇ、Ｃ．Ｓ．Ｙａｎｇ、「自動索引付けのためのベクトル空間モデル（Ａ Ｖｅｃｔｏｒ Ｓｐａｃｅ Ｍｏｄｅｌ ｆｏｒ Ａｕｔｏｍａｔｉｃ Ｉｎｄｅｘｉｎｇ）」、ＡＣＭの通信（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ）、１８（１１）、６１３−６２０ページ（１９７５年）を参照されたい）。
【００５８】
地形、話題、ユーザ年齢範囲、言語等の幅広い属性は、例えば機械学習分類子を使用して文書とユーザについて計算できる。また、このような幅広い属性は、マッチングにおいて単語と句のようなより狭い属性とも一緒に使用できる。
【００５９】
当然、広告のスコアは、例えば、検索クエリーに、又は文書のコンテンツに対するその関連性、既定の結果（例えば、インプレッション、選択、コンバージョン等）について広告主が支払う、あるいは支払う用意がある金額、広告の性能の測度（例えば、クリックスルー率、コンバージョン率、ユーザ定格等）、広告主の品質の測度等の、ＵＰＩ一致に加えて他の要因の関数である場合がある。さらに、異なる中間広告スコアは異なる目的で（例えば、関連性、位置、相対的なレンダリング属性等）使用されてよい。
【００６０】
第４．２．２．２項 ＵＰＩを使用する広告クリエーティブ選択
ＵＰＩを使用する広告クリエーティブ選択及び／又は生成を用いると、広告クリエーティブは（例えば、ユーザ、文書等の）ＵＰＩに合わせて調整されてよい。
【００６１】
第４．２．２．３項 ＵＰＩを使用するクエリー両義性解決
適切な広告つまり広告クリエーティブを選択することに加えて、ＵＰＩは不明瞭な検索用語を含む検索クエリーを明確にするために使用されてよい。例えば、検索クエリー「ジャガー」を提出するユーザは、（Ａ）車ジャガー（Ｊａｇｕａｒ）についての情報、（Ｂ）動物についての情報、（Ｃ）アップルジャガー（Ａｐｐｌｅ Ｊａｇｕａｒ）オペレーティングシステムについての情報、又は（Ｄ）ジャクソンビルジャガー（Ｊａｃｋｓｏｎｖｉｌｌｅ Ｊａｇｕａｒ）ＮＦＬフットボールチームについての情報のどれかを必要とする可能性がある。ユーザのＵＰＩは、「ジャガー」検索用語を明確にするために使用できるであろう。この例では、ユーザの以前のブラウジング活動からの情報が、曖昧なクエリー「ジャガー」を明確にするのに役立つ、あるいはユーザにとってほとんど又はまったく重要ではない広告が表示されないようにしてよい。例えば、ユーザが最近「アップルコンピュータ」と「オペレーティングシステム」についてクエリーを行っており、その後検索クエリー「ジャガー」を提出した場合、ユーザの以前のクエリー履歴は、クエリーがアップル（Ａｐｐｌｅ）コンピュータ用のオペレーティングシステムを参照しており、車、動物又はＮＦＬチームを参照していない可能性が高かった。その結果、広告はこのような情報を利用することによってユーザに対象を設定できるであろう。
【００６２】
他だけではなく、ＵＰＩを使用するためのこれらの前記アプリケーションは、ＵＰＩが入手可能であると仮定する。しかしながら、これが当てはまらない場合、このようなＵＰＩが生成及び／又は更新される必要がある。ＵＰＩを決定する、及び／又は更新するための例示的な方法は、以下の第４．２．３項に説明される。
【００６３】
第４．２．３項 ＵＰＩを決定する、及び／又は更新すること
ユーザプロファイル情報（ＵＰＩ）が、サービスに加入するときにユーザが提供した情報を使用して決定できることを想起されたい。しかしながら、多くのケースでは、ユーザは自らについての情報を進んで開示しない（ｖｏｌｕｎｔｅｅｒ）、あるいは単にこのような情報を進んで開示しないように頼まれる。さらにユーザがたとえこのような情報を進んで開示しても、（例えば、加入の時点で与えられた情報がサービスに必要とされていることに限定されてよく、したがって包括的ではないために）それは不完全である可能性がある、それは意図的に又は無意図的に不正確である可能性がある、それは陳腐になる可能性がある等である。
【００６４】
同様に、ＵＰＩ情報はユーザが要求した、あるいはアクセスしている文書について入手できない可能性がある。
【００６５】
広告は、広告主にＵＰＩ情報を供給させることができるが、このようにすることは広告主にとっては重荷となる可能性がある。
【００６６】
後述されるように、ユーザ、文書等のＵＰＩは、明示的な情報がシステムに与えられていなくても決定できる（あるいは更新できる、あるいは拡張できる）。以下では、初期の（又はベースライン）ＵＰＩが、ブートストラップ段階の間に決定されてよい。このような初期ＵＰＩは、ユーザ又は文書に、あるいはＵＰＩが関連付けられる広告に固有の情報を使用してよい。初期ＵＰＩは、明示的に入力された何らかのＵＰＩ情報を含んでもよいし、含まなくてもよい。
【００６７】
広告採点、広告クリエーティブ選択、クエリー両義性解決等の応用例に、このような初期ＵＰＩ又はベースラインＵＰＩを使用するだけで十分な場合がある。しかしながら、拡大及び／又は強化段階の間に、初期ＵＰＩ又はベースラインＵＰＩを補足することが所望されてよい。例えば図４を参照し直すと、（例えばユーザの、又は文書の、又は広告の、又は広告待ち受けページの）ＵＰＩ４１０は、過去に存在しなかった、又は値を有していなかったかのいずれかである属性４２０に値４３０を追加することによって拡大されてよい。代わりに、又は加えて、ＵＰＩ４１０の属性４２０の値４３０の４４０のスコアは、修正又は強化されてよい。したがって、例えば、値＝男性を有する属性＝性別の確率は、規定の追加情報を増加又は減少してよい。初期ＵＰＩを拡大又は補足するために使用される情報は、推測された情報と見なされてよい。
【００６８】
図６は、本発明にしたがった方法で文書ＵＰＩを決定するために使用されてよい例示的な方法６００のフロー図である。文書のための初期ＵＰＩが決定される。（ブロック６１０）これは、文書コンテンツ等の文書に固有の情報を使用して行われてよい。この行為を実行するための例示的な方法は図８に関して後述される。文書のための追加ＵＰＩ情報が推測される。（ブロック６２０）これは、アクセスしているユーザ、リンクされている文書等から推測される情報を使用して行われてよい。次に、新しい（例えば、拡大された及び／又は強化された）文書ＵＰＩは、初期文書ＵＰＩ及び推測された文書ＵＰＩを使用して決定される。（ブロック６３０）行為６２０と６３０は、方法６００が終了される前に一回以上実行されてよい。（ノード６４０）。行為６２０と６３０が、仮想分岐戻り線によって示されるように繰り返される場合、新しい文書ＵＰＩは、以前の文書ＵＰＩ及びさらに多くの推測文書ＵＰＩを使用して決定されてよい。
【００６９】
図７は、本発明にしたがった方法で（個人又はグループとしての）ユーザＵＰＩを決定するために使用されてよい、例示的な方法７００のフロー図である。ユーザのための初期ＵＰＩが決定される。（ブロック７１０）これはユーザによって提出される過去の検索クエリー等のユーザに固有な情報を使用して行われてよい。この行為を実行するための例示的な方法は図９を参照して後述される。ユーザのための追加のＵＰＩ情報が推測される。（ブロック７２０）これは検索結果、選択された検索結果等から推測される情報を使用して実行されてよい。次に、新しい（例えば、拡大された、及び／又は強化された）ユーザＵＰＩは、初期ユーザＵＰＩ及び推測されたユーザＵＰＩを使用して決定される。（ブロック７３０）行為７２０と７３０は、方法７００が終了される前に一回以上実行されてよい。（ノード７４０）。行為７２０と７３０が、仮想分岐戻り線によって示されるように、繰り返される場合、新しいユーザＵＰＩは、以前のユーザＵＰＩとさらに多くの推測されたユーザＵＰＩを使用して決定されてよい。
【００７０】
図６のブロック６１０から、初期文書ＵＰＩが決定されてよいことを想起されたい。図８は、本発明にしたがった方法で初期ＵＰＩ又はベースライン文書ＵＰＩを決定するために使用されてよい、例示的な方法８００のフロー図である。示されているように、文書ＵＰＩ属性値は（例えば、文書のコンテンツ、文書のメタ情報等を使用して）投入されてよい。（ブロック８１０）
図７のブロック７１０から、初期ユーザＵＰＩが決定されてよいことを想起されたい。図９は、本発明にしたがった方法で初期ＵＰＩ又はベースラインユーザＵＰＩを決定するために使用されてよい、例示的な方法９００のフロー図である。図示されるように、ユーザＵＰＩ属性値は（例えば、ユーザの過去のクエリー情報、ユーザによって明示的に入力される情報等を使用して）投入されてよい（ブロック９１０）。
【００７１】
第４．２．４項 ユーザ情報がどのようにして取得されるのかの例
ユーザ情報を取得する多くの代替方法がある。例えば、属性４２０と値４３０のスコア４４０は、以前に実施されたクエリーの単語を使用して、プロファイルの中のＵＰＩ属性４２０の値４３０を予測する機械学習分類子を用いて決定できる。例えば、以前の検索クエリーの中の「女性の健康」に関連するキーワードを考えると、分類子はユーザが０．８という確率で女性であると推測してよい。さらに、以前の検索クエリーで日本語の単語が使用されたことを考えると、分類子はユーザが０．９の確率で日本人であると推測してよい等である。２つのＵＰＩのスコア４４０は、それらが一致するかどうかに影響を及ぼす可能性がある。属性４２０は、１つのＵＰＩでは「サンフランシスコ」で、もう１つでは「サンホセ」である場合がある。これらの未処理の属性は一致しないが、機械学習分類子は両方のケースで地理的なカテゴリ＝「カリフォルニア」を割り当ててよく、一般化されるプロファイル属性は一致するであろう。したがって、機械学習分類子は、ユーザと文書を、地理、話題、民族性、又は読書レベルに関する幅広いカテゴリに分類するために使用されてよい。
【００７２】
ＵＰＩ情報が推測されてよいことを、図６のブロック６２０と図７の７２０の両方から想起されたい。ユーザＵＰＩは、何らかの方法でユーザと関連付けられる他のユーザ及び／又は文書のＵＰＩから推測されてよい。同様に、文書ＵＰＩは他の文書のＵＰＩから推測されてよい、及び／又はユーザは、文書と何らかの方法で関連付けられてよい。図１０は、ユーザと文書がどのようにして関連付けられるのかを示す。
【００７３】
図１０に示されるように、ユーザ／文書関連動作１０１０は、一人以上のユーザのユーザ情報１０２０、１つ以上の文書の文書情報１０３０、文書リンク（例えば、ウェブトポロジー）情報１０４０、（代わりにユーザ情報１０２０として提供されてよい）ユーザクエリー１０５０の検索結果、及び（代わりにユーザ情報１０３０として提供されてよい）ユーザ文書選択１０６０のうち１つ以上を使用して、ユーザ及び／又は文書（ユーザ対ユーザ、ユーザ対文書、文書対文書、及び／又は（示されているもののような無向グラフでのユーザ対文書の関連と同じであってよい）文書対ユーザ）を関連付ける、情報１０７０を生成してよい。
【００７４】
本発明の例示的な一実施形態では、関連情報１０７０は、ユーザと文書がそれぞれノード１０７２と１０７６として表されるグラフであってよい。図１１は、本発明にしたがった方法でユーザ及び／又は文書を関連付けるために使用されてよい、例示的な方法１１００のフロー図である。図示されるように、ノードは各ユーザと文書に定められてよい。（ブロック１１１０）ユーザノード１０７２のそれぞれに、ユーザが提出した検索クエリーに応えて検索エンジンによって戻された一番上のウェブページのために、（関連を示す）エッジ１０７４がユーザノードと文書ノードの間に描画されてよい。（変形では、エッジ１０７４は、ユーザが選択した（例えばクリックした）ウェブページだけで描画できるであろう）。さらに、エッジ１０７８がそれらの間にリンク（例えばハイパーリンク）を有する文書の組の間に描画されてよい。（ブロック１１２０）図示されていないが、ユーザ対ユーザの関連も生成されてよい。例えば、エッジは同じ文書の１つ以上にアクセスしたユーザ間で追加されてよい。
【００７５】
図７を参照し直すと、このグラフ１０７０を考えると、ユーザのための新しいＵＰＩが、その初期のＵＰＩ、及び推測されたユーザＵＰＩとして、ユーザノード１０７２がリンクされるノード１０７６に対応する文書のＵＰＩを使用して、決定されてよい。同様に、図６を参照し直すと、文書の新しいＵＰＩは、このグラフ１０７０を考えて、その初期のＵＰＩ、及び推測される文書ＵＰＩとして、文書ノード１０７６がリンクされる、それぞれノード１０７２と１０７６に対応するユーザＵＰＩと文書のＵＰＩを使用して、決定されてよい。
【００７６】
本発明の一実施形態において、それぞれ図６と図７のブロック６３０と７３０を参照し直すと、
ｕｐｄａｔｅｄ＿ＵＰＩ＝ｉｎｉｔｉａｌ＿ＵＰＩ＊ａｌｐｈａ＋ｎｅｉｇｈｂｏｒｈｏｏｄ＿ＵＰＩ＊ｂｅｔａ
であり、アルファとベータは定数（例えば、アルファ＝０．７、ベータ＝０．３）であり、ｎｅｉｇｈｂｏｒｈｏｏｄ＿ＵＰＩはグラフ内の近傍のノードのＵＰＩの平均である。ＵＰＩを更新するための他の関数が考えられる。このプロセスは反復を多数回（例えば、５０）繰り返されてよい。
【００７７】
平均ＵＰＩを決定するために、個々の属性４２０の値４３０が平均され、場合によってはスコア４４０で加重されてよい。
【００７８】
さらに多くの離れたノード（例えば、２エッジ以上離れた）も検討されてよいが、より少なく加重されなければならない。
【００７９】
ユーザＵＰＩと文書ＵＰＩの両方とも更新されてよいが、一方又は他方だけを更新することが可能である。
【００８０】
代替実施形態では、ユーザノード１０７２は、ユーザの集団を表してよい。同様に文書ノード１０７６は（例えば、多くのウェブページを含むウェブサイト等）文書の集合体を表してよい。
【００８１】
代替実施形態では、グラフエッジには関連重みが割り当てられる。したがって、例えば、文書がユーザ検索クエリーに応えて返された検索結果リストに単に含まれていた場合より、ユーザが検索結果リストから文書を選択した場合には、ユーザノード１０７２から文書ノード１０７６へのエッジ１０７４には、より大きな重みが与えられてよい。
【００８２】
第４．２．５項 例示的な装置
図１２は、前述された動作の１つ以上を達成してよい機械１２００の高水準ブロック図である（例えば、エンドユーザシステム又はクライアントデバイスによって実行される動作、コンテンツサーバによって実行される動作、検索エンジンによって実行される動作、あるいは広告サーバによって実行される動作）。機械１２００は、基本的に、１台以上のプロセッサ１２１０、１台以上の入力／出力インタフェース装置１２３０、１台以上の記憶装置１２２０、結合された要素の間の情報の通信を容易にするための１つ以上のシステムバス及び／又はネットワーク１２４０を含む。１台以上の入力装置１２３２及び１台以上の出力装置１２３４は、１つ以上の入力／出力インタフェース１２３０と結合されてよい。
【００８３】
該１台以上のプロセッサ１２１０は、本発明の１つ以上の態様を達成するために機械実行可能な命令（例えば、カリフォルニア州パロアルト（Ｐａｌｏ Ａｌｔｏ，Ｃａｌｉｆｏｒｎｉａ）のサンマイクロシステムズ社（Ｓｕｎ Ｍｉｃｒｏｓｙｓｔｅｍｓ Ｉｎｃ．）から入手可能なソラリス（Ｓｏｌａｒｉｓ）オペレーティングシステム、あるいはノースカロライナ州ダーハム（Ｄｕｒｈａｍ，Ｎｏｒｔｈ Ｃａｒｏｌｉｎａ）のレッドハット社（Ｒｅｄ Ｈａｔ，Ｉｎｃ．）等の多くのベンダから広範囲に入手可能なリナックス（登録商標）（Ｌｉｎｕｘ（登録商標））オペレーティングシステムで実行する、Ｃ又はＣ＋＋）を実行してよい。機械実行可能命令の少なくとも一部は、該１台以上の記憶装置１２２０上に（一時的に、又はより恒久的に）記憶されてよい、及び／又は１台以上の入力インタフェース装置１２３０を介して外部ソースから受け取られてよい。
【００８４】
一実施形態では、機械１２００は１台以上の従来のパーソナルコンピュータであってよい。このケースでは、該処理装置１２１０は１台以上のマイクロプロセッサであってよい。該バス１２４０はシステムバスを含んでよい。該記憶装置１２２０は、読み取り専用メモリ（ＲＯＭ）及び／又はランダムアクセスメモリ（ＲＡＭ）等のシステムメモリを含んでよい。記憶装置１２２０は、ハードディスクに読み書きするためのハードディスクドライブ、（例えばリムーバブル）磁気ディスクに読み書きするための磁気ディスクドライブ、及びコンパクトディスク又は他の（磁気）光学媒体等のリムーバブル（磁気）光学ディスクに読み書きするための光学ディスクドライブを含んでよい。
【００８５】
ユーザは、例えば、キーボードとポインティングデバイス（例えばマウス）等の入力装置１２３２を通して、パーソナルコンピュータにコマンドと情報を入力してよい。マイク、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ等の他の入力装置もまた、（あるいは代わりに）含まれてよい。これらの及び他の入力装置は多くの場合、システムバス１２４０に結合されている適切なインタフェース１２３０を通して処理装置（複数の場合がある）１２１０に接続されている。出力装置１２３４は、適切なインタフェースを介してシステムバス１２４０にも接続されてよいモニタ、又は他のタイプのディスプレイ装置を含んでよい。モニタに加えて（あるいは代わりに）パーソナルコンピュータは、例えばスピーカ及びプリンタ等の他の（周辺）出力装置（図示せず）を含んでよい。
【００８６】
第４．３項 改良版及び代替策
第４．３．１項 決定技法
マッチング（つまり類似性）決定は、多くの方法で実行できる。例えば、以下の類似性決定技法の１つ以上が使用されてよい。（ａ）（例えば後述されるような）ベクトルベース、（ｂ）（例えば後述されるような）規則ベース、（ｃ）一致の確率又は尤度を推測するための確率的推論、及び（ｄ）ファジー論理マッチングである。他の類似性技法は、本発明の元でも使用されてよい。
【００８７】
上で触れたように、類似性を決定する１つの方法はＵＰＩベクトルを形成することである。複数の広告のそれぞれは代表的な対象設定ＵＰＩベクトルを有してもよい。このようなＵＰＩベクトルは、履歴データから決定される追加情報も含んでよいことに留意されたい。例えば、どの人口グループがある広告をクリックする傾向があるかについての推論は、データマイニング技法を使用して決定されてよい。この（例えばオフラインの）分析の結果は、次に広告のＵＰＩ対象設定ベクトルの１つ以上の属性として使用されてよい。ＵＰＩベクトルは、ベクトル間のコサイン距離、ハミング距離、及び／又は種々の他のベクトル距離基準等の採点関数を使用して一致できる。次に広告は、このような関数により生じるスコアを使用して（例えばスコアに従って）ランクを付けることができる。
【００８８】
また前記に示されたように、ＵＰＩをマッチさせるための別の技法は、ユーザＵＰＩ、文書ＵＰＩ、広告ＵＰＩ、及び広告待ち受けページＵＰＩの１つ以上の組の類似性を定める規則及び／又は関数の集合を適用することを含む。このような規則及び／又は式をベースにしたシステムは、加重スコアを出すために（例えば、加重して）論理規則の任意の組み合わせを使用できる。
【００８９】
このように、ベクトルベースの技法及び規則及び／又は公式ベースの技法は、一致決定を生成するためにいっせいに使用されてよい。
【００９０】
本発明の一実施形態では、属性頻度−反転文書（又はユーザ）頻度積（ａｔｔｒｉｂｕｔｅ ｆｒｅｑｕｅｎｃｙ−ｉｎｖｅｒｓｅ ｄｏｃｕｍｅｎｔ（ｏｒ ｕｓｅｒ）ｆｒｅｑｕｅｎｃｙ ｐｒｏｄｕｃｔ）（ＴＦ−ＩＤＦ）基準は、類似性スコアを生じさせるためにＵＰＩを使用して決定される。
【００９１】
第４．３．１．１項 類似性決定技法の改良版
ＵＰＩを一致させるプロセスを効率的に保つために、属性選択、属性汎用化及び／又は属性集約の技法が、比較されているベクトルのサイズを縮小するために使用されてよい。例えば、属性選択は、ＵＰＩの間の一致プロセスの一部として使用される属性の数及び／又はサイズを削減するために使用されてよい。このような属性選択技法は、（絶対項及び／又は相対項の中で）高いスコア（例えば、確率又は重要性重み）を有する何らかの数の属性だけを、ＵＰＩのベクトル表現で保つことを含んでよい。別の属性選択技法は、うまく機能する（例えばクリックされる）可能性が高い１つ以上の一致を生成するために、他よりどの属性がより指標となるかを決定するために、「相互情報」、カイ二乗適合（Ｃｈｉ−ｓｑｕａｒｅｄ ｆｉｔ）、又は例えば相関等の、統計基準を使用することを含んでよい。さらに別の属性選択技法は、最も有用であると考えられるそれらの属性を単に手作業で選択することである。これらの又は他の属性選択技法の２つ以上がいっせいに使用されてよい。
【００９２】
同様に、ＵＰＩベクトルは、残っている広告ＵＰＩベクトルの小さい部分集合だけがユーザＵＰＩと文書ＵＰＩに関してランク付けされる必要があるように、（例えば、特定の特徴を正確に一致させる等の）何らかの初期基準の集合を使用して、前置フィルタにかけられてよい。この技法は、結合された規則ベースの類似性決定技法と、ベクトル距離類似性決定技法を示している。この技法を使用すると、ＵＰＩ間の全体的な一致プロセスの効率を高めるのに役立つという追加の利点がある。
【００９３】
例えば、ユーザ及び／又は文書に関連性のある１つ以上の広告の第１の集合が先に決定されてよい。１つ以上の広告の第１の集合は広告の最終的な集合を決定するためにＵＰＩ情報動作をさらに使用して処理されてよい（例えば、ＵＰＩを使用して決定される第２の類似性スコアに基づいて順序付けられる、及び／又はフィルタリングされる）。このような実施形態は、ＵＰＩ（の一部）がクライアントに記憶されるときに有用であり得る。例えば、広告サーバは、ユーザ要求（例えば検索クエリー又は文書要求）のために上位Ｎの（例えばＮ＝１００）の広告をクライアントに送信してよい。クライアントは、次にこれらの供給された広告に、ローカルユーザ情報に基づいて順序を付け直すことができる。
【００９４】
第４．３．２項 どのように及びどこにＵＰＩが記憶されるのかの例
本発明の一実施形態では、ＵＰＩは、関連付けられたソース（例えば、ｎグラムは表示されるウェブページ、クエリー等からである）、ＵＲＬ、又は異なる種類の情報（例えば、ユーザは特定のウェブブラウザを使用している、あるいはユーザは特定の緯度と軽度に位置している等）の特定の値が付いた、ｎグラム（長さ１からほぼ最大、例えば３までの単語のシーケンス）として記憶される。
【００９５】
ＵＰＩの記憶及び使用は、（ａ）（例えば、ブラウザクッキー、ローカルファイル、非表示形式フィールド、又はＵＲＬ符号化等の形をとる）クライアント側記憶装置、（ｂ）（例えば、プロファイル／動作情報を記憶し、検索するための記録のデータベース、フラットファイル、又は独自仕様の構造等の）サーバ側記憶装置、及び／又は（ｃ）サードパーティの記憶装置を含む、多様な異なる形式を取ってよい。このようにして、ＵＰＩはサーバ側のレポジトリに常駐する必要はないが、実際にはクライアント及び／又はサードパーティで記憶され、ユーザの要求とともに情報サーバに送信されてよい（例えば、検索クエリー又は文書要求）。ＵＰＩは例えば、ウェブブラウザクッキーで送信できる。
【００９６】
図３の例示的なネットワーク環境を参照し直すと、ＵＰＩは、１台以上のクライアントデバイス３２０、１台以上のコンテンツサーバ３３０、１つ以上の検索エンジン３４０、１台以上の広告サーバ３５０、及び／又は１台以上のユーザ情報サーバ３６０に記憶されてよい。いずれにせよ、ユーザ情報は、何らかのデータ管理方式（例えば、データベース、フラットファイル、独自仕様データ管理システム、ウェブブラウザクッキー等）を使用することにより保持されてよい。ユーザ情報のさまざまな項目（例えば異なるユーザ特徴）がさまざまなデバイスに記憶されてよい。
【００９７】
第４．３．２．１項 情報記憶に対する改良版
実践的なシステムを達成するために、対象設定広告で使用されるＵＰＩの量を削減する、及び／又はＵＰＩを順序付けることが所望されるようになる、又は必要になる。本発明は、情報と精度の最小限の損失でこのような削減を可能にする。さらに、広告の供給における、ひいてはＵＰＩの検索における待ち時間を制約することが、望ましい又は必要である可能性があるので、広告サーバは限られたＵＰＩで、あるいはＵＰＩなしで動作する必要がある場合もある。本発明にしたがった方法で優先順位を設定することにより、広告サーバは対象設定プロセス中に使用可能な貴重な（例えば最も貴重な）情報に焦点を当てることができる。データ削減及び処理優先順位の設定のための例示的な技法が後述される。
【００９８】
本発明の一実施形態では、少なくともいくつかのＵＰＩ属性のそれぞれが、関連付けられたスコア（重要性重み、確率等）を有する。複数のＵＰＩ属性の重要性重みは、何らかの方法でともに分類されるあるいは集約されてよい。
【００９９】
当初、ＵＰＩ属性に割り当てられる重要性重みは、おそらく特に一種の情報を使用して決定されてよい。例えば、検索クエリーは、ユーザが表示したウェブページから抽出されるｎグラムより高い初期重みを有してよい。
【０１００】
ＵＰＩ属性の重要性重みは、特定のユーザの、又はユーザのグループのアクションに基づいて更新されてよい。例えば、（参照してここに組み込まれ、「第７９１号出願」と呼ばれる）２００３年６月２日に出願された、Ｓｔｅｖｅ Ｌａｗｒｅｎｃｅ、Ｍｅｈｒａｎ Ｓａｈａｍｉ及びＡｍｉｔ Ｓｉｎｇｈａｌを発明者として示す「ユーザ要求情報とユーザ情報を使用して広告を供給すること（ＳＥＲＶＩＮＧ ＡＤＶＥＲＴＩＳＥＭＥＮＴＳ ＵＳＩＮＧ ＵＳＥＲ ＲＥＱＵＥＳＴ ＩＮＦＯＲＭＡＴＩＯＮ ＡＮＤ ＵＳＥＲ ＩＮＦＯＲＭＡＴＩＯＮ）」と題される米国特許出願第１０／４５２，７９１号の図９は、本発明にしたがった方法で広告ＵＰＩ又はユーザＵＰＩを管理するために使用されてよい例示的な方法を示す。例えば、その例示的な方法では、ユーザが広告を選択すると、推奨されているこの広告につながったユーザＵＰＩ属性の重要性重みが増加してよい。重要性重み（複数の場合がある）が増す量（絶対又は相対）は、各ＵＰＩ属性が広告推奨スコアにどの程度貢献したのかに少なくとも部分的に依存してよい。同様に、関連性のあるＵＰＩ属性の重要性重みは、ユーザが広告を選択しないときには削減されてよい。本発明の一実施形態では、重み削減係数は重み増加係数より小さい。
【０１０１】
本発明の一実施形態では、重要性重みは随意的に、ＵＰＩ属性が全ユーザ全体で（絶対的及び／又は相対的に）どの程度頻繁に優れた推奨策を生じさせたのかに基づいて大局的な重みを使用して（例えば結合されて）調整されてよい。代わりに、又は加えて、重要性重みは、ＵＰＩ属性が随意的に（例えばすべての類似した）ユーザのグループ全体で（絶対的に及び／又は相対的に）どの程度頻繁に優れた推奨策を生じさせたのかに基づいて、同一性重みを使用して（例えば結合されて）調整されてよい。
【０１０２】
本発明の一実施形態では、ＵＰＩは特定のサイズに達すると、それは少なくとも重要性重みを使用して情報のあまり重要でない項目を削除することによって削減されてよい。ＵＰＩ属性の記憶要件も検討されてよい。このようにして、多くの記憶域を必要とするが、低い重要性重みを有するＵＰＩ属性は削除の第一の候補となるであろう。
【０１０３】
本発明の一実施形態は、個々のＵＰＩ属性をその重要性重みを使用して順序付けることが（そして記憶することも）できる。このような実施形態では、既定のユーザＵＰＩに対する要求は（重要性重みという点で）最も重要な属性だけを含む不完全なＵＰＩを供給されることがある、あるいは十分な情報が取得されるまで、及び／又は追加の処理が望ましくない又は可能ではなくなるまで断片的に供給されてよい。したがって、例えば、ＵＰＩ属性を使用して処理することは、その重要性重みの順序で行われてよい。これにより、（例えば、効率のために、何らかの待ち時間制約を満たし、処理が特定の期限内に完了されることを確実にするために等）処理を早期に終了することができる。
【０１０４】
新しいＵＰＩ属性が追加されるにつれ、既存の属性の重要性重みが変更される可能性がある。その結果、（例えば既定のユーザの）ＵＰＩ属性の順序は重要性重み順序と異なる可能性がある。したがって、本発明は、それぞれの重要性重みを使用して（例えば、これに従って）ＵＰＩ属性を周期的に順序付けし直すために使用されてよい。
【０１０５】
いくつかのケースでは、ＵＰＩの転送又は処理は、（例えば既定のユーザの）ＵＰＩが重要性重みを使用して（例えば、これに従って）順序付け直される前に概算の順序で実行されてよい。少なくともいくつかの例及び／又はいくつかの実施形態では、その順序で効率的に転送及び／又は処理されるこのような情報のそれぞれの重要性重みの順序で、ＵＰＩ属性を物理的に記憶することが必要ではない可能性があることに留意されたい。実際に、少なくともいくつかの例及び／又はいくつかの実施形態では、重要性順序でＵＰＩ属性を転送する及び／又は処理することが必要ではない可能性がある。例えば、条件によっては、すべての情報は転送される、及び／又は処理されてよい。
【０１０６】
第４．４項 結論
前記開示から理解できるように、本発明はキーワード対象設定広告システムだけではなく、コンテンツ対象設定広告システムも改善するために使用できる。ユーザ、文書、広告及び／又は広告待ち受けページのユーザプロファイル情報は、受け入れることができる、及び／又は推測できる。
【特許請求の範囲】
【請求項１】
ユーザのためのユーザプロファイル情報を決定するための方法であって、
ａ）前記ユーザのための初期ユーザプロファイル情報を決定することと、
ｂ）前記ユーザのためのユーザプロファイル情報を推測することと、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記ユーザのための前記ユーザプロファイル情報を決定することと、
を備える、方法。
【請求項２】
前記ユーザのための初期ユーザプロファイル情報を決定する前記行為は、前記ユーザにより提出される過去の検索クエリーを使用する、請求項１に記載の方法。
【請求項３】
前記ユーザのための初期ユーザプロファイル情報を決定する前記行為は、前記ユーザによる過去の文書選択を使用する、請求項１に記載の方法。
【請求項４】
前記ユーザのための初期ユーザプロファイル情報を決定する前記行為は、（ｉ）前記ユーザによって提出された過去の検索クエリーと、（ｉｉ）前記ユーザによる過去の文書選択を使用する、請求項１に記載の方法。
【請求項５】
前記初期ユーザプロファイルは複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項１に記載の方法。
【請求項６】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項５に記載の方法。
【請求項７】
前記ユーザのためのユーザプロファイル情報を推測する前記行為は、
ｉ）多くの文書と前記ユーザのそれぞれにノードを定義することと、
ｉｉ）グラフを定義するためにノード間に関連がある場合に、ノード間でエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーを使用する前記ユーザのためのユーザプロファイル情報、及び他の文書のユーザプロファイル情報を推測することと、
を含む、請求項１に記載の方法。
【請求項８】
第１のノードに対応する文書が第２のノードに対応する前記ユーザからの検索クエリーに対して検索結果ページで返された場合に、前記第１のノードと前記第２のノードの間にエッジが加えられる、請求項７に記載の方法。
【請求項９】
第１のノードに対応する文書が第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１０】
第１のノードに対応する文書が第２のノードに対応する文書とリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１１】
第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことのあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１２】
第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされる１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１３】
前記グラフのトポロジーを使用して前記ユーザのためのユーザプロファイル情報を推測する前記行為は、
ｉ）第１の積を生成するために、第１の値で前記ユーザの前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を加算することと、
を含む、請求項７に記載の方法。
【請求項１４】
文書のユーザプロファイル情報を決定する方法であって、
ａ）前記文書のための初期ユーザプロファイル情報を決定することと、
ｂ）前記文書のためのユーザプロファイル情報を推測することと、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記文書のための前記ユーザプロファイル情報を決定することと、
を備える、方法。
【請求項１５】
前記文書のための初期ユーザプロファイル情報を決定する前記行為は、前記文書からのコンテンツ情報を使用する、請求項１４に記載の方法。
【請求項１６】
前記文書のための初期ユーザプロファイル情報を決定する前記行為は、文書メタ情報を使用する、請求項１４に記載の方法。
【請求項１７】
前記文書のための初期ユーザプロファイル情報を決定する前記行為は、（ｉ）前記文書からのコンテンツ情報、及び（ｉｉ）文書メタ情報を使用する、請求項１４に記載の方法。
【請求項１８】
前記初期ユーザプロファイル情報は複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項１４に記載の方法。
【請求項１９】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項１８に記載の方法。
【請求項２０】
前記文書のためのユーザプロファイル情報を推測する前記行為は、
ｉ）多くの文書のそれぞれに、及び多くのユーザのそれぞれにノードを定義することと、
ｉｉ）グラフを定義するために前記ノード間に関連がある場合に、ノード間にエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーを使用する前記文書のためのユーザプロファイル情報、及びユーザの、及び他の文書のユーザプロファイル情報を推測することと、
を含む、請求項１４に記載の方法。
【請求項２１】
第１のノードに対応する文書が、第２のノードに対応する前記ユーザからの検索クエリーに対する検索結果ページに戻された場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２２】
第１のノードに対応する文書が、第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２３】
第１のノードに対応する文書が、第２のノードに対応する文書とリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２４】
第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことのあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２５】
第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされた１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２６】
前記グラフのトポロジーを使用して前記文書のためのユーザプロファイル情報を推測する前記行為が、
ｉ）第１の積を生成するために、第１の値で前記文書の前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を加算することと、
を含む、請求項２０に記載の方法。
【請求項２７】
広告を採点するために使用される一致を決定するための方法であって、
ａ）前記広告の広告待ち受けページのユーザプロファイル情報と、前記広告の対象を設定するために使用されるユーザプロファイル情報の少なくとも１つ、及び（Ｂ）前記広告が表示されるユーザのユーザプロファイル情報を使用して、第１の一致値を求めることと、
ｂ）（Ａ）広告の広告待ち受けページのユーザプロファイル情報と、広告の対象を設定するために使用されるユーザプロファイル情報の少なくとも１つ、及び（Ｂ）前記広告が供給される文書のユーザプロファイル情報を使用して、第２の一致値を求めることと、
ｃ）前記第１の一致値と前記第２の一致値を使用して、前記広告を採点するために使用される前記一致を決定することと、
を備える、方法。
【請求項２８】
前記広告の前記広告待ち受けページの前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項２９】
前記広告の対象設定に使用される前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項３０】
前記ユーザの前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項３１】
前記文書の前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項３２】
前記ユーザプロファイル情報は、
−（Ａ）地理的地域、（Ｂ）話題、（Ｃ）ユーザ年齢範囲、（Ｄ）言語を含む幅広い属性の集合から選択される、少なくとも１つの幅広い属性と、
−（Ａ）単語と（Ｂ）句を含む狭い属性の集合から選択される少なくとも１つの狭い属性と、
を含む、請求項２７に記載の方法。
【請求項３３】
ユーザのためのユーザプロファイル情報を決定するための装置であって、
ａ）前記ユーザのための初期ユーザプロファイル情報を決定するための手段と、
ｂ）前記ユーザのためのユーザプロファイル情報を推測するための手段と、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記ユーザの前記ユーザプロファイル情報を決定するための手段と、
を備える、装置。
【請求項３４】
前記ユーザのための初期ユーザプロファイル情報を決定するための前記手段は、前記ユーザによって提出された過去の検索クエリーを使用する、請求項３３に記載の装置。
【請求項３５】
前記ユーザのための初期ユーザプロファイル情報を決定するための手段が、前記ユーザによる過去の文書選択を使用する、請求項３３に記載の装置。
【請求項３６】
前記ユーザのための初期ユーザプロファイル情報を決定するための前記手段は、（ｉ）前記ユーザによって提出された過去の検索クエリーと、（ｉｉ）前記ユーザによる過去の文書選択とを使用する、請求項３３に記載の装置。
【請求項３７】
前記初期ユーザプロファイルは複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項３３に記載の装置。
【請求項３８】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項３７に記載の装置。
【請求項３９】
前記ユーザのためのユーザプロファイル情報を推測するための前記手段は、
ｉ）多くの文書と前記ユーザのそれぞれにノードを定義することと、
ｉｉ）グラフを定義するために前記ノード間に関連がある場合に、ノード間にエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーと他の文書のユーザプロファイル情報を使用する、前記ユーザのユーザプロファイル情報を推測することと、
のための手段を含む、請求項３７に記載の装置。
【請求項４０】
エッジを追加するための手段は、第１のノードに対応する文書が第２のノードに対応する前記ユーザからの検索クエリーに対して検索結果ページで返された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４１】
エッジを追加するための前記手段は、第１のノードに対応する文書が第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４２】
エッジを追加するための前記手段は、第１のノードに対応する文書が第２のノードに対応する文書とリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４３】
エッジを追加するための前記手段は、第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことがあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４４】
エッジを追加するための前記手段は、第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされる１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４５】
前記グラフのトポロジーを使用する、前記ユーザのためのユーザプロファイル情報を推測するための手段が、
ｉ）第１の積を生成するために、第１の値で前記ユーザの前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を追加すること、
のための手段を含む、請求項３９に記載の方法。
【請求項４６】
文書のためのユーザプロファイル情報を決定するための装置であって、
ａ）前記文書のための初期ユーザプロファイル情報を決定するための手段と、
ｂ）前記文書のためのユーザプロファイル情報を推測するための手段と、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記文書のためのユーザプロファイル情報を決定するための手段と、
を備える、装置。
【請求項４７】
前記文書のための初期ユーザプロファイル情報を決定するための前記手段は、前記文書からコンテンツ情報を使用する、請求項４６に記載の装置。
【請求項４８】
前記文書のための初期ユーザプロファイル情報を決定するための前記手段は、文書メタ情報を使用する、請求項４６に記載の装置。
【請求項４９】
前記文書のための初期ユーザプロファイル情報を決定するための前記手段は、（ｉ）前記文書からのコンテンツ情報と、（ｉｉ）文書メタ情報を使用する、請求項４６に記載の装置。
【請求項５０】
前記初期ユーザプロファイル情報は複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項４６に記載の装置。
【請求項５１】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項５０に記載の装置。
【請求項５２】
前記文書のためのユーザプロファイル情報を推測するための前記手段は、
ｉ）多くの文書のそれぞれに対し、及び多くのユーザのそれぞれに対してノードを定義することと、
ｉｉ）グラフを定義するためにノード間に関連がある場合に、ノード間にエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーと、ユーザ及び他の文書のユーザプロファイル情報を使用して、前記文書のためのユーザプロファイル情報を推測すること、
のための手段を含む、請求項４６に記載の装置。
【請求項５３】
エッジを追加するための前記手段は、第１のノードに対応する文書が、第２のノードに対応する前記ユーザからの検索クエリーに検索結果ページで返された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５４】
エッジを追加するための前記手段は、第１のノードに対応する文書が第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５５】
エッジを追加する前記手段は、第１のノードに対応する文書が第２のノードに対応する文書にリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５６】
エッジを追加する前記手段は、第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことのあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５７】
エッジを追加するための前記手段は、第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされた１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５８】
前記グラフのトポロジーを使用する前記文書のためのユーザプロファイル情報を推測する前記手段は、
ｉ）第１の積を生成するために、第１の値で前記文書の前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を加算すること、
のための手段を含む、請求項５２に記載の装置。
【請求項５９】
広告を採点するために使用される一致を決定するための装置であって、
ａ）（Ａ）前記広告の広告待ち受けページのユーザプロファイル情報と、前記ユーザの対象設定のために使用されるユーザプロファイル情報のうち少なくとも１つと、（Ｂ）前記広告が表示されるユーザのユーザプロファイル情報とを使用して、第１の一致値を求めるための手段と、
ｂ）前記広告の広告待ち受けページのユーザプロファイル情報と、前記広告の対象設定のために使用されるユーザプロファイル情報の少なくとも１つと、（Ｂ）前記広告が供給される文書のユーザプロファイル情報を使用して、第２の一致値を求めるための手段と、
ｃ）前記第１の一致値と前記第２の一致値を使用して広告を採点するために使用される前記一致を決定するための手段と、
を備える、装置。
【請求項６０】
前記広告の前記広告待ち受けページの前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６１】
前記広告の対象設定のために使用される、前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６２】
前記ユーザのための前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６３】
前記文書の前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６４】
前記ユーザプロファイル情報は、
−（Ａ）地理的地域、（Ｂ）話題、（Ｃ）ユーザ年齢範囲、（Ｄ）言語を含む幅広い属性の集合から選択される、少なくとも１つの幅広い属性と、
−（Ａ）単語と（Ｂ）句を含む狭い属性の集合から選択される、少なくとも１つの狭い属性と、
を含む、請求項５９に記載の方法。
【請求項１】
ユーザのためのユーザプロファイル情報を決定するための方法であって、
ａ）前記ユーザのための初期ユーザプロファイル情報を決定することと、
ｂ）前記ユーザのためのユーザプロファイル情報を推測することと、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記ユーザのための前記ユーザプロファイル情報を決定することと、
を備える、方法。
【請求項２】
前記ユーザのための初期ユーザプロファイル情報を決定する前記行為は、前記ユーザにより提出される過去の検索クエリーを使用する、請求項１に記載の方法。
【請求項３】
前記ユーザのための初期ユーザプロファイル情報を決定する前記行為は、前記ユーザによる過去の文書選択を使用する、請求項１に記載の方法。
【請求項４】
前記ユーザのための初期ユーザプロファイル情報を決定する前記行為は、（ｉ）前記ユーザによって提出された過去の検索クエリーと、（ｉｉ）前記ユーザによる過去の文書選択を使用する、請求項１に記載の方法。
【請求項５】
前記初期ユーザプロファイルは複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項１に記載の方法。
【請求項６】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項５に記載の方法。
【請求項７】
前記ユーザのためのユーザプロファイル情報を推測する前記行為は、
ｉ）多くの文書と前記ユーザのそれぞれにノードを定義することと、
ｉｉ）グラフを定義するためにノード間に関連がある場合に、ノード間でエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーを使用する前記ユーザのためのユーザプロファイル情報、及び他の文書のユーザプロファイル情報を推測することと、
を含む、請求項１に記載の方法。
【請求項８】
第１のノードに対応する文書が第２のノードに対応する前記ユーザからの検索クエリーに対して検索結果ページで返された場合に、前記第１のノードと前記第２のノードの間にエッジが加えられる、請求項７に記載の方法。
【請求項９】
第１のノードに対応する文書が第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１０】
第１のノードに対応する文書が第２のノードに対応する文書とリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１１】
第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことのあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１２】
第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされる１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項７に記載の方法。
【請求項１３】
前記グラフのトポロジーを使用して前記ユーザのためのユーザプロファイル情報を推測する前記行為は、
ｉ）第１の積を生成するために、第１の値で前記ユーザの前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を加算することと、
を含む、請求項７に記載の方法。
【請求項１４】
文書のユーザプロファイル情報を決定する方法であって、
ａ）前記文書のための初期ユーザプロファイル情報を決定することと、
ｂ）前記文書のためのユーザプロファイル情報を推測することと、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記文書のための前記ユーザプロファイル情報を決定することと、
を備える、方法。
【請求項１５】
前記文書のための初期ユーザプロファイル情報を決定する前記行為は、前記文書からのコンテンツ情報を使用する、請求項１４に記載の方法。
【請求項１６】
前記文書のための初期ユーザプロファイル情報を決定する前記行為は、文書メタ情報を使用する、請求項１４に記載の方法。
【請求項１７】
前記文書のための初期ユーザプロファイル情報を決定する前記行為は、（ｉ）前記文書からのコンテンツ情報、及び（ｉｉ）文書メタ情報を使用する、請求項１４に記載の方法。
【請求項１８】
前記初期ユーザプロファイル情報は複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項１４に記載の方法。
【請求項１９】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項１８に記載の方法。
【請求項２０】
前記文書のためのユーザプロファイル情報を推測する前記行為は、
ｉ）多くの文書のそれぞれに、及び多くのユーザのそれぞれにノードを定義することと、
ｉｉ）グラフを定義するために前記ノード間に関連がある場合に、ノード間にエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーを使用する前記文書のためのユーザプロファイル情報、及びユーザの、及び他の文書のユーザプロファイル情報を推測することと、
を含む、請求項１４に記載の方法。
【請求項２１】
第１のノードに対応する文書が、第２のノードに対応する前記ユーザからの検索クエリーに対する検索結果ページに戻された場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２２】
第１のノードに対応する文書が、第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２３】
第１のノードに対応する文書が、第２のノードに対応する文書とリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２４】
第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことのあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２５】
第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされた１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジが追加される、請求項２０に記載の方法。
【請求項２６】
前記グラフのトポロジーを使用して前記文書のためのユーザプロファイル情報を推測する前記行為が、
ｉ）第１の積を生成するために、第１の値で前記文書の前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を加算することと、
を含む、請求項２０に記載の方法。
【請求項２７】
広告を採点するために使用される一致を決定するための方法であって、
ａ）前記広告の広告待ち受けページのユーザプロファイル情報と、前記広告の対象を設定するために使用されるユーザプロファイル情報の少なくとも１つ、及び（Ｂ）前記広告が表示されるユーザのユーザプロファイル情報を使用して、第１の一致値を求めることと、
ｂ）（Ａ）広告の広告待ち受けページのユーザプロファイル情報と、広告の対象を設定するために使用されるユーザプロファイル情報の少なくとも１つ、及び（Ｂ）前記広告が供給される文書のユーザプロファイル情報を使用して、第２の一致値を求めることと、
ｃ）前記第１の一致値と前記第２の一致値を使用して、前記広告を採点するために使用される前記一致を決定することと、
を備える、方法。
【請求項２８】
前記広告の前記広告待ち受けページの前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項２９】
前記広告の対象設定に使用される前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項３０】
前記ユーザの前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項３１】
前記文書の前記ユーザプロファイル情報の少なくとも一部が推測された、請求項２７に記載の方法。
【請求項３２】
前記ユーザプロファイル情報は、
−（Ａ）地理的地域、（Ｂ）話題、（Ｃ）ユーザ年齢範囲、（Ｄ）言語を含む幅広い属性の集合から選択される、少なくとも１つの幅広い属性と、
−（Ａ）単語と（Ｂ）句を含む狭い属性の集合から選択される少なくとも１つの狭い属性と、
を含む、請求項２７に記載の方法。
【請求項３３】
ユーザのためのユーザプロファイル情報を決定するための装置であって、
ａ）前記ユーザのための初期ユーザプロファイル情報を決定するための手段と、
ｂ）前記ユーザのためのユーザプロファイル情報を推測するための手段と、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記ユーザの前記ユーザプロファイル情報を決定するための手段と、
を備える、装置。
【請求項３４】
前記ユーザのための初期ユーザプロファイル情報を決定するための前記手段は、前記ユーザによって提出された過去の検索クエリーを使用する、請求項３３に記載の装置。
【請求項３５】
前記ユーザのための初期ユーザプロファイル情報を決定するための手段が、前記ユーザによる過去の文書選択を使用する、請求項３３に記載の装置。
【請求項３６】
前記ユーザのための初期ユーザプロファイル情報を決定するための前記手段は、（ｉ）前記ユーザによって提出された過去の検索クエリーと、（ｉｉ）前記ユーザによる過去の文書選択とを使用する、請求項３３に記載の装置。
【請求項３７】
前記初期ユーザプロファイルは複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項３３に記載の装置。
【請求項３８】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項３７に記載の装置。
【請求項３９】
前記ユーザのためのユーザプロファイル情報を推測するための前記手段は、
ｉ）多くの文書と前記ユーザのそれぞれにノードを定義することと、
ｉｉ）グラフを定義するために前記ノード間に関連がある場合に、ノード間にエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーと他の文書のユーザプロファイル情報を使用する、前記ユーザのユーザプロファイル情報を推測することと、
のための手段を含む、請求項３７に記載の装置。
【請求項４０】
エッジを追加するための手段は、第１のノードに対応する文書が第２のノードに対応する前記ユーザからの検索クエリーに対して検索結果ページで返された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４１】
エッジを追加するための前記手段は、第１のノードに対応する文書が第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４２】
エッジを追加するための前記手段は、第１のノードに対応する文書が第２のノードに対応する文書とリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４３】
エッジを追加するための前記手段は、第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことがあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４４】
エッジを追加するための前記手段は、第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされる１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項３９に記載の装置。
【請求項４５】
前記グラフのトポロジーを使用する、前記ユーザのためのユーザプロファイル情報を推測するための手段が、
ｉ）第１の積を生成するために、第１の値で前記ユーザの前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を追加すること、
のための手段を含む、請求項３９に記載の方法。
【請求項４６】
文書のためのユーザプロファイル情報を決定するための装置であって、
ａ）前記文書のための初期ユーザプロファイル情報を決定するための手段と、
ｂ）前記文書のためのユーザプロファイル情報を推測するための手段と、
ｃ）前記初期ユーザプロファイル情報と前記推測されたユーザプロファイル情報の両方を使用して、前記文書のためのユーザプロファイル情報を決定するための手段と、
を備える、装置。
【請求項４７】
前記文書のための初期ユーザプロファイル情報を決定するための前記手段は、前記文書からコンテンツ情報を使用する、請求項４６に記載の装置。
【請求項４８】
前記文書のための初期ユーザプロファイル情報を決定するための前記手段は、文書メタ情報を使用する、請求項４６に記載の装置。
【請求項４９】
前記文書のための初期ユーザプロファイル情報を決定するための前記手段は、（ｉ）前記文書からのコンテンツ情報と、（ｉｉ）文書メタ情報を使用する、請求項４６に記載の装置。
【請求項５０】
前記初期ユーザプロファイル情報は複数の属性を含み、前記複数の属性のそれぞれが値及びスコアを有する、請求項４６に記載の装置。
【請求項５１】
前記スコアは、前記属性の前記値が正しい尤度を示す、請求項５０に記載の装置。
【請求項５２】
前記文書のためのユーザプロファイル情報を推測するための前記手段は、
ｉ）多くの文書のそれぞれに対し、及び多くのユーザのそれぞれに対してノードを定義することと、
ｉｉ）グラフを定義するためにノード間に関連がある場合に、ノード間にエッジを追加することと、
ｉｉｉ）前記グラフのトポロジーと、ユーザ及び他の文書のユーザプロファイル情報を使用して、前記文書のためのユーザプロファイル情報を推測すること、
のための手段を含む、請求項４６に記載の装置。
【請求項５３】
エッジを追加するための前記手段は、第１のノードに対応する文書が、第２のノードに対応する前記ユーザからの検索クエリーに検索結果ページで返された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５４】
エッジを追加するための前記手段は、第１のノードに対応する文書が第２のノードに対応する前記ユーザによって選択された場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５５】
エッジを追加する前記手段は、第１のノードに対応する文書が第２のノードに対応する文書にリンクされる場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５６】
エッジを追加する前記手段は、第１のノードに対応する文書が、第２のノードに対応する別の文書にアクセスしたことのあるユーザの集合によってアクセスされた場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５７】
エッジを追加するための前記手段は、第１のノードに対応するユーザが、第２のノードに対応する別のユーザによってもアクセスされた１つ以上の文書の集合にアクセスした場合に、前記第１のノードと前記第２のノードの間にエッジを追加する、請求項５２に記載の装置。
【請求項５８】
前記グラフのトポロジーを使用する前記文書のためのユーザプロファイル情報を推測する前記手段は、
ｉ）第１の積を生成するために、第１の値で前記文書の前記初期ユーザプロファイル情報を乗算することと、
ｉｉ）第２の積を生成するために、第２の値で近接するグラフノードのユーザプロファイル情報を乗算することと、
ｉｉｉ）前記第１の積と前記第２の積を加算すること、
のための手段を含む、請求項５２に記載の装置。
【請求項５９】
広告を採点するために使用される一致を決定するための装置であって、
ａ）（Ａ）前記広告の広告待ち受けページのユーザプロファイル情報と、前記ユーザの対象設定のために使用されるユーザプロファイル情報のうち少なくとも１つと、（Ｂ）前記広告が表示されるユーザのユーザプロファイル情報とを使用して、第１の一致値を求めるための手段と、
ｂ）前記広告の広告待ち受けページのユーザプロファイル情報と、前記広告の対象設定のために使用されるユーザプロファイル情報の少なくとも１つと、（Ｂ）前記広告が供給される文書のユーザプロファイル情報を使用して、第２の一致値を求めるための手段と、
ｃ）前記第１の一致値と前記第２の一致値を使用して広告を採点するために使用される前記一致を決定するための手段と、
を備える、装置。
【請求項６０】
前記広告の前記広告待ち受けページの前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６１】
前記広告の対象設定のために使用される、前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６２】
前記ユーザのための前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６３】
前記文書の前記ユーザプロファイル情報の少なくとも一部が推測された、請求項５９に記載の装置。
【請求項６４】
前記ユーザプロファイル情報は、
−（Ａ）地理的地域、（Ｂ）話題、（Ｃ）ユーザ年齢範囲、（Ｄ）言語を含む幅広い属性の集合から選択される、少なくとも１つの幅広い属性と、
−（Ａ）単語と（Ｂ）句を含む狭い属性の集合から選択される、少なくとも１つの狭い属性と、
を含む、請求項５９に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１７６６７５（Ｐ２０１０−１７６６７５Ａ）
【公開日】平成２２年８月１２日（２０１０．８．１２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−１８７７４（Ｐ２０１０−１８７７４）
【出願日】平成２２年１月２９日（２０１０．１．２９）
【分割の表示】特願２００６−５４７２５７（Ｐ２００６−５４７２５７）の分割
【原出願日】平成１６年１２月２１日（２００４．１２．２１）
【出願人】（５０２２０８３９７）グーグル インコーポレイテッド (161)
【Ｆターム（参考）】
【公開日】平成２２年８月１２日（２０１０．８．１２）
【国際特許分類】
【出願番号】特願２０１０−１８７７４（Ｐ２０１０−１８７７４）
【出願日】平成２２年１月２９日（２０１０．１．２９）
【分割の表示】特願２００６−５４７２５７（Ｐ２００６−５４７２５７）の分割
【原出願日】平成１６年１２月２１日（２００４．１２．２１）
【出願人】（５０２２０８３９７）グーグル インコーポレイテッド (161)
【Ｆターム（参考）】
[ Back to top ]