(57)【特許請求の範囲】
【請求項１】
コンピューティングデバイスによって実行される、Ｗｅｂページの広告イメージを識別する方法であって、
前記方法は、
Ｗｅｂページのトレーニングイメージを提供するステップであって、該提供されたそれぞれのトレーニングイメージはＷｅｂページによって参照される、ステップと、
前記イメージに広告イメージまたは非広告イメージのラベルを付けるステップと、
前記トレーニングイメージの各々についての特徴ベクトルを生成するステップであって、前記特徴ベクトルは、前記イメージのＷｅｂページから導き出されたビジュアルレイアウトフィーチャおよび前記イメージのコンテンツから導き出されたコンテンツフィーチャを含み、該コンテンツフィーチャは、前記イメージのコンテンツの異なるカラーの数、前記イメージがハイコントラストであるか否かの表示、および前記イメージがフォトグラフであるか否かの表示を含むグループから選択される、ステップと、
前記特徴ベクトルおよび前記イメージのラベルを使用してバイナリクラシファイアをトレーニングするステップと、
前記イメージについての特徴ベクトルを生成し、トレーニングしたバイナリクラシファイアを前記イメージの前記生成された特徴ベクトルに適用することによって前記イメージを広告イメージまたは非広告イメージとして分類するステップと
を含むことを特徴とする方法。
【請求項２】
イメージを広告イメージおよび非広告イメージとして分類するために関連フィーチャを学習するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記学習するステップは、アダプティブブースティング手法を適用して、各々の弱いクラシファイアがフィーチャに対応している弱いクラシファイアのウエイトを学習すること、およびそのウエイトが広告イメージを非広告イメージから区別するのに有効であることを示しているフィーチャを関連フィーチャとして選択することをさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】
イメージのフィーチャは、ビジュアルレイアウトフィーチャおよびコンテンツフィーチャを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記ビジュアルレイアウトフィーチャは、イメージの上部、右側および左側の座標、イメージの中心の座標、イメージの幅、イメージと同じ右座標をもつＷｅｂページのイメージの数、イメージと同じ上部座標をもつＷｅｂページのイメージの数、イメージと同じ右座標および同じ幅をもつＷｅｂページのイメージの数、およびイメージと同じ上部座標および同じ高さをもつＷｅｂページのイメージの数を含むグループから選択されたフィーチャを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記コンテンツフィーチャは、イメージのサイズ、およびイメージのグレイが占める割合を含むグループから選択されたフィーチャを含むことを特徴とする請求項４に記載の方法。
【請求項７】
イメージのフィーチャは、ハイパーリンクから導き出されたフィーチャをさらに含むことを特徴とする請求項４に記載の方法。
【請求項８】
バイナリクラシファイアは、サポートベクターマシンを使用してトレーニングされることを特徴とする請求項１に記載の方法。
【請求項９】
アダプティブブースティング手法を適用して、各々の弱いクラシファイアがフィーチャに対応している弱いクラシファイアのウエイトを学習し、そのウエイトが広告イメージを非広告イメージから区別するのに有効であることを示しているフィーチャを関連フィーチャとして選択することによってイメージを広告イメージおよび非広告イメージとして分類するために関連フィーチャを学習することをさらに含み、
イメージのフィーチャは、ビジュアルレイアウトフィーチャおよびコンテンツフィーチャを含むことを特徴とする請求項８に記載の方法。
【請求項１０】
特徴ベクトルに含められるイメージのフィーチャは、候補フィーチャを使用してクラシファイアをトレーニングし、前記クラシファイアによって最も重く重み付けされたフィーチャを関連フィーチャとして選択することによって学習されることを特徴とする請求項１に記載の方法。
【請求項１１】
Ｗｅｂページのイメージを広告イメージまたは非広告イメージとして分類するバイナリクラシファイアを生成する方法をコンピュータに実行させるためのコンピュータ実行可能命令を格納したコンピュータ読み取り可能な記憶媒体であって、
前記コンピュータ実行可能命令は、実行される時に、
トレーニングＷｅｂページを提供するステップと、
前記トレーニングＷｅｂページのイメージを識別するステップと、
イメージが広告イメージであるのか、または非広告イメージであるのかを示す、前記イメージについてのラベルを受信するステップと、
前記識別されたイメージの各々についての特徴ベクトルを生成するステップであって、前記特徴ベクトルは、前記Ｗｅｂページ上のイメージのビジュアルレイアウトフィーチャおよび前記イメージのコンテンツにアクセスすることによって前記イメージのコンテンツから導き出されたコンテンツフィーチャを含み、前記コンテンツフィーチャは、前記イメージのアスペクト比、イメージフォーマット、前記イメージがフォトグラフであるかグラフィックであるかの表示、前記イメージのサイズ、前記イメージの異なるカラーの数、前記イメージのグレイエリアが占める割合、および前記イメージがハイコントラストであるかどうかの表示を含むグループから選択される、ステップと、
前記特徴ベクトルおよび前記イメージのラベルを使用してバイナリクラシファイアをトレーニングするステップであって、該トレーニングするステップは、イメージを分類する際に使用されるフィーチャのウエイトを識別する、ステップと
を含む方法をコンピュータに実行させることを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１２】
イメージについての特徴ベクトルを生成し、トレーニングしたバイナリクラシファイアを前記イメージの前記生成された特徴ベクトルに適用することによってイメージを広告イメージまたは非広告イメージとして分類するステップをさらに含むことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１３】
イメージを広告イメージおよび非広告イメージとして分類する関連フィーチャを学習するステップをさらに含むことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１４】
前記学習するステップは、アダプティブブースティング手法を適用して、フィーチャに固有の弱いクラシファイアのウエイトを学習すること、およびそのウエイトが広告イメージを非広告イメージと区別するのに有効であることを示している弱いクラシファイアのフィーチャを関連フィーチャとして選択することを含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１５】
イメージのフィーチャは、コンテンツフィーチャを含むことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１６】
バイナリクラシファイアは、サポートベクターマシンを使用してトレーニングされることを特徴とする請求項１１に記載のコンピュータ読み取り可能な記憶媒体。
【請求項１７】
イメージを広告イメージまたは非広告イメージとして分類する際に使用されるＷｅｂページのイメージのフィーチャを識別するコンピューティングデバイスであって、
Ｗｅｂページのイメージを検索し、前記Ｗｅｂページの検索されたイメージについての特徴ベクトルをトレーニングデータストアに格納するコンポーネントであって、前記検索されたイメージは、広告イメージまたは非広告イメージとラベル付けされ、前記特徴ベクトルは、前記イメージのＷｅｂページから導き出されたビジュアルレイアウトコンテンツおよび前記検索されたイメージのコンテンツにアクセスすることによって前記検索されたイメージのコンテンツから導き出されたコンテンツフィーチャを含む候補フィーチャを含み、前記コンテンツフィーチャは、前記イメージのアスペクト比、イメージフォーマット、前記イメージがフォトグラフであるかグラフィックであるかの表示、前記イメージのサイズ、前記イメージの異なるカラーの数、前記イメージのグレイエリアが占める割合、および前記イメージがハイコントラストであるかどうかの表示を含むグループから選択される、コンポーネントと、
前記トレーニングデータストアの候補フィーチャおよびラベルをもつ前記特徴ベクトルを使用してバイナリクラシファイアをトレーニングするコンポーネントと、
そのウエイトが広告イメージと非広告イメージとを区別するのに有効であると示している候補フィーチャを、イメージを分類する際に使用するフィーチャとして選択するコンポーネントと
を備えたことを特徴とするコンピューティングデバイス。
【請求項１８】
選択したフィーチャを使用してイメージを広告イメージおよび非広告イメージとして分類するようにバイナリクラシファイアをトレーニングするコンポーネントをさらに含むことを特徴とする請求項１７に記載のコンピューティングデバイス。
【請求項１９】
候補フィーチャを使用してトレーニングされるクラシファイアは、アダプティブブースティング手法を使用してトレーニングされ、選択したフィーチャを使用してトレーニングされるバイナリクラシファイアはサポートベクターマシン手法を使用してトレーニングされることを特徴とする請求項１８に記載のコンピューティングデバイス。
【請求項２０】
イメージについての選択したフィーチャの特徴ベクトルを生成し、トレーニングしたバイナリクラシファイアを前記イメージの前記生成した特徴ベクトルに適用することによってイメージを広告イメージまたは非広告イメージとして分類するコンポーネントをさらに含むことを特徴とする請求項１９に記載のコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広告イメージまたは非広告イメージとしてのイメージを分類する方法およびシステムに関する。
【背景技術】
【０００２】
多くのＷｅｂサイトのプロバイダは収入源としてオンライン広告に頼っている。プロバイダは、自身のＷｅｂサイトのＷｅｂページに組み込まれている広告を提供するためにサードパーティの広告サーバに頼ることがある。Ｗｅｂページが生成されるとき、広告スペースは、広告サーバを参照するハイパーリンクでもってＷｅｂページ上に割り振られることがある。Ｗｅｂページがブラウザによって表示されるとき、ブラウザはリクエストを広告サーバに送ることによってハイパーリンクを解決している。広告サーバは該当する広告を特定し、その広告をブラウザに返しているが、その広告には広告される内容に関係するＷｅｂページへのリンクが含まれていることがある。そのあと、ブラウザは広告をＷｅｂページの一部として表示している。Ｗｅｂページのプロバイダには、ユーザが広告のハイパーリンクを選択したときその広告についての報酬が支払われることがある。
【０００３】
収入増加の可能性を向上させるために、Ｗｅｂページのプロバイダは、Ｗｅｂページを広告で一杯にすることがある。しかし、Ｗｅｂページが広告で一杯になると、負の結果が生じるおそれがある。例えば、ハンドヘルドパーソナルコンピュータやセルフォン、ＰＤＡ（personal digital assistant）などのモバイルデバイスがインターネットにアクセスする方法としてますます普及している。残念ながら、これらのモバイルデバイスを使用してユーザが多数の広告を含むＷｅｂページにアクセスするときの経験は満足されるものではなかった。第一に、これらのモバイルデバイスは表示域が小さいため、多数の広告を含むＷｅｂページをこのような小さな表示域に効果的に表示することが困難になっている。第二に、これらのモバイルデバイスは、通信リンク（例えば、セルフォンネットワーク経由の）が比較的低速であるのが代表的であるため、アクセスしたＷｅｂページが広告で一杯になっているときそのＷｅｂページをダウンロードするのに容認し得ない程の長時間を要することがある。第三に、モバイルデバイスはコンピューティングパワーに制約があるため、広告で一杯になったＷｅｂページをレンダリングすることも、容認し得ない程の長時間を要することがある。
【０００４】
別の例として、多くの検索エンジンサービス（search engine service）は、Ｗｅｂページを介してアクセス可能なイメージを検索する機能を備えている。これらの検索エンジンサービスは、ユーザに関心のある可能性のあるイメージをユーザが検索するのを可能にしている。検索語（search term）を含む検索リクエスト（すなわち、クエリ）をユーザがサブミットしたあと、検索エンジンサービスは、これらの検索語に関係する可能性のあるイメージを特定する。関連するイメージの特定を高速化するために、検索エンジンサービスは、キーワードとイメージとを対応付けたマッピングまたはインデックスを維持していることがある。このマッピングは、イメージを収めているＷｅｂページのキーワードを特定するためにＷｅｂ（すなわち、ワールドワイドウェブをクローリング（crawling）することによって生成されることがある。Ｗｅｂをクローリングするために、検索エンジンサービスはルートＷｅｂページのリストを使用して、これらのルートＷｅｂページを通してアクセス可能であるすべてのＷｅｂページを特定することがある。検索エンジンサービスはＷｅｂページ上のあるイメージを特定すると、そのイメージをマッピングに追加する。Ｗｅｂページのイメージの多くは広告の一部であるイメージであるので、マッピングは広告のイメージを収めているが、これらの広告は、イメージを検索するユーザにとって関心がないのが一般的である。広告のイメージが非常に多数存在するときは、検索エンジンサービスがマッピングを生成するのに長い時間を要し、マッピングはより多くのシステムリソースを消費し、マッピングにアクセスするのに長い時間を要するため、検索結果にはユーザにとって関心のない広告のイメージが多数含まれていることがある。
【発明の概要】
【０００５】
表示ページのイメージを広告イメージまたは非広告イメージとして特定することが提供されている。広告イメージ分類システム（advertisement image classification system）は、イメージを広告イメージまたは非広告イメージとして分類するようにバイナリクラシファイア（binary classifier）をトレーニングし、そのあと、そのバイナリクラシファイアを使用してＷｅｂページなどの表示ページのイメージを広告イメージまたは非広告イメージとして分類する。トレーニングフェーズ期間に、分類システムはイメージを含むＷｅｂページを収集し、Ｗｅｂページのイメージを特定する。そのあと、分類システムは、各々のイメージについてそのイメージが広告イメージであるか、非広告イメージであるかを示すラベルを入力する。そのあと、分類システムは、各々のイメージについてイメージとそのＷｅｂページから導き出されたフィーチャを収めている特徴ベクトル（feature vector）を生成する。分類システムはイメージの特徴ベクトルとラベルを含むトレーニングデータを使用してイメージを分類するようにバイナリクラシファイアをトレーニングする。分類フェーズ期間に、分類システムはイメージを含むＷｅｂページを入力し、そのイメージの特徴ベクトルを生成する。そのあと、分類システムはトレーニングしたバイナリクラシファイアを特徴ベクトルに適用して、そのイメージが広告イメージであるか、または非広告イメージであるかを示すスコア（得点）を生成する。
【０００６】
この要約説明は、以下の「発明を実施するための形態」にて詳述される概念のいくつかを選んで簡単に紹介したものである。この要約説明は特許請求の範囲に記載の主題のキーとなる特徴または基本的特徴を特定するものでもなく、特許請求の範囲に記載の主題の範囲を判断する際の一助として使用されるものでもない。
【図面の簡単な説明】
【０００７】
【図１】一実施形態における分類システムのコンポーネントを示すブロック図である。
【図２】いくつかの実施形態におけるビジュアルレイアウトフィーチャを生成する際に使用されるファクタを示すブロック図である。
【図３】いくつかの実施形態における分類システムのクラシファイア生成コンポーネントの処理を示すフロー図である。
【図４】いくつかの実施形態における分類システムの特徴ベクトル生成コンポーネントの処理を示すフロー図である。
【図５】いくつかの実施形態における分類システムのイメージに対する特徴ベクトル生成コンポーネントの処理を示すフロー図である。
【図６】いくつかの実施形態における分類システムの関連フィーチャ学習コンポーネントの処理を示すフロー図である。
【図７】いくつかの実施形態における分類システムのイメージ分類コンポーネントの処理を示すフロー図である。
【図８】いくつかの実施形態における分類システムのフィーチャ生成コンポーネントの処理を示すフロー図である。
【発明を実施するための形態】
【０００８】
表示ページのイメージを広告イメージまたは非広告イメージとして特定することが提供されている。いくつかの実施形態において、広告イメージ分類システムは、イメージを広告イメージまたは非広告イメージとして分類するようにバイナリクラシファイア（binary classifier）をトレーニングし、そのあと、そのバイナリクラシファイアを使用してＷｅｂページなどの表示ページのイメージを広告イメージまたは非広告イメージとして分類する。トレーニングフェーズ期間に、分類システムはイメージを含むＷｅｂページを収集し、Ｗｅｂページのイメージを特定する。そのあと、分類システムは各々のイメージについて、そのイメージが広告イメージであるか、非広告イメージであるかを示すラベルを入力する。そのあと、分類システムは各々のイメージについて、そのイメージとそのＷｅｂページから導き出されたフィーチャを収めている特徴ベクトルを生成する。例えば、フィーチャには、イメージのサイズ、そのＷｅｂページ上のイメージの左側座標と上部座標、同じ左側座標をもつそのＷｅｂページ上のイメージの数、イメージの高さなどが含まれていることがある。分類システムは、イメージの特徴ベクトルとラベルを含んでいるトレーニングデータを使用してイメージを分類するようにバイナリクラシファイアをトレーニングする。分類システムは、サポートベクターマシン（ＳＶＭ）手法、ニューラルネットワーク手法、ベイジアン（Bayesian）手法などの、種々の手法を用いてバイナリクラシファイアをトレーニングすることができる。バイナリクラシファイアは、イメージを分類するとき各フィーチャに付与されるウエイトを示すフィーチャ・ウエイト（特徴重み）で表されることがある。分類フェーズ期間に、分類システムはイメージを含むＷｅｂページを入力し、そのイメージの特徴ベクトルを生成する。そのあと、分類システムはバイナリクラシファイアのウエイトを特徴ベクトルに適用して、そのイメージが広告イメージであるか、または非広告イメージであるかを示すスコア（得点）を生成する。バイナリクラシファイアは、広告イメージを特定し、そのイメージを破棄してからイメージがイメージのマッピングに追加されるようにイメージ検索エンジンサービスによって使用されることができる。また、バイナリクラシファイアは、広告イメージを特定し、その広告イメージをＷｅｂページから破棄してからそのＷｅｂページがモバイルデバイスに提供されるように、モバイルデバイスをサポートするサーバによって使用されることもできる。
【０００９】
いくつかの実施形態において、分類システムは、フィーチャ特定フェーズ期間にイメージを広告イメージまたは非広告イメージとして分類することに関連するフィーチャを特定する。そのあと、分類システムは、トレーニングフェーズ期間に関連フィーチャ（relevant feature）を使用することがある。関連フィーチャを特定するために、分類システムは候補フィーチャ（candidate feature）を選択し、その候補フィーチャから関連フィーチャが特定される。分類システムは、トレーニングフェーズの場合に上述したのと同じように、フィーチャ特定フェーズの場合も、特徴ベクトルとそのラベルを含むトレーニングデータを生成する。なお、１つの相違点は、フィーチャ特定フェーズで使用される特徴ベクトルはすべての候補ベクトルを含んでいるのに対し、トレーニングフェーズで使用される特徴ベクトルは関連があると判断された候補フィーチャだけを含んでいることである。例えば、候補フィーチャは、イメージのメタデータが単語「広告」を含んでいるかどうかを示すフィーチャおよびイメージのサイズを示す別のフィーチャを含んでいることがある。フィーチャ特定フェーズ期間に、分類システムは、メタデータに関係するフィーチャは関連性がないが、サイズに関係するフィーチャは関連性があると判断することがある。従って、関連フィーチャは候補フィーチャのサブセットになっている。分類システムがフィーチャ特定フェーズとトレーニングフェーズの両方で同じＷｅｂページを使用する場合は、分類システムは、フィーチャ特定フェーズ期間に生成された特徴ベクトルから関連フィーチャをコピーすることによって、トレーニングフェーズの場合の特徴ベクトルを生成することができる。
【００１０】
そのあと、分類システムは、イメージを広告イメージまたは非広告イメージとして分類するように、候補フィーチャの特徴ベクトルとラベルを使用してクラシファイアをトレーニングするためにアダプティブブースティング（adaptive boosting）手法を使用する。アダプティブブースティング手法では、各々の候補フィーチャについて弱いクラシファイア（weak classifier）が生成され、各々の弱いクラシファイアのウエイトが学習される。アダプティブブースティング手法では、トレーニングデータの誤った分類に基づいてウエイトが学習される。そのあと、分類システムは、イメージを広告イメージまたは非広告イメージとして分類することに関連しているとそのウエイトが示している弱いクラシファイアの候補フィーチャを関連フィーチャとして選択する。例えば、分類システムは、最も重く重み付けされた弱いクラシファイアの候補フィーチャを選択することがある。
【００１１】
いくつかの実施形態において、分類システムは、候補フィーチャをテキストフィーチャ、リンクフィーチャ、ビジュアルレイアウトフィーチャまたはコンテンツフィーチャとしてカテゴライズする。テキストフィーチャはＷｅｂページ（例えば、イメージのＵＲＬ、イメージのＡＬＴストリング、またはイメージの周囲のテキスト）から導き出された単語であり、そのＷｅｂページはその単語が広告であることを示していることがある。このような単語には、「ポップアップ」と「広告」が含まれていることがある。
【００１２】
リンクフィーチャ（link feature）は、イメージと関連付けられたリンクがポイントしているサイトから導き出されたものである。あるリンクフィーチャは、イメージを特定するハイパーリンクがＷｅｂページを提供した同じＷｅｂサイトをポイントしているか、別のロケーションをポイントしているかを示しており、その別のロケーションは広告サーバであることがある。別のロケーションをポイントしているこのようなハイパーリンクは広告サーバをポイントしていることがあるので、そのイメージが広告であることを示していることがある。別のリンクフィーチャは、イメージと関連付けられたハイパーリンクがＷｅｂページを提供した同じＷｅｂサイトをポイントしているか、別のロケーションをポイントしているかを示しており、その別のロケーションは、そこを通して広告アイテムの購入が可能であるＷｅｂページであることがある。別のロケーションをポイントするこのようなハイパーリンクは、広告主のＷｅｂページをポイントしていることがあるので、そのイメージが広告であることを示していることがある。
【００１３】
ビジュアルレイアウトフィーチャ（visual layout feature）は、イメージがそのＷｅｂページ内でどのようにビジュアル的にレイアウトされているかに関係している。ビジュアルレイアウトフィーチャとしては、イメージの左端座標、イメージの高さ、同じ左端座標をもつＷｅｂページのイメージの数などがある。種々のフィーチャはＷｅｂページの幅と高さに正規化することができる。例えば、Ｘ座標とＹ座標は０と１の範囲にすることができる。
【００１４】
コンテンツフィーチャ（content feature）は、イメージ自体のコンテンツに関係している。コンテンツフィーチャは、イメージのアスペクト比、イメージフォーマット、イメージがフォトグラフであるかグラフィックであるか、イメージのサイズ、イメージの異なるカラーの数、イメージのグレイエリアが占める割合（パーセンテージ）、およびイメージがハイコントラストであるかどうかの表示などを含む。アスペクト比フィーチャは、ショートでワイドなバナー広告を特定するときに利用すると便利なことがある。イメージフォーマットフィーチャは、複数のフレームをもつフォーマットになっている広告イメージを特定するときに利用すると便利なことがある。フォトグラフ／グラフィックフィーチャは、多くの広告イメージが広告の情報と一体になったグラフィックであるので利用すると便利なことがある。サイズフィーチャは、広告イメージが注目されるだけの十分な大きさにする必要があるので利用すると便利なことがある。カラーの数フィーチャは、広告イメージが非広告イメージよりも異種カラーの数が少ないのが一般であるので利用すると便利なことがある。グレイが占める割合（パーセンテージ）フィーチャは、広告イメージは変化する階調（shades of gray）が背景になっていることがよくあるので利用すると便利なことがある。コントラストフィーチャは、広告イメージがシャープなコントラストをもつように手作業で作成されるので利用すると便利なことがある。
【００１５】
以下の表は、一実施形態において関連があると特定された候補フィーチャをリストしたものである。ランクは、フィーチャ特定フェーズ期間にフィーチャに対して弱いクラシファイアに割り当てられたウエイトのランキングを示している。Ｃ１はテキストフィーチャを表し、Ｃ２はリンクフィーチャを表し、Ｃ３はビジュアルレイアウトフィーチャを表し、Ｃ４はコンテンツフィーチャを表している。
【００１６】
【表１】
0004783476.tif 000002
【００１７】
上述のように、アダプティブブースティング手法を使用すると、イメージを広告イメージまたは非広告イメージとして分類することに関連する候補フィーチャを特定することができる。アダプティブブースティングは、例を有するトレーニングデータのコレクションについて複数のテストを実行する繰り返し（iterative）プロセスである。アダプティブブースティングは弱い学習アルゴリズム（実行効率が見込みよりもわずかだけ良好であるアルゴリズム）を強い学習アルゴリズム（低エラー発生率で表示するアルゴリズム）に変換する。弱い学習アルゴリズムは、トレーニングデータの異なるサブセットで実行されることがある。このアルゴリズムは、以前のアルゴリズムが誤りを示す傾向にあった例にますます集中している。このアルゴリズムは以前の弱い学習アルゴリズムが行なっていたエラーを訂正している。このアルゴリズムがアダプティブであるのは、以前のアルゴリズムのエラー発生率に適応するからである。アダプティブブースティングは、おおざっぱでほどほどに不正確である経験則（rule of thumb）を結合してハイパフォーマンスのアルゴリズムを作成している。アダプティブブースティングは別々に実行した各テストの結果を結合して、単一で非常に正確なクラシファイアまたはランキング関数にしている。
【００１８】
上述のように、分類では、関連があると特定されたフィーチャを使用してバイナリクラシファイアをトレーニングするためにサポートベクターマシンが使用されることがある。サポートベクターマシンは動作すると、起り得る入力のスペースにハイパ面（hyper-surface）を見つける。ハイパ面では、正の例（例えば、広告イメージラベルの特徴ベクトル）と負の例（例えば、非広告ラベルをもつ特徴ベクトル）の最寄り（nearest）からハイパ面までの間の距離を最大限にすることによって正の例を負の例から分割することを試みている。このようにすると、トレーニングデータに類似しているが同一でないデータを正確に分類することが可能になる。サポートベクターマシンをトレーニングするには様々な手法が使用できる。ある手法では、大きな２次プログラミング（quadratic programming）問題を、解析的に解決できる一連の小さな２次プログラミング問題に細分化する順次最小最適化アルゴリズムを使用している。（順次最小最適化については、
（http://www.research.microsoft.com/~jplatt/smo.htmlを参照のこと）
【００１９】
図１は、一実施形態における分類システムのコンポーネントを示すブロック図である。分類システム１１０は、通信リンク１３０を介してＷｅｂサーバ１４０、検索エンジンクローラ（crawler）１５０、モバイルデバイスサーバ１６０、およびユーザコンピューティングデバイス１７０に接続されている。Ｗｅｂサーバは、検索エンジンクローラによってクローリングされ、ユーザコンピューティングデバイスによってアクセスされるＷｅｂページにサービスを提供している。モバイルデバイスサーバ１６０はモバイルデバイスへＷｅｂページのサービスを提供している。分類システム１１０は、トレーニングイメージストア１１１、トレーニングデータストア１１２、関連フィーチャストア１１３、および分類ウエイトストア１１４を備えている。トレーニングイメージストア１１１は、バイナリクラシファイアをトレーニングするために使用されるイメージを含むＷｅｂページを収めている。トレーニングデータストア１１２は、トレーニングイメージストア１１１のイメージに対する特徴ベクトルとラベルを収めている。特徴ベクトルはすべての候補フィーチャを含んでいることがある。関連フィーチャストア１１３は、フィーチャ特定フェーズ期間に関連があると判断された候補フィーチャの表示を収めている。分類ウエイトストア１１４は、トレーニングされたバイナリクラシファイアを表すウエイトを収めている。
【００２０】
分類システム１１０は、クラシファイア生成（generate classifier）コンポーネント１２１、特徴ベクトル生成（generate feature vector）コンポーネント１２２、イメージに対する特徴ベクトル生成（generate feature vectors for image）コンポーネント１２３、関連フィーチャ学習（learn relevant feature）コンポーネント１２４、および種々のフィーチャ生成コンポーネント１２５も備えている。クラシファイア生成コンポーネント１２１は、特徴ベクトル生成コンポーネント１２２を起動してトレーニングイメージストア１１１のイメージに対する特徴ベクトルを生成する。特徴ベクトル生成コンポーネント１２２は、イメージに対する特徴ベクトル生成コンポーネント１２３を起動してイメージに対する特徴ベクトルを生成する。イメージに対する特徴ベクトル生成コンポーネント１２３は、フィーチャ生成コンポーネント１２５を起動して特徴ベクトルのフィーチャを生成する。そのあと、クラシファイア生成コンポーネント１２１は、分類ウエイトを学習するようにバイナリクラシファイアをトレーニングする。クラシファイア生成コンポーネント１２１は、関連フィーチャ学習コンポーネント１２４を起動して、アダプティブブースティング手法を使用して候補フィーチャから関連フィーチャを特定することもある。
【００２１】
分類システム１１０は、Ｗｅｂページのイメージを広告イメージまたは非広告イメージであると分類するイメージ分類（classify image）コンポーネント１２６も備えている。イメージ分類コンポーネント１２６は、イメージに対する特徴ベクトル生成コンポーネント１２３を起動して、分類されるイメージに対する特徴ベクトルを生成する。そのあと、イメージ分類コンポーネント１２６は、分類ウエイトを特徴ベクトルに適用してイメージを分類する。
【００２２】
分類システム１１０が実現されているコンピューティングデバイスは、中央処理ユニット、メモリ、入力デバイス（例えば、キーボードおよびポインティングデバイス）、出力デバイス（例えば、ディスプレイデバイス）、およびストレージデバイス（例えば、ディスクドライブ）を装備することが可能である。メモリとストレージデバイスは、システムを実現するコンピュータ実行可能命令でコーディングが可能であるコンピュータ可読媒体である。つまり、命令を収めているコンピュータ可読媒体を意味している。さらに、命令、データ構造、およびメッセージ構造は、通信リンク上の信号といったデータ伝送媒体を介してストアまたは伝送されることもある。種々の通信リンクが使用可能であり、そのようなものとして、インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、ポイントツーポイントダイヤルアップコネクション、セルフォンネットワークなどがある。
【００２３】
分類システム１１０の実施形態は、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラマブルコンシューマエレクトロニクス、デジタルカメラ、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、セルフォン、パーソナルデジタルアシスタント、スマートフォン、上記に挙げたシステムまたはデバイスのいずれかを含む分散コンピューティング環境などを含んでいる種々の動作環境で実現されることも、その動作環境と関連して使用されることもある。
【００２４】
分類システム１１０は、プログラムモジュールのように、１または２以上のコンピュータまたは他のデバイスによって実行されるコンピュータ実行命令の一般的コンテキストの中で説明することができる。一般的に、プログラムモジュールの中には、特定のタスクを実行し、または特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれている。代表例として、プログラムモジュールの機能は、種々の実施形態で望まれるように組み合わされていることも、分散されていることもある。例えば、フィーチャ特定フェーズ、トレーニングフェーズおよび分類フェーズは異なるコンピュータシステム上で実行されることがある。バイナリクラシファイアは、広告イメージを特定することを必要とする種々の検索エンジンサービス、モバイルデバイスサーバ、またはその他のコンピューティングデバイスに分散されていることがある。
【００２５】
図２は、いくつかの実施形態においてビジュアルレイアウトフィーチャを生成する際に使用されるファクタを例示するブロック図である。Ｗｅｂページ２００はイメージ２０１を含んでいる。Ｗｅｂページ２００は、正規化されたＷｅｂページ幅２０２が１に、正規化されたＷｅｂページ高さ２０２が１になっている。Ｘ座標とＹ座標は０と１の間で変化している。イメージの位置２０４は、イメージの左上隅のＸ座標とＹ座標によって表されている。イメージ中心２０５は、イメージの中心点のＸ座標とＹ座標によって表されている。イメージ幅２０６とイメージ高さ２０７はＷｅｂページの幅と高さに正規化されている。
【００２６】
図３は、いくつかの実施形態における分類システムのクラシファイア生成コンポーネントの処理を示すフロー図である。クラシファイア生成コンポーネントは、オプションとして、フィーチャ特定フェーズ期間に候補フィーチャから関連フィーチャを学習してからトレーニングフェーズを実行することがある。トレーニングフェーズ期間に、コンポーネントは、関連フィーチャの特徴ベクトルとラベルを含むトレーニングデータを使用してバイナリクラシファイアをトレーニングする。ブロック３０１において、コンポーネントはトレーニングイメージストアのイメージに広告イメージであるか、非広告イメージであるかのラベルを付ける。ブロック３０２において、コンポーネントは候補フィーチャを渡して特徴ベクトル生成コンポーネントを起動してすべてのイメージに対する特徴ベクトルを生成する。ブロック３０３において、コンポーネントは関連フィーチャ学習コンポーネントを起動して、候補フィーチャのどれが関連フィーチャであるかを学習する。ブロック３０４において、コンポーネントは特徴ベクトル生成コンポーネントを起動して、イメージに対する関連フィーチャの特徴ベクトルを生成する。この分野の精通者ならば理解されるように、候補フィーチャを含む特徴ベクトルから関連フィーチャを抽出できるのは関連フィーチャが候補フィーチャのサブセットであるからである（ただし、候補特定フェーズ期間とトレーニングフェーズ期間に同じイメージが使用されることを想定する）。ブロック３０５において、コンポーネントは、サポートベクターマシンアルゴリズムまたはその他のなんらかのマシン学習アルゴリズムの使用によって、関連フィーチャの特徴ベクトルとラベルを使用してバイナリクラシファイアをトレーニングする。ブロック３０６において、コンポーネントは、フィーチャの学習したウエイトを分類ウエイトストアにストアし、そのあと完了する。
【００２７】
図４は、いくつかの実施形態における分類システムの特徴ベクトル生成コンポーネントの処理を示すフロー図である。コンポーネントにフィーチャ（例えば、候補フィーチャまたは関連フィーチャ）のリストが渡され、これらのフィーチャを含む各イメージに対する特徴ベクトルを生成する。ブロック４０１において、コンポーネントはトレーニングイメージストアの次のイメージを選択する。判定ブロック４０２において、すべてのイメージがすでに選択されていれば、コンポーネントはリターンし、そうでなければ、コンポーネントはブロック４０３から継続する。ブロック４０３において、コンポーネントは、選択したイメージとフィーチャを渡してイメージに対する特徴ベクトル生成コンポーネントを起動し、選択したイメージに対する特徴ベクトルを生成する。ブロック４０４において、コンポーネントはイメージに対する特徴ベクトルをトレーニングデータストアにストアし、そのあと、ブロック４０１にループして次のイメージを選択する。
【００２８】
図５は、いくつかの実施形態における分類システムのイメージに対する特徴ベクトル生成コンポーネントの処理を示すフロー図である。コンポーネントにはイメージおよびフィーチャのリストが渡される。コンポーネントは、渡されたフィーチャを含んでいるイメージに対する特徴ベクトルを生成する。ブロック５０１において、コンポーネントは渡された次のフィーチャを選択する。判定ブロック５０２において、すべてのフィーチャがすでに選択されていれば、コンポーネントは特徴ベクトルを返し、そうでなければ、コンポーネントはブロック５０３から継続する。ブロック５０３において、コンポーネントは、該当のフィーチャ生成コンポーネントを起動することによってイメージに対する選択したフィーチャを生成する。ブロック５０４において、コンポーネントは生成したフィーチャをイメージに対する特徴ベクトルに追加し、そのあと、ブロック５０１にループして次のフィーチャを選択する。
【００２９】
図６は、いくつかの実施形態における分類システムの関連フィーチャ学習コンポーネントの処理を示すフロー図である。コンポーネントは、トレーニングデータストアのトレーニングデータを使用して関連フィーチャを特定し、関連フィーチャであるとの表示を関連フィーチャストアにストアする。コンポーネントは、イメージを広告イメージまたは非広告イメージとして分類することに関連する候補フィーチャを特定する。ブロック６０１において、コンポーネントはイメージに同等ウエイトを割り当てる。アダプティブブースティングプロセス期間に、イメージのウエイトは、弱いクラシファイアのウエイトに基づいて誤分類されたイメージにトレーニングが集中するように調整される。ブロック６０２〜６０８において、コンポーネントはループして弱いクラシファイアのウエイトを判断し、誤分類されたイメージのウエイトを調整する。ブロック６０２において、コンポーネントは次の繰り返し（iteration）にインクリメントする。判定ブロック６０３において、すべての繰り返しが完了していれば、コンポーネントはブロック６０９から継続し、そうでなければコンポーネントはブロック６０４から継続する。ブロック６０４〜６０６において、コンポーネントはループして各々のフィーチャについて弱いクラシファイアをトレーニングする。ブロック６０４において、コンポーネントは次のフィーチャを選択する。判定ブロック６０５において、すべてのフィーチャがすでに選択されていれば、コンポーネントはブロック６０７から継続し、そうでなければ、コンポーネントはブロック６０６から継続する。ブロック６０６において、コンポーネントは選択したフィーチャについての弱いクラシファイアを、イメージのウエイトを使用してトレーニングする。そのあと、コンポーネントはブロック６０４にループして次のフィーチャを選択する。ブロック６０７において、コンポーネントは最良の弱いクラシファイア、すなわち、誤分類が最も少ない弱いクラシファイアを選択する。ブロック６０８において、コンポーネントは、選択した弱いクラシファイアの誤分類に基づいてイメージのウエイトを調整する。誤分類されたイメージのウエイトは、正しく分類されたイメージのウエイトに対して増加される。そのあと、コンポーネントはブロック６０２にループして次の繰り返しにインクリメントする。ブロック６０９において、コンポーネントは最良の弱いクラシファイアのフィーチャを選択し、そのあと、選択したフィーチャを関連フィーチャとしてリターンする。
【００３０】
図７は、いくつかの実施形態における分類システムのイメージ分類コンポーネントの処理を示すフロー図である。コンポーネントにはイメージを含んでいるＷｅｂページが渡され、そのイメージが広告イメージであるか、非広告イメージであるかの通知を返す。ブロック７０１において、コンポーネントはイメージに対する特徴ベクトル生成コンポーネントを起動してそのイメージに対する特徴ベクトルを生成する。ブロック７０２において、コンポーネントは、分類ウエイトストアのウエイトを特徴ベクトルのフィーチャに適用することによって分類のスコア（得点）を生成する。判定ブロック７０３において、そのイメージが広告であることをスコア（得点）が示していれば、コンポーネントは広告イメージであるとの通知を返し、そうでなければ、コンポーネントは非広告イメージであるとの通知を返却する。
【００３１】
図８は、いくつかの実施形態における分類システムのフィーチャ生成コンポーネントの処理を示すフロー図である。この例では、フィーチャ生成コンポーネントは、イメージと同じ左端Ｘ座標をもつ数のＷｅｂページのイメージを生成する。ブロック８０１において、コンポーネントはイメージの左端Ｘ座標をリトリーブする。ブロック８０２において、コンポーネントはカウントを初期化する。ブロック８０３〜８０７において、コンポーネントはループしてＷｅｂページの他のイメージの各々が同じ左端Ｘ座標をもっているかどうかを判断する。ブロック８０３において、コンポーネントはＷｅｂページの次の他のイメージを選択する。判定ブロック８０４において、他のイメージすべてがすでに選択されていれば、コンポーネントはカウントをリターンし、そうでなければ、コンポーネントはブロック８０５から継続する。ブロック８０５において、コンポーネントは選択した他のイメージの左端Ｘ座標をリトリーブする。判定ブロック８０６において、Ｘ座標が同じであれば、コンポーネントはブロック８０７から継続し、そうでなければ、コンポーネントはブロック８０３にループして次の他のイメージを選択する。ブロック８０７において、コンポーネントはカウントをインクリメントし、そのあと、ブロック８０３にループして次の他のメッセージを選択する。
【００３２】
構造上の特徴および／または方法上のアクトに特有の表現で主題を説明してきたが、当然に理解されるように、特許請求の範囲に明確されている主題は必ずしも上述した特定の特徴またはアクトに限定されない。むしろ、上述した特定の特徴およびアクトは、特許請求の範囲を実現する形態の例として開示されたものである。従って、本発明は特許請求の範囲による場合を除き限定されない。
【図１】
0004783476.tif 000003
【図２】
0004783476.tif 000004
【図３】
0004783476.tif 000005
【図４】
0004783476.tif 000006
【図５】
0004783476.tif 000007
【図６】
0004783476.tif 000008
【図７】
0004783476.tif 000009
【図８】
0004783476.tif 000010