(57)【特許請求の範囲】
【請求項１】
ユーザにコンテンツを提供する装置であって、
前記ユーザと前記コンテンツとの関係性を評価した実績値を要素とする観測行列を生成する観測行列生成部と、
前記実績値のそれぞれについて前記実績値の信頼度を算出する信頼度算出部と、
前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させる低ランク近似処理部と、
前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツ及び前記ユーザに対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出する評価値算出部と、
前記評価値に応じて、前記ユーザに提供する前記コンテンツである提供コンテンツを前記候補コンテンツの中から決定する提供コンテンツ決定部と、
を備えることを特徴とするコンテンツ提供装置。
【請求項２】
請求項１に記載のコンテンツ提供装置であって、
前記コンテンツはオンラインで提供される広告であり、
前記観測行列生成部は、前記ユーザによる前記広告のクリック率を前記実績値として算出し、
前記信頼度算出部は、前記広告のクリック数および前記広告の閲覧数の少なくともいずれかに応じて前記信頼度を算出すること、
を特徴とするコンテンツ提供装置。
【請求項３】
請求項２に記載のコンテンツ提供装置であって、
前記信頼度算出部は、前記広告を前記ユーザが閲覧した閲覧数と、前記広告を前記ユーザがクリックしたクリック数とを取得し、ベータ分布Ｂｅ（ｐ，ｑ）を事前分布として、前記クリック率のベイズ推定による事後分布Ｂｅ（ｐ＋クリック数，ｑ＋閲覧数＋クリック数）の分散を算出し、前記分散が小さいほど前記信頼度が高くなるように前記信頼度を決定すること、
を特徴とするコンテンツ提供装置。
【請求項４】
請求項１に記載のコンテンツ提供装置であって、
前記信頼度算出部は、前記実績値に応じて所定の確率分布における分散を算出し、算出した分散を底とするべき乗値の逆数を前記信頼度として算出すること、
を特徴とするコンテンツ提供装置。
【請求項５】
請求項４に記載のコンテンツ提供装置であって、
前記確率分布はベータ分布であり、
前記信頼度算出部は、所定の事前分布からベイズ推定を行った事後分布の分散を算出すること、
を特徴とするコンテンツ提供装置。
【請求項６】
ユーザにコンテンツを提供する装置であって、
前記ユーザを１つの以上の第１の分類に分類分けするユーザ分類部と、
前記コンテンツを１つ以上の第２の分類に分類分けするユーザ分類部と、
前記第１および第２の分類の間の関係性を評価した実績値を要素とする観測行列を生成する観測行列生成部と、
前記実績値のそれぞれについて前記実績値の信頼度を算出する信頼度算出部と、
前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させる低ランク近似処理部と、
前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツが属する前記第１の分類および前記ユーザが属する前記第２の分類に対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出する評価値算出部と、
前記ユーザに提供する前記コンテンツである提供コンテンツを前記評価値に応じて前記候補コンテンツの中から決定する提供コンテンツ決定部と、
を備えることを特徴とするコンテンツ提供装置。
【請求項７】
請求項６に記載のコンテンツ提供装置であって、
前記信頼度算出部は、前記実績値に応じて所定の確率分布における分散を算出し、算出した分散を底とするべき乗値の逆数を前記信頼度として算出すること、
を特徴とするコンテンツ提供装置。
【請求項８】
コンテンツを当該コンテンツに関係するユーザに提供するための、前記コンテンツと前記ユーザとの関係性を評価した評価値を要素とする関係行列に、低ランク近似により近似させた複数の行列を生成する装置であって、
前記関係性を評価した実績値を要素とする観測行列を生成する観測行列生成部と、
前記実績値のそれぞれについて前記実績値の信頼度を算出する信頼度算出部と、
前記実績値に対して前記信頼度に応じた重み付けをしたうえで、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させる低ランク近似処理部と、
を備えることを特徴とする低ランク近似行列生成装置。
【請求項９】
請求項８に記載の低ランク近似行列生成装置であって、
前記信頼度算出部は、前記実績値に応じて所定の確率分布における分散を算出し、算出した分散を底とするべき乗値の逆数を前記信頼度として算出すること、
を特徴とする低ランク近似行列生成装置。
【請求項１０】
ユーザにコンテンツを提供する方法であって、
コンピュータが、
前記ユーザと前記コンテンツとの関係性を評価した実績値を要素とする観測行列を生成するステップと、
前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、
前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、
前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツ及び前記ユーザに対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出するステップと、
前記評価値に応じて、前記ユーザに提供する前記コンテンツである提供コンテンツを前記候補コンテンツの中から決定するステップと、
を実行することを特徴とするコンテンツ提供方法。
【請求項１１】
コンテンツを当該コンテンツに関係するユーザに提供するための、前記コンテンツと前記ユーザとの関係性を評価した評価値を要素とする関係行列に、低ランク近似により近似させた複数の行列を生成する方法であって、
コンピュータが、
前記関係性を評価した実績値を要素とする観測行列を生成するステップと、
前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、
前記実績値に対して前記信頼度に応じた重み付けをしたうえで、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、
を実行することを特徴とする低ランク近似行列生成方法。
【請求項１２】
ユーザにコンテンツを提供するためのプログラムであって、
コンピュータに、
前記ユーザと前記コンテンツとの関係性を評価した実績値を要素とする観測行列を生成するステップと、
前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、
前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、
前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツ及び前記ユーザに対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出するステップと、
前記評価値に応じて、前記ユーザに提供する前記コンテンツである提供コンテンツを前記候補コンテンツの中から決定するステップと、
を実行させるためのプログラム。
【請求項１３】
コンテンツを当該コンテンツに関係性するユーザに提供するための、前記コンテンツと前記ユーザとの関係性を評価した評価値を要素とする関係行列に、低ランク近似により近似させた複数の行列を生成するためのプログラムであって、
コンピュータに、
前記関係性を評価した実績値を要素とする観測行列を生成するステップと、
前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、
前記実績値に対して前記信頼度に応じた重み付けをしたうえで、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ提供装置、低ランク近似行列生成装置、コンテンツ提供方法、低ランク近似行列生成方法およびプログラムに関する。
【背景技術】
【０００２】
オンラインショッピングにおける商品のレコメンド処理において協調フィルタリングを行う場合などにはユーザや商品の間の関係性を行列で管理することが行われている。さらにこの関係性の行列を複数の低ランクの行列に分解する近似処理が行われている。例えば特許文献１では無限次元の行列因子分解を行うことにより大規模な関係性を処理することができるシステムが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−４８２８６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
オンラインでの広告の配信に係るクリック率を広告の関係性として管理しようとする場合、広告のクリック率は低い（１％未満であることも多い）ことが知られている。したがって、１回のクリックがクリック率に与える影響が非常に大きく、特に広告の配信数が少ない場合には、クリック率自体の信頼度が低いことが生じうる。しかしながら、従来の低ランク近似では観測値自体は絶対的に正しいものとして近似処理を行っていたため、配信数が少ない広告のクリック率を観測して低ランク近似を行っても正確な関係性を予測することができないことがあった。
本発明は、このような背景を鑑みてなされたものであり、正確な関係性の予測を行うことのできるようにすることを目的とする。
【課題を解決するための手段】
【０００５】
上記課題を解決するための本発明の主たる発明は、ユーザにコンテンツを提供する装置であって、前記ユーザと前記コンテンツとの関係性を評価した実績値を要素とする観測行列を生成する観測行列生成部と、前記実績値のそれぞれについて前記実績値の信頼度を算出する信頼度算出部と、前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させる低ランク近似処理部と、前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツ及び前記ユーザに対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出する評価値算出部と、前記評価値に応じて、前記ユーザに提供する前記コンテンツである提供コンテンツを前記候補コンテンツの中から決定する提供コンテンツ決定部と、を備えることとする。
【０００６】
また、本発明のコンテンツ提供装置では、前記コンテンツはオンラインで提供される広告であり、前記観測行列生成部は、前記ユーザによる前記広告のクリック率を前記実績値として算出し、前記信頼度算出部は、前記広告のクリック数および前記広告の閲覧数の少なくともいずれかに応じて前記信頼度を算出するようにしてもよい。
【０００７】
また、本発明のコンテンツ提供装置では、前記信頼度算出部は、前記広告を前記ユーザが閲覧した閲覧数と、前記広告を前記ユーザがクリックしたクリック数とを取得し、ベータ分布Ｂｅ（ｐ，ｑ）を事前分布として、前記クリック率のベイズ推定による事後分布Ｂｅ（ｐ＋クリック数，ｑ＋閲覧数＋クリック数）の分散を算出し、前記分散が小さいほど前記信頼度が高くなるように前記信頼度を決定するようにしてもよい。
【０００８】
また、本発明のコンテンツ提供装置では、前記信頼度算出部は、前記実績値に応じて所定の確率分布における分散を算出し、算出した分散を底とするべき乗値の逆数を前記信頼度として算出するようにしてもよい。
【０００９】
また、本発明のコンテンツ提供装置では、前記確率分布はベータ分布であり、前記信頼度算出部は、所定の事前分布からベイズ推定を行った事後分布の分散を算出するようにしてもよい。
【００１０】
また、本発明の他の態様は、ユーザにコンテンツを提供する装置であって、前記ユーザを１つの以上の第１の分類に分類分けするユーザ分類部と、前記コンテンツを１つ以上の第２の分類に分類分けするユーザ分類部と、前記第１および第２の分類の間の関係性を評価した実績値を要素とする観測行列を生成する観測行列生成部と、前記実績値のそれぞれについて前記実績値の信頼度を算出する信頼度算出部と、前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させる低ランク近似処理部と、前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツが属する前記第１の分類および前記ユーザが属する前記第２の分類に対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出する評価値算出部と、前記ユーザに提供する前記コンテンツである提供コンテンツを前記評価値に応じて前記候補コンテンツの中から決定する提供コンテンツ決定部と、を備えることとする。
【００１１】
また、本発明のコンテンツ提供装置では、前記信頼度算出部は、前記実績値に応じて所定の確率分布における分散を算出し、算出した分散を底とするべき乗値の逆数を前記信頼度として算出するようにしてもよい。
【００１２】
また、本発明の他の態様は、コンテンツを当該コンテンツに関係するユーザに提供するための、前記コンテンツと前記ユーザとの関係性を評価した評価値を要素とする関係行列に、低ランク近似により近似させた複数の行列を生成する装置であって、前記関係性を評価した実績値を要素とする観測行列を生成する観測行列生成部と、前記実績値のそれぞれについて前記実績値の信頼度を算出する信頼度算出部と、前記実績値に対して前記信頼度に応じた重み付けをしたうえで、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させる低ランク近似処理部と、を備えることとする。
【００１３】
また、本発明の低ランク近似行列生成装置では、前記信頼度算出部は、前記実績値に応じて所定の確率分布における分散を算出し、算出した分散を底とするべき乗値の逆数を前記信頼度として算出するようにしてもよい。
【００１４】
また、本発明の他の態様は、ユーザにコンテンツを提供する方法であって、コンピュータが、前記ユーザと前記コンテンツとの関係性を評価した実績値を要素とする観測行列を生成するステップと、前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツ及び前記ユーザに対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出するステップと、前記評価値に応じて、前記ユーザに提供する前記コンテンツである提供コンテンツを前記候補コンテンツの中から決定するステップと、を実行することとする。
【００１５】
また、本発明の他の態様は、コンテンツを当該コンテンツに関係するユーザに提供するための、前記コンテンツと前記ユーザとの関係性を評価した評価値を要素とする関係行列に、低ランク近似により近似させた複数の行列を生成する方法であって、コンピュータが、前記関係性を評価した実績値を要素とする観測行列を生成するステップと、前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、前記実績値に対して前記信頼度に応じた重み付けをしたうえで、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、を実行することとする。
【００１６】
また、本発明の他の態様は、ユーザにコンテンツを提供するためのプログラムであって、コンピュータに、前記ユーザと前記コンテンツとの関係性を評価した実績値を要素とする観測行列を生成するステップと、前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、前記実績値に対して前記信頼度に応じた重み付けをして、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、
前記ユーザに提供可能な前記コンテンツである候補コンテンツのそれぞれについて、当該候補コンテンツ及び前記ユーザに対応する前記複数の行列の要素に基づいて前記候補コンテンツの評価値を算出するステップと、前記評価値に応じて、前記ユーザに提供する前記コンテンツである提供コンテンツを前記候補コンテンツの中から決定するステップと、を実行させることとする。
【００１７】
また、本発明の他の態様は、コンテンツを当該コンテンツに関係性するユーザに提供するための、前記コンテンツと前記ユーザとの関係性を評価した評価値を要素とする関係行列に、低ランク近似により近似させた複数の行列を生成するためのプログラムであって、コンピュータに、前記関係性を評価した実績値を要素とする観測行列を生成するステップと、前記実績値のそれぞれについて前記実績値の信頼度を算出するステップと、前記実績値に対して前記信頼度に応じた重み付けをしたうえで、前記観測行列よりも低ランクの複数の行列の積を前記観測行列に近似させるステップと、を実行させることとする。
【００１８】
その他本願が開示する課題やその解決方法については、発明の実施形態の欄及び図面により明らかにされる。
【発明の効果】
【００１９】
本発明によれば、正確な関係性の予測を行うことができる。
【図面の簡単な説明】
【００２０】
【図１】ユーザベクトル、性向行列、広告ベクトルから期待クリック性向を算出することを説明する図である。
【図２】本実施形態の広告配信システムの全体構成を示す図である。
【図３】Ｗｅｂサーバ２０のハードウェア構成例を示す図である。
【図４】Ｗｅｂサーバ２０のソフトウェア構成例を示す図である。
【図５】広告データベース２５２に記憶される広告情報の構成例を示す図である。
【図６】ユーザデータベース２５３に記憶されるユーザ情報の構成例を示す図である。
【図７】近似行列記憶部２５４の構成例を示す図である。
【図８】インプレッションログ記憶部２５５に記憶されるインプレッションログの構成例を示す図である。
【図９】クリックログ記憶部２５６に記憶されるクリックログの構成例を示す図である。
【図１０】解析処理部２１５による解析処理の流れを示す図である。
【図１１】観測行列の作成処理の一例を示す図である。
【図１２】Ｗｅｂサーバ２０により行われる処理の流れを示す図である。
【図１３】広告の選択処理の流れを示す図である。
【発明を実施するための形態】
【００２１】
＝＝（１）発明の概要＝＝
以下、本発明の一実施形態に係る広告配信システムについて説明する。本実施形態において広告とは、Ｗｅｂページにおいてコンテンツの内容等に応じて表示される広告（リスティング広告と呼ばれる。）を想定する。
【００２２】
本実施形態では、ユーザおよび広告に対してそれぞれクラスタリング処理を行い、ユーザに関するクラスタ（以下、ユーザクラスタという。）と広告に関するクラスタ（以下、広告クラスタという。）とを求め、ユーザクラスタと広告クラスタとの間でのクリック性向を示す行列（以下、性向行列という。）を作成する。ユーザは複数のユーザクラスタに属することができ、広告も複数の広告クラスタに属することができるものとする。また、ユーザは各ユーザクラスタに属する度合い（帰属度）が算出され、広告も各広告クラスタに対する帰属度が算出されるものとする。以下の説明において、ユーザの各ユーザクラスタに対する帰属度を要素とするベクトルをユーザベクトルといい、広告の各広告クラスタに対する帰属度を要素とするベクトルを広告ベクトルという。なお、クラスタリング処理には複数のクラスタへの帰属度を算出することのできる一般的な手法を用いるものとして本明細書では説明を省略する。
【００２３】
ユーザクラスタの数をＮ、広告クラスタの数をＭとすると、性向行列はＮ×Ｍの行列になる。性向行列は、ユーザクラスタと広告クラスタの各ペアについて、当該ユーザクラスタに帰属するユーザに対して当該広告クラスタに帰属する広告が表示された回数（インプレッション数と呼ばれる。）と、当該ユーザクラスタに属するユーザが当該広告クラスタに属する広告をクリックしたクリック数とをログから取得して、クリック率をインプレッション数で割った実クリック率（以下、実ＣＴＲと表記する。）を求めるものとする。なお、あるユーザがあるユーザクラスタに帰属するとは、当該ユーザの当該ユーザクラスタに対する帰属度が所定値（例えば０）より大きいことを意味し、同様にある広告がある広告クラスタに帰属するとは、当該広告の当該広告クラスタに対する帰属度が所定値（例えば０）より大きいことを意味するものとする。
【００２４】
図１に示すように、あるユーザについてのユーザベクトル１（の転置ベクトル）と、性向ベクトル２と、ある広告についての広告ベクトル３とを乗算することにより、当該ユーザによる当該広告のクリック性向（期待クリック性向）が算出される。本実施形態では、この期待ＣＴＲを広告の評価値として、表示する広告を決定する。
本実施形態では、性向行列を複数の行列の積として分解する。行列の分解は例えば特異値分解（Singular Value Decomposition；ＳＶＤ）や行列因子分解（Matrix Factorization）などが知られている。ユーザクラスタおよび広告クラスタは数百〜数千作られることが考えられるため、性向行列を複数の（性向行列よりも低ランクの）行列の積として表現することにより、性向行列を管理する情報量を圧縮することができる。また、ノイズが除去されるいわゆるスムージング効果も期待できる。
【００２５】
＝＝（２）行列因子分解（Matrix Factorization）＝＝
本実施形態では、行列因子分解により性向行列を２つの行列に分解するものとする。行列因子分解では、ユーザクラスタと広告クラスタとに対応する広告の実ＣＴＲを観察値とした観察行列を作成し、観察値と２つの行列の積における対応する要素との差の合計が最小になるように２つの行列を決定する。例えばクラスタリングにより数百、数千のクラスタが作成されたときなどには、あるユーザクラスタのユーザにある広告クラスタの広告が配信されていないという状態、すなわち欠損値が存在する状態が発生し得るが、行列因子分解による低ランク近似を行うことにより欠損値を補完することもできる。
【００２６】
本実施形態では、観察行列における欠損値（すなわちインプレッション数が０である場合）以外の観測値のそれぞれについて、２つの行列ＵおよびＡの積の対応する要素との差を最小化するように最適化計算を行う。なお、行列Ｕはユーザの属性を表す行列、行列Ａは広告の属性を表す行列となる。ここで２つの低ランク行列ＵおよびＡの積ＵＡの要素である予測クリック率（以下、予測ＣＴＲと表記する。）の予測モデルは、予測ＣＴＲをｒ’、予測クリック率の平均をμ、ユーザクラスタの影響（例えば、気軽に広告をクリックしがちなユーザクラスタである場合など）による平均クリック率からの偏差をｂｕｓｅｒ、広告クラスタの影響（例えば、大ヒット商品の広告クラスタである場合など）による平均クリック率からの偏差をｂａｄとして、次式とする。
0005507607.tif 000002
【００２７】
一般的な行列因子分解の手法において、行列ＵおよびＡを決定するための最適計算は、観測値（本実施形態の場合は、実クリック率である。以下、実ＣＴＲと表記する。）をｒ、予測ＣＴＲをｒ’として次式のような目的関数の最小化を行うことになる。
0005507607.tif 000003
【００２８】
ここで、式Ｅ２の目的関数において、実ＣＴＲと予測ＣＴＲとの差を底とし２を指数としたべき乗の項を損失関数といい、ｂｕｓｅｒ、ｂａｄ、Ｕ、Ａを含む第２項を正則化項という。また、行列因子分解は観測行列から性向行列に近似した行列を学習することができることから上記の目的関数を学習モデルとも称する。なお、正則化項においてどのような説明変数を用いるかについては一般的な行列因子分解の手法によるものとし本明細書では説明を省略する。
【００２９】
上記のように一般的な行列因子分解の手法では、観測値（実ＣＴＲ）の信頼度は考慮されていない。しかしながら、特に広告のクリック率のように通常非常に小さい値（広告のクリック率は一般に１％未満であることが多いことが知られている。）の場合には、クリックが発生せずに実ＣＴＲが０のままの状態が続いたり、インプレッション数が少ない間にたまたまクリックが発生したときには期待されるクリック率よりも非常に大きな値となってしまったりすることが考えられ、特にインプレッション数が少ない場合には実ＣＴＲの信頼度は低い。そこで本実施形態では、行列因子分解の最小化計算における目的関数に含まれる損失関数において信頼度を評価する。すなわち、実ＣＴＲと予測ＣＴＲとの差（上記Ｅ２式では差の二乗）に信頼度を乗じた値を最小化するようにする。
【００３０】
本実施形態では、実ＣＴＲがベータ分布に従うものとして、ベータ分布の分散の逆数を信頼度として用いるものとする。ここで、事前分布をＢｅ（ｐ，ｑ）とし、クリック数がｃｕａ、インプレッション数がｉｕａであった場合、ベイズ推定による事後分布はＢｅ（ｐ＋ｃｕａ，ｑ＋ｉｕａ−ｃｕａ）となり、この事後分布の分散ｖｕａは次式で表される。
0005507607.tif 000004
この分散ｖｕａを底としたべき乗値（指数ｓは１であってもよい。）の１／ｖｕａｓを信頼度として用いることにより、実ＣＴＲのばらつきが少ないほど信頼度が高くなることになる。なお、指数ｓには任意の値を設定することができる。また、事前分布Ｂｅ（ｐ，ｑ）のパラメータｐ，ｑには任意の値を設定することが可能であり、例えば解析者が過去の実ＣＴＲの分布を解析して決定することができる。また、事前分布は一様分布であるものとして、Ｂｅ（１，１）を事前分布として採用するようにしてもよい。
【００３１】
以上より、本実施形態では次式を学習モデルとして最小化することになる。
0005507607.tif 000005
【００３２】
このようにベイズ推定の事後分布の分散の逆数（のべき乗）を信頼度とすることにより、インプレッション数が増えて実ＣＴＲのばらつきが小さくなるほど予測ＣＴＲと実ＣＴＲとの差を大きく評価し、インプレッション数が少なく実ＣＴＲのばらつきが大きい間の予測ＣＴＲと実ＣＴＲとの差は小さく評価した上で低ランク近似を行うことができる。
【００３３】
＝＝（３）システム構成＝＝
図２は本実施形態の広告配信システムの全体構成を示す図である。本実施形態の広告配信システムは、ユーザ端末１０と通信ネットワーク３０を介して通信可能に接続されるＷｅｂサーバ２０を含んで構成される。
通信ネットワーク３０は、例えば公衆電話回線網や専用通信回線網、携帯電話回線網、無線通信網、イーサネット（登録商標）などにより構築される、インターネットやＬＡＮ（Local Area Network）である。
【００３４】
Ｗｅｂサーバ２０は、画像や動画、テキストなどの各種のコンテンツをＨＴＴＰ（HyperText Transfer Protocol）に従って提供する、例えばワークステーションやパーソナルコンピュータなどのコンピュータである。ユーザ端末１０は、Ｗｅｂサーバ２０が提供する各種のＷｅｂページを閲覧するブラウザを動作させる、例えばパーソナルコンピュータやタブレットコンピュータ、携帯電話端末、ＰＤＡ（Personal Digital Assistant）などのコンピュータである。
【００３５】
＝＝（４）Ｗｅｂサーバ２０のハードウェア構成＝＝
図３はＷｅｂサーバ２０のハードウェア構成例を示す図である。Ｗｅｂサーバ２０は、ＣＰＵ２０１、メモリ２０２、記憶装置２０３、通信インタフェース２０４、入力装置２０５、出力装置２０６を備える。記憶装置２０３は、各種のデータやプログラムを記憶する、例えばハードディスクドライブやソリッドステートドライブ、フラッシュメモリなどである。通信インタフェース２０４は、通信ネットワーク３０に接続するためのインタフェースであり、例えばイーサネット（登録商標）に接続するためのアダプタ、公衆電話回線網に接続するためのモデム、無線通信を行うための無線通信機、シリアル通信のためのＵＳＢ（Universal Serial Bus）コネクタやＲＳ２３２Ｃコネクタなどである。入力装置２０５は、データを入力する、例えばキーボードやマウス、タッチパネル、ボタン、マイクロフォンなどである。出力装置２０６は、データを出力する、例えばディスプレイやプリンタ、スピーカなどである。
【００３６】
＝＝（５）Ｗｅｂサーバ２０のソフトウェア構成＝＝
図４はＷｅｂサーバ２０のソフトウェア構成例を示す図である。Ｗｅｂサーバ２０は、ＨＴＴＰ処理部２１１、Ｗｅｂページ作成部２１２、広告選択部２１３、ログ収集部２１４および解析処理部２１５の機能部と、Ｗｅｂ情報データベース２５１、広告データベース２５２、ユーザデータベース２５３、近似行列記憶部２５４、インプレッションログ記憶部２５５およびクリックログ記憶部２５６の記憶部とを備えている。
【００３７】
なお、上記各機能部は、Ｗｅｂサーバ２０が備えるＣＰＵ２０１が記憶装置２０２に記憶されているプログラムを実行することにより実現され、上記各記憶部は、Ｗｅｂサーバ２０が備えるメモリ２０２及び記憶装置２０３が提供する記憶領域の一部として実現される。
【００３８】
＝＝（６）記憶部の説明＝＝
（６−１）Ｗｅｂ情報データベース２５１
Ｗｅｂ情報データベース２５１は、Ｗｅｂページを作成するための情報（以下、Ｗｅｂ情報という。）を記憶する。Ｗｅｂ情報は、例えば、ＨＴＭＬで記述されたファイルや、ＣＧＩ（Common Gateway Interface）などの仕組みにより実行されるプログラムを格納したプログラムファイル、画像ファイルなどである。Ｗｅｂ情報データベース２５１は、例えば、Ｗｅｂサーバ２０で動作するオペレーティングシステムが提供するファイルシステムのディレクトリやフォルダにより実現することができる。
【００３９】
（６−２）広告データベース２５２
広告データベース２５２は、広告を表示するための情報（以下、広告情報という。）を記憶する。図５は、広告データベース２５２に記憶される広告情報の構成例を示す図である。広告情報には、広告の識別情報である広告ＩＤに対応付けて、広告のカテゴリ、広告に関するＵＲＬ（Uniform Resource Locator）、広告のタイトル、入札額、実ＣＴＲおよび当該広告の各広告クラスタへの帰属度が含まれる。広告情報のＵＲＬが示すＷｅｂページはランディングページとも呼ばれ、広告がクリックされるとランディングページにリダイレクトされることになる。
【００４０】
入札額は、広告がクリックされた場合に広告主から支払われる最大の単価であり、広告主により決定される。
本実施形態ではタイトルの文字列をＷｅｂページの広告として表示するものとする。広告には広告ＩＤを指定した所定のＵＲＬ（ホスト名にＷｅｂサーバ２０が指定されるものとする。以下、リダイレクトＵＲＬという。）へのリンクが設定される。Ｗｅｂページにおいて広告がクリックされると、広告ＩＤを含むリクエストがＷｅｂサーバ２０に送信され、後述するログ収集部２１４によりクリックされたことのログが収集され、ＨＴＴＰ処理部２１１により広告ＩＤに対応する広告情報のＵＲＬにリダイレクトされる（例えば、当該ＵＲＬをリダイレクト先として指定した応答が送信される。）。これにより、広告に応じたユーザの行動（クリック）を検知することができる。
【００４１】
なお、広告として画像や動画などを表示し、あるいは音声を出力させるようにしてもよく、その場合には、例えば広告情報には、広告として表示する画像や動画のデータを示すＵＲＬを追加するようにすることができる。
【００４２】
（６−３）ユーザデータベース２５３
ユーザデータベース２５３は、ユーザに関する情報（以下、ユーザ情報という。）を記憶する。図６はユーザデータベース２５３に記憶されるユーザ情報の構成例を示す図である。ユーザ情報には、ユーザの識別情報であるユーザＩＤに対応付けて、ユーザの性別やユーザが現在する都道府県、ユーザの趣味などのユーザの属性と、当該ユーザの各ユーザクラスタへの帰属度とが含まれる。なお、性別、都道府県、趣味以外にも各種のユーザについての属性をユーザ情報に含めることができる。
【００４３】
（６−４）近似行列記憶部２５４
図７は、近似行列記憶部２５４の構成例を示す図である。近似行列記憶部２５４は、観測行列の低ランク近似させた複数の行列（本実施形態では行列Ｕおよび行列Ａ）を記憶する。行列ＡおよびＵは、たとえば表形式で保存するようにしてもよいし、数式として記憶するようにしてもよい。図７に示すように、行列Ｕの行数はユーザクラスタの数Ｎであり、行列Ａの列数は広告クラスタの数Ｍである。行列Ｕの列数および行列Ａの行数はともにｋであり、低ランク近似により設定される数である。行列Ｕと行列Ａとを乗算することにより性向行列（の近似行列）を復元することができる。なお、ｋは解析者が任意の値に設定できるものとしてもよい。
【００４４】
（６−５）インプレッションログ記憶部２５５
インプレッションログ記憶部２５５は、Ｗｅｂページに広告が表示されたこと（インプレッションと呼ばれる。）を示す情報（以下、インプレッションログという。）を記憶する。図８は、インプレッションログ記憶部２５５に記憶されるインプレッションログの構成例を示す図である。インプレッションログには、Ｗｅｂページに広告が表示された日時（すなわち、ＷｅｂページがＷｅｂサーバ２０から送信された日時である。以下、配信日時という。）、Ｗｅｂページを示すＵＲＬ、表示された広告を示す広告ＩＤ、Ｗｅｂページを閲覧したユーザを示すユーザＩＤが含まれる。インプレッションログは１つの広告が表示されるにつき１つ登録される。すなわち、たとえば１つのＷｅｂページに３つの広告が表示された場合には、３つのインプレッションログが登録されることになる。
【００４５】
（６−６）クリックログ記憶部２５６
クリックログ記憶部２５６は、Ｗｅｂページに表示された広告がクリックされたことを示す情報（以下、クリックログという。）を記憶する。図９は、クリックログ記憶部２５６に記憶されるクリックログの構成例を示す図である。クリックログには、クリックされた広告を示す広告ＩＤ、広告をクリックしたユーザを示すユーザＩＤ、広告が表示されたＷｅｂページを示すＵＲＬ、および広告がクリックされた日時（クリック日時）が含まれる。
【００４６】
＝＝（７）機能部の説明＝＝
（７−１）ＨＴＴＰ処理部２１１
ＨＴＴＰ処理部２１１は、ＨＴＴＰの処理を行う。ＨＴＴＰ処理部２１１は、ユーザ端末１０から送信されるＨＴＴＰのリクエストを受信する。  
リクエストにリダイレクトＵＲＬが指定されていた場合、ＨＴＴＰ処理部２１１は、ログ収集部２１４を呼び出してクリックログを登録させた上で、リクエストに含まれている広告ＩＤに対応する広告情報を広告データベース２５２から読み出し、読み出した広告情報に含まれているＵＲＬをリダイレクト先として指定した応答をユーザ端末１０に応答する。
【００４７】
リクエストにリダイレクトＵＲＬ以外の、Ｗｅｂページを示すＵＲＬが指定された場合には、ＨＴＴＰ処理部２１１は、Ｗｅｂページ作成部２１２を呼び出してＷｅｂページを表示するための情報（以下、画面情報という。画面情報は例えばＨＴＭＬファイルである。）を作成させ、Ｗｅｂページ作成部２１２が作成した画像情報をユーザ端末１０に応答し、ログ収集部２１４を呼び出してインプレッションログを登録させる。
【００４８】
（７−２）Ｗｅｂページ作成部２１２
Ｗｅｂページ作成部２１２は、Ｗｅｂページを表示するための画面情報を作成する。Ｗｅｂページ作成部２１２は、広告選択部２１３を呼び出してＷｅｂページに表示させる広告を選択させ、選択された広告がＷｅｂページに表示され、広告がクリックされた場合にはリダイレクトＵＲＬにアクセスするように、例えばリンクタグを設定した文字列を画面情報に挿入する。なお、Ｗｅｂページ作成部２１２が、広告以外の各種のコンテンツを作成する処理については、一般的なＷｅｂサーバによる処理を用いるものとして、ここでは説明を省略する。
【００４９】
（７−３）広告選択部２１３
広告選択部２１３は、Ｗｅｂページに表示する広告を選択する。
広告選択部２１３は、配信候補抽出部２２１、評価値算出部２２２、広告決定部２２３を備えている。なお、配信候補抽出部２２１、評価値算出部２２２、広告決定部２２３も、ＣＰＵ２０１が記憶装置２０３に記憶されているプログラムをメモリ２０２に読み出して実行することにより実現される。
【００５０】
（７−３−１）配信候補抽出部２２１
配信候補抽出部２２１は、広告の候補を決定する。配信候補抽出部２２１は、広告データベース２５２から所定数（例えば１０個や５０個、１００個など、任意の数を指定することができる。）の広告情報を読み出す。本実施形態では、配信候補抽出部２２１は、ランダムに所定数の広告情報を読み出すものとするが、例えば、コンテンツの内容やユーザの属性に応じて広告情報を読み出すようにしてもよい。なお、配信候補抽出部２２１が、数ある広告の中から所定数の広告を選択する処理については、一般的な広告の選択処理を用いることもできる。
【００５１】
（７−３−２）評価値算出部２２２
評価値算出部２２２は、広告の評価値を算出する。上述したように、期待クリック性向が評価値として用いられる。期待クリック性向は、ユーザが帰属するユーザクラスタおよび広告が帰属する広告クラスタに対応する行列Ｕ、Ａの要素に基づいて算出される。本実施形態では、ユーザベクトル（の転置ベクトル）、行列Ｕ、行列Ａおよび広告ベクトルを乗算して算出されるスカラ値を期待クリック性向とするが、ユーザが帰属するユーザクラスタと広告が帰属する広告クラスタとに対応する行列Ｕ，Ａの要素（または行列Ｕ，Ａを乗じて求められる性向行列の要素）に基づいて、合計、平均等任意の演算を行うことにより算出される値を期待クリック性向とすることができる。
【００５２】
（７−３−３）広告決定部２２３
広告決定部２２３は、配信候補抽出部２２１が決定した候補の中から表示する広告を決定する。広告決定部２２３は、評価値算出部２２２が算出したｘＣＴＲの大きい順に所定数（図１の例では３）の広告を、表示する広告として決定する。
【００５３】
（７−４）ログ収集部２１４
ログ収集部２１４は、インプレッションログ及びクリックログを登録する。ログ収集部２１４は、ＨＴＴＰにリダイレクトＵＲＬが指定されていた場合には、リダイレクトＵＲＬに指定されている広告ＩＤに対応するカテゴリを広告データベース２５２から読み出し、当該広告ＩＤ、読み出したカテゴリ、及び現在の日時を設定したクリックログを作成してクリックログ記憶部２５６に登録する。ＨＴＴＰにリダイレクトＵＲＬ以外のＵＲＬが指定されていた場合には、ログ収集部２１４は、広告選択部２１３が選択した広告のそれぞれについて、現在日時、広告を示す広告ＩＤ、及び当該広告のカテゴリを含むインプレッションログを作成してインプレッションログ記憶部２５５に登録する。
【００５４】
（７−５）解析処理部２１５
解析処理部２１５は、低ランク近似により行列Ｕおよび行列Ａを求める。解析処理部２１５は、クラスタリング処理部２３１、観測行列生成部２３２、信頼度算出部２３３、および低ランク近似処理部２３４を備える。なお、クラスタリング処理部２３１、観測行列生成部２３２、信頼度算出部２３３、および低ランク近似処理部２３４も、ＣＰＵ２０１が記憶装置２０３に記憶されているプログラムをメモリ２０２に読み出して実行することにより実現される。
【００５５】
（７−５−１）クラスタリング処理部２３１
クラスタリング処理部２３１はデータクラスタリングを行い、ユーザをユーザクラスタに分類し、広告を広告クラスタに分類する。なお、クラスタリング処理部２３１が行うデータクラスタリングの処理は一般的なものを採用するものとするが、対象データが複数のクラスタの所属することを許容するソフトクラスタリングの手法を採用するものとする。
【００５６】
（７−５−２）観測行列生成部２３２
観測行列生成部２３２は、ユーザが広告をクリックした実ＣＴＲを観測値として観測行列を生成する。観測行列生成部２３２は、ユーザクラスタと広告クラスタとの全ての組合せについて、当該ユーザクラスタに帰属するユーザが、当該広告クラスタに帰属する広告を閲覧したインプレッション数および当該ユーザが当該広告をクリックしたクリック数を取得して、クリック数をインプレッション数で割って実ＣＴＲを算出する。
【００５７】
（７−５−３）信頼度算出部２３３
信頼度算出部２３３は、観測行列の要素の信頼度を算出する。上述したように本実施形態では観測行列の要素の信頼度はベータ分布の分散のべき乗の逆数１／ｖｕａｓであるものとする。なお、事前分布Ｂｅ（ｐ，ｑ）のｐ、ｑは予め設定されているものとする。また、指数ｓも予め定められているものとする。
【００５８】
（７−５−４）低ランク近似処理部２３４
低ランク近似処理部２３４は、信頼度による重み付けを行った上で観測行列に対する低ランク近似を行う。低ランク近似処理部２３４は、重み付けした観測行列に行列Ｕ，Ａを近似させて、近似させた行列Ｕ，Ａを近似行列記憶部２５４に登録する。本実施形態では、低ランク近似として行列因子分解を用いるものとするが、特異値分解その他の各種の低ランク近似の手法を採用することができる。欠損値を許容しない低ランク近似の手法を採用する場合に欠損値が発生したときは、例えば０％を観測値として補完するなど、一般的な手法により欠損値を補完した上で低ランク近似を行うようにすることができる。
【００５９】
＝＝（８）解析処理＝＝
図１０は解析処理部２１５による解析処理の流れを示す図である。
クラスタリング処理部２３１は、例えばユーザ情報に含まれている属性、インプレッションログおよびクリックログなどに基づく行動履歴などを用いてユーザのクラスタリングを行い、ユーザクラスタを決定し、各ユーザの各ユーザクラスタへの帰属度を算出する（Ｓ３１１）。クラスタリング処理部２３１は、算出した帰属度を対応するユーザ情報に設定するようにユーザデータベース２５３を更新する（Ｓ３１２）。
【００６０】
クラスタリング処理部２３１は、広告についても広告情報に含まれている項目の内容や、広告情報のＵＲＬが示すランディングページの内容を用いて広告のクラスタリングを行い、広告クラスタを決定し、各広告の各広告クラスタへの帰属度を算出する（Ｓ３１３）。クラスタリング処理部２３１は、算出した帰属度を広告情報に設定するように広告データベース２５２を更新する（Ｓ３１４）。
これにより各ユーザの各ユーザクラスタに対する帰属度がユーザ情報に設定され、各広告の各広告クラスタに対する帰属度が広告情報に設定される。
【００６１】
観測行列生成部２３２は、ユーザクラスタおよび広告クラスタについての実ＣＴＲを要素とする観測行列を作成する（Ｓ３１５）。図１１は観測行列の作成処理の一例を示す図である。観測行列生成部２３２は、ユーザクラスタおよび各広告クラスタについて、以下の処理を行う。すなわち、観測行列生成部２３２は、当該ユーザクラスタへの帰属度が０（または所定の閾値）より大きいユーザ情報のユーザＩＤをユーザデータベース２５３から読み出してＵＬとする（Ｓ３３１）。
【００６２】
観測行列生成部２３２は、当該広告クラスタへの帰属度が０（または所定の閾値）より大きい広告情報の広告ＩＤを広告データベース２５２から読み出してＡＬとする（Ｓ３３２）。観測行列生成部２３２は、インプレッションログ記憶部２５５に登録されているインプレッションログのうち、ユーザＩＤがＵＬに含まれており、かつ、広告ＩＤがＡＬに含まれているものをカウントしてインプレッション数ｉｕａとして算出する（Ｓ３３３）。観測行列生成部２３２は、クリックログ記憶部２５６に登録されているクリックログのうち、ユーザＩＤがＵＬに含まれており、かつ、広告ＩＤがＡＬに含まれているものをカウントしてクリック数ｃｕａとして算出する（Ｓ３３４）。
【００６３】
観測行列生成部２３２は、インプレッション数ｉｕａが０でなければ（Ｓ３３５：ＹＥＳ）、クリック数ｃｕａをインプレッション数ｉｕａで割って実ＣＴＲを算出し（Ｓ３３６）、インプレッション数ｉｕａが０であれば（Ｓ３３５：ＮＯ）、欠損値を表す値（例えば−１あるいはｎｕｌｌ値とすることができる。）を実ＣＴＲとする（Ｓ３３７）。
観測行列生成部２３２は、以上の処理を各ユーザクラスタおよび広告クラスタについて繰り返した後、実ＣＴＲを要素とした観測行列を作成する（Ｓ３３８）。
【００６４】
次に信頼度算出部２３３が、欠損値以外の要素について、要素に対応するインプレッション数ｉｕａおよびクリック数ｃｕａと事前分布のパラメータｐ、ｑとを式Ｅ３に代入して分散ｖｕａを算出し、算出した分散のｖｕａを底としｓを指数とするべき乗値で１を割った値を信頼度１／ｖｕａｓとして算出する（Ｓ３１７）。
【００６５】
低ランク近似処理部２３４は、観測行列の欠損値以外の各要素について上述した式Ｅ４の目的関数を適用した値の合計が最小となるように、行列ＵおよびＡを決定し（Ｓ３１８）、決定した行列ＵおよびＡを近似行列記憶部２５４に登録する（Ｓ３２０）。
以上のようにして、観測行列の要素に信頼度を乗じたうえで低ランク近似が行われ、近似された行列Ｕ，Ａが近似行列記憶部２５４に登録される。 
【００６６】
＝＝（９）リクエスト処理＝＝
図１２は、Ｗｅｂサーバ２０により行われる処理の流れを示す図である。  
ＨＴＴＰ処理部２１１は、ユーザ端末１０からＨＴＴＰのリクエストを受信する（Ｓ４０１）。なおリクエストには、ＵＲＬ、ユーザＩＤおよび現在日時が設定されているものとする。ＨＴＴＰ処理部２１１は、リクエストにリダイレクトＵＲＬが指定されているか否かにより、広告がクリックされたか否かを判定する（Ｓ４０２）。
【００６７】
広告がクリックされたと判定した場合（Ｓ４０２：ＹＥＳ）、ログ収集部２１４は、リダイレクトＵＲＬに設定されている広告ＩＤに対応する広告情報を広告データベース２５２から読み出し、リクエストに設定されているユーザＩＤおよび現在日時ならびに広告ＩＤを含むクリックログを作成してクリックログ記憶部２５６に登録する（Ｓ４０３）。ＨＴＴＰ処理部２１１は、広告情報のＵＲＬにリダイレクトするようにＨＴＴＰのレスポンスをユーザ端末１０に送信する（Ｓ４０４）。
【００６８】
一方、広告がクリックされていないと判断した場合には（Ｓ４０２：ＮＯ）、図１３の処理により、広告選択部２１３が選択した広告の広告情報を含む広告リストを作成する（Ｓ４０５）。なお、図１３に示す広告情報の選択処理については後述する。
【００６９】
Ｗｅｂページ作成部２１２は、リクエストに応じて各種のコンテンツを表示するためのＨＴＭＬファイルなどの画面情報を作成する（Ｓ４０６）。なお、ステップＳ４０６における画面情報の作成処理は、一般的なＷｅｂサーバによる処理を採用することができる。
【００７０】
Ｗｅｂページ作成部２１２は、広告リストに含まれる各広告情報について、所定のＵＲＬの引数に広告情報に含まれる広告ＩＤを設定したリダイレクトＵＲＬを作成する（Ｓ４０７）。リダイレクトＵＲＬは、例えば「www.foobar.com/ad?id=xxxx」という形式とすることができる。Ｗｅｂページ作成部２１２は、広告リストに含まれる各広告情報について、広告情報に含まれるタイトルを内容として含むリダイレクトＵＲＬへのリンクタグ（例えば、「<a href="http://www.foobar.com/ad?id=xxxx">タイトル</a>」という形式とすることができる。）を画面情報に挿入する（Ｓ４０８）。
【００７１】
ＨＴＴＰ処理部２１１は、作成された画面情報をリクエストへの応答としてユーザ端末１０に送信する（Ｓ４０９）。ログ収集部２１４は、広告リストに含まれる各広告情報について、広告情報に含まれる広告ＩＤと、リクエストに含まれていたＵＲＬ、ユーザＩＤおよび現在日時とを含むインプレッションログを作成してインプレッションログ記憶部２５５に登録する（Ｓ４１０）。
【００７２】
＝＝（１０）広告の選択処理＝＝
図１３は、ステップＳ４０８における広告の選択処理の流れを示す図である。  
配信候補抽出部２２１は、広告データベース２５２から所定数ｍ個の広告情報を抽出する（Ｓ４２１）。なお、広告データベース２５２からどのような広告情報を抽出するかは任意に設定可能である。例えば、ランダムにｍ個の広告情報を抽出するようにしてもよいし、広告情報のタイトルがコンテンツにマッチする度合いの高い順にｍ個の広告情報を抽出するようにしてもよいし、ユーザが興味を有しているカテゴリをユーザ情報の属性として記憶しておき、そのカテゴリにマッチする広告情報をｍ個抽出するようにしてもよい。
【００７３】
評価値算出部２２２は、リクエストに設定されているユーザＩＤに対応するユーザ情報をユーザデータベース２５３から読み出し、読み出したユーザ情報に含まれている各ユーザクラスタへの帰属度を要素とするユーザベクトルｕを作成する（Ｓ４２２）。評価値算出部２２２は、近似行列記憶部２５４から行列ＵおよびＡを読み出す（Ｓ４２３）。
【００７４】
評価値算出部２２２は、抽出した広告情報のそれぞれについて以下の処理を行う。すなわち、評価値算出部２２２は、広告情報に含まれている各広告クラスタへの帰属度を要素とする広告ベクトルａを生成し（Ｓ４２４）、ユーザベクトルｕの転置ベクトル、行列Ｕ、広告ベクトルａおよび行列Ａを乗じた値を、当該広告ＩＤが当該ユーザによりクリックされる傾向の評価値（期待クリック性向）を算出する（Ｓ４２５）。
【００７５】
評価値算出部２２２が以上の処理を各広告情報について行った後、広告決定部２２３は、期待クリック性向の大きい順にｎ個の広告情報を選択して広告リストとする（Ｓ４２５）。なお、広告決定部２２３は、期待クリック性向に広告情報の入札額を乗じた値の大きい順にｎ個の広告情報を選択するようにしてもよい。
【００７６】
＝＝（１１）効果＝＝
以上説明したように、本実施形態の広告配信システムでは、ユーザと広告との関係性の観測値（本実施形態では実ＣＴＲ）に、その信頼度による重み付けをする補正をしたうえで、低ランク近似を行っている。したがって、例えば信頼度の小さな観測値については観測値と予測値との差が小さく評価され、信頼度の高い観測値については観測値と予測値との差が大きく評価され、この評価値を最小化するように近似が行われるので、結果として信頼度の高い関係性を予測可能な近似の行列を作成することができる。
【００７７】
また、低ランク近似を行うことにより行列のランクを低くすることができるので、関係性（クリック率）に関するノイズを除去することができる。
【００７８】
また、本実施形態では、関係性としてクリック率を想定しているところ、オンライン広告におけるクリック率は非常に小さい値（１％未満であることも多い。）となることが知られている。したがって、特にインプレッション数が少ない間では、１度のクリックによる関係性への影響は非常に大きく、商品の購入回数が少ない間における１度の購入や、ランキングの評価回数が少ない間における１度のランキング付けなどを行った場合に比べて、関係性の予測値としては信頼度が著しく低くなる。よって、本実施形態のように信頼度を用いて観測値を補正することにより、クリックによる過度な影響を抑えることが可能となり、近似によるノイズ除去をより効果的に行うことができる。
【００７９】
また、本実施形態では観測値（実ＣＴＲ）の分散を底とするべき乗値の逆数を信頼度として使用している。したがって、観測値のばらつきが小さいほど信頼度が高くなるようにすることができる。低ランク近似は観測値と近似行列の積との差を最小化することになるため、観測値自体にばらつきが大きい場合には、最小化による近似の信頼度も低くなると考えられる。よって、本実施形態のように、ばらつきが小さい程信頼度を高くすることにより、最小化による近似の結果の信頼度も高くなることが期待される。
【００８０】
また、本実施形態の広告配信システムでは、クリック率はベータ分布に従うものとし、ベイズ推定による推定後の事後分布の分散が小さいほど信頼度が高くなるようにしている。一般に広告のインプレッション数が増えるに従って実クリック率の信頼度も上がると考えられるところ、ベイズ推定でも学習が進むにつれて分散が小さくなっていく。したがって、本実施形態のように事後分布の分散の小ささを信頼度とする妥当性が担保され、妥当な信頼度を用いて観測値を補正することができる。
【００８１】
また、本実施形態の広告配信システムでは、ユーザおよび広告をクラスタに分類した上で関係性（クリック率）を観測し行列で管理しているので、大量のユーザや広告が存在する場合であっても、関係性の管理を容易に行うことが可能となり、観測値や関係性の管理にかかるリソースを低減することができる。また、広告クラスタごとにクリック率を観測することができるので欠損値を減らすことができる。よって、近似させた行列を用いた関係性の予測の精度を向上することができる。
【００８２】
また、本実施形態の広告配信システムでは、配信する広告を決定する際に、期待クリック性向の大きい順に広告を選択しているので、ユーザのニーズに合わせた広告を配信することを可能とするとともに、広告のクリックによる広告収益を向上させることができる。
【００８３】
＝＝（１１）変形例＝＝
なお、本実施形態では、クリック率はベータ分布に従うものとしてベイズ推定の事後分布の分散に応じて信頼度を決定するものとしたが、クリック率は正規分布に従うものとして正規分布の分散に応じて信頼度を決定するようにしてもよい。この場合、分散ｖｕａはクリック率をｒとして、次式により算出することができる。
0005507607.tif 000006
この分散を底として指数をｓとするべき乗値の逆数を信頼度としてもよい。
【００８４】
また、クリック数およびインプレッション数の少なくともいずれかに応じて信頼度を決定してもよい。例えばインプレッション数やクリック数そのものを信頼度としてもよい。また、クリック数を底としたべき乗値とインプレッション数を底としたべき乗値との積を信頼度としてもよい。また、クリック数またはインプレッション数の対数を信頼度としてもよいし、クリック数の対数とインプレッション数の対数との合計値を信頼度としてもよい。
【００８５】
また、本実施形態ではインプレッション数を問わずに分散に応じて信頼度を決定するものとしたが、インプレッション数が所定の閾値を超えた場合には信頼度を１として補正を行わないようにしてもよい。
【００８６】
また、本実施形態では、ユーザベクトル、行列Ｕ、行列Ａおよび広告ベクトルを乗算して期待クリック性向を算出するものとしたが、行列ＵおよびＡを乗じて性向行列を作成し、作成した性向行列を近似行列記憶部２５４に記憶するようにして、ユーザベクトルと性向行列と広告ベクトルを乗算して期待クリック性向を算出するようにしてもよい。
【００８７】
また、予測モデルＥ１を用いて予測ＣＴＲを算出し、予測ＣＴＲを広告の評価値として算出するようにしてもよい。
【００８８】
また、本実施形態ではソフトクラスタリングによりユーザおよび広告はそれぞれ複数のクラスタの帰属することが可能であるものとしたが、ハードクラスタリングにより１つのクラスタにのみ帰属可能としてもよい。この場合、評価値算出部２２２は、ユーザが帰属するユーザクラスタに対応する要素を行列Ｕから読み出し、広告が帰属する広告クラスタに対応する要素を行列Ａから読み出し、読み出した要素に基づいて評価値を決定することができる。この場合、読み出した要素は、平均をとってもよいし、合計してもよい。また、行列Ｕおよび行列Ａを乗じて性向行列を作成し、作成した性向行列からユーザが帰属するユーザクラスタと広告が所属する広告クラスタとに対応する要素を読み出し、読み出した要素に応じて評価値を決定するようにしてもよい。
【００８９】
＝＝（１２）他の適用例＝＝
本実施形態では広告の配信を想定しているが、広告の配信に限らず、各種のコンテンツの提供を行うシステムに適用してもよい。また、コンテンツとユーザとの関係性もクリック率に限らず、ユーザがコンテンツを嗜好する度合いなど各種の関係性とすることができる。また、本実施形態の低ランク近似の処理は商品のレコメンド処理における協調フィルタリングなどに適用することもできる。
【００９０】
以上、本実施形態について説明したが、上記実施形態は本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明は、その趣旨を逸脱することなく、変更、改良され得ると共に、本発明にはその等価物も含まれる。
【符号の説明】
【００９１】
２１１  ＨＴＴＰ処理部
２１２  Ｗｅｂページ作成部
２１３  広告選択部
２１４  ログ収集部
２１５  解析処理部
２２１  配信候補抽出部
２２２  評価値算出部
２２３  広告決定部
２３１  クラスタリング処理部
２３２  観測行列生成部
２３３  信頼度算出部
２３４  低ランク近似処理部
２５１  Ｗｅｂ情報データベース
２５２  広告データベース
２５３  ユーザデータベース
２５４  近似行列記憶部
２５５  インプレッションログ記憶部
２５６  クリックログ記憶部
【図１】
0005507607.tif 000007
【図２】
0005507607.tif 000008
【図３】
0005507607.tif 000009
【図４】
0005507607.tif 000010
【図５】
0005507607.tif 000011
【図６】
0005507607.tif 000012
【図７】
0005507607.tif 000013
【図８】
0005507607.tif 000014
【図９】
0005507607.tif 000015
【図１０】
0005507607.tif 000016
【図１１】
0005507607.tif 000017
【図１２】
0005507607.tif 000018
【図１３】
0005507607.tif 000019