研究論文から垣間見る中国人の国民性

Exploring in the Weblog Space by Detecting Informative and Affective Articlesより（ｗｗｗ２００７）

この研究はブログ記事をある観点から２つに分類するのという事を行っている。
分類する２つについて述べると、一つは個人的な感想を述べた日記的なブログ記事であり、もう一つは事実や客観的な意見（大衆的な意見？）を淡々と述べたような新聞やニュースサイトに載っているようなことを書いたブログ記事である。
ブログというものは本来、特に日本では個人の日記という意味合いが強いため、前者の日記的なブログ記事が大半であると思うかもしれないが、ブログ検索エンジンでブログを検索してみるとニュース記事のようなブログ記事も多く引っかかってくる。
個人の意見（一般市民の意見）を抽出したい時にニュース記事みたいな記事が引っかかってきてうざいからこのような研究を始めたのだと最初思ったのだが、実はそうではないみたいである。
この研究ではニュース記事のようなブログ記事を良質なブログ記事とみなしていて、個人の感想は有用ではないとしているのである。
ブログにニュース記事を求めるのは意味がわからないっということで議論していたところ、次のような結論に落ち着いた。この論文を書いた人は中国人であり、中国は社会主義国家である。すなわち個人が好き勝手な感想を述べてもらっては全体の統一を取る上で困る、だから個人の意見などは排除してやろう。
ブログの本質は個人による情報発信にあると思っていたが、中国では意外とそうでもないのかもしれないと思った。研究というよりも文化を知る上でこの論文は重要ではあるまいか！

Internet-Scale Collection of Human-Reviewed Data

内容は機械学習などで使うラベル付けを考える時に、企業内や他の企業へのアウトソーシングを行うよりも、インターネットを利用して大衆の力、すなわち集合知を使った方がより安く速くラベル付けが行えるのではないかという考えの元、システムMというアプリケーションを使ってそれらを実証する実験を行っている。システムMはWeb上で集めた労働者に賃金を払いラベル付けを行ってもらうシステムである。ユーザの集め方の具体的な方法については書いていないのが残念ではあった。なぜならユーザを集めるのにお金が掛かっていては結局企業内でラベル付けを行ったほうが安くて済むかもしれないからである。またヤフーアンサーを使ってラベル付けを大衆にしてもらおうという試みも行っている。これはうまく行けば無償でラベルデータを手に入れることができ非常に便利であるが、Q&Aの方式で書かれた文書を機械可読な方式で置き換えるのは非常に難しい話である。そんな時Q＆A方式のサイトをもう少し拡張して、多数決やラジオボタンを使った複数選択形式のアンケートを導入できれば機械可読できる確率が高まり有用である。

1. INTRODUCTION

最近の企業やWebコンテンツ管理システムは、異なるソースからデータを統合することを自動化している。例えばヤフーショッピング、ヤフートラベル、ヤフーローカル（地域の口コミ、就職情報などを検索するアメリカ限定のサービス）などではコンテンツを有料フィードプロバイダ（有用な構造化されたデータを有料で提供しているサービス会社か？）やユーザやWebクローリングから収集している。人手により評価されたデータはそのような自動情報収集システムにおいて重要な役割を果たす。コンテンツ集約はつねに属性抽出(Attribute extraction)、カテゴライゼーション(Categoraization)、エンティティレゾリューション(Entity resolution)を含む。ここでこの３つの意味を説明しておく

Attribute Extraction：128MB(capacity),size 10,10:00-6:00(time)などの副次的な情報に対してラベル付けを行う事

Categorization：外部の分類法を用いてデータの記録を一つあるいはより多くの場所に割り当てること。

Entity resolution：データレコード間に表記の違いがあった場合、それが同じものを指しているのかを確認すること。例えばHilton San Jose,123 Main StreetとSJ Hilton,123 Main St.が同じホテルを指しているかどうかなど。

これらを合わせて、我々はACEと呼ぶことにする。またこのような技術を使ったアプリケ

ーションをACEアプリケーションと呼ぶことにする。

ACEアプリケーションは機械学習アルゴリズムの学習やルール推論や質を確かめるモニタリングやフィードバックのために、人によってラベル付けされた質の高いデータを必要とする。さらに人のレビューはしばしばデータの質を上げるために重要である。例えば外部データフィードはエラーや間違えた情報に対して人手で調整される必要があるかもしれない。あるいはユーザが作り出したコンテンツはスパムや人を不快にさせるようなコンテンツを抑える必要があるかもしれない。（？エラーやスパムを人手により評価されたデータにより抑えられるという事だと思う。）

　効果的に人が評価したリソースを活用する研究は今までにある、特にアクティブラーニングの領域で顕著である。アクティブラーニングは最小限の人を用いて、機械学習のパフォーマンスを最大限に向上させようというものである。ところが人がレビューしたデータを大規模に集める仕組み、人手のデータを提供する回答者の行動に関する研究はほとんど行われていない。

　工業において、人手により評価されたデータを収集するためには一般的に低コスト契約作業員を使用する。これらの作業員は前述したACEアプリケーションで活用するためにデータのラベル付けを行う。このレビューとラベル付けの生態系（ecosysytem）はラベル付けに対して一つの便利なビジネスインタフェースを提供する。しかしますます上昇する関連コストに対して統合された供給連鎖管理システムの潜在性と処理能力と同様に拡張性の限界を持っている。（要するにラベル付けされたデータを作るのにわざわざ低コスト契約作業員を使っていては、大規模システムになるにつれてコストが嵩んでいきシステムの拡張に無理が生じるということ。だからそれ以下のコストでラベル付けされたデータを集める仕組みが必要なのである。）

一方でGoogle Image LabelerやAmazon Mechanical Turkは人手のデータを収集するためインターネットユーザの集合知を活用しようと試みている。潜在的に人が評価したデータを収集する技術プラットフォームとして、これら２つのシステムを凌駕するものとして我々はYahoo! Answersのような一般的なQ＆Aの場を挙げる。

インターネット規模で人手で評価されたデータを集めることにより外注や企業内でラベル付けを行う場合のボトルネックとなる処理能力の問題を克服でき、さらにコストも抑えられるのである。

この論文は、データの質とタスクの処理能力とユーザの振る舞いに焦点を当てた人により評価されたデータをインターネット規模で収集するメカニズムの最初の公式の研究である。我々は一般的なQ＆Aサイトが人手により評価されたデータの収集に使えるか調べるためにYahoo!Answers上で人手で評価されたデータを集める実験も行った。

2. RELATED WORK

   1. Active Learning and Collaborative Filtering

教師あり機械学習アルゴリズムはACEアプリケーションにおいて共通して使われる。正確なラベルのついたトレーニングデータセットは学習アルゴリズムのパフォーマンスを上げる上で重要である。ところが人間のレビューをラベル付けに使う事はコストが高い。

Active learning[6]は限られた人手によるレビューを最大限に学習器生成に活用することに焦点を当てている。Active learningはentity resolution[16]や情報抽出[3]やテキスト分類[13]など多くのアプリケーションの分野に適用されている。

　協調フィルタリング[5],[15]はユーザが提供するデータの集合を、ユーザの嗜好を推測するために使っている。

　我々の研究はこれら２つの研究領域を補助するものである。

2. Data Cleaning

データクリーニングはデータのエラーと不具合を発見して取り除く研究領域である。Entity resolution[4]は一般的なデータクリーニングアプリケーションである。これは実世界のものを表しているデータレコード間の関係を確認するアプリケーションである。データクリーニングの研究は大部分がアルゴリズムによる解決とデータの質による評価に焦点を当てている。しかし我々の研究ではアルゴリズムでデータを使うのではなく、そのようなアルゴリズムで使われる人手で批評されたデータを集めることに重点を置いている。

3. Human Computation

Human Computation[19]は多数の人々を活用して計算やコンテンツ作りを実行させるという新興の理論的枠組みである。カーネギーメロン大学で開発されたESP Game[20],Peekaboom[21],Verbosity[22]はHuman Computingの模範となるゲームアプリケーションである。我々の研究はインターフェースのデザイン設計よりも人により批評されたデータの解析に焦点を当てている。Gentryら[8]によるセキュリティや信頼性の観点からのhuman computationの研究もある。

3. SYSTEM TASKS

我々はSystem Mというウェブベースで人手のデータを収集するシステムを実験に用いる。

我々の実験は、現在のデータのサプライチェーンをシステムM上の仕事の形で複製することである。システムMは十分な遂行能力を持っており、構造化された応答インタフェースを提供し、我々の用いる人手で評価されたデータ収集アプリケーションのために多くの役立つ機能を提供する。しかしシステムMではユーザ数が少なく（limited user base）、賃金の作業員への支払いを前提としている。それとは対照的にYahoo! Answersはずっと大きいユーザ数を有しており、作業員には賃金は支払われない。ただし収集されたデータは構造化されていない。セクション５ではSystem Mでの実験をYahoo! Answers上でも行う。

1. System M Overview

システムM上で、依頼人は作業人に仕事を与える。与えられたタスクに対して依頼人は、タスクが作業員に承認されるまでの寿命、仕事を受け取ってから完了するまで間での長さ、受け入れるべき答えの数、承認された答えごとに支払う報酬を指示する。依頼人は受け取った答えを承認するか却下するか一方的に決定できる。承認された答えだけが課金対象となる。

　システムMではタスクを割り振る前にまず作業員にテストを行わせることで、作業員の作業の正確さを判定し、資格スコアを算出する。そのスコアに応じてタスクを割り振る。そして一度資格スコアが決定するともうそのスコアを更新する事はできなくする。

　

2. Tasks and Datasets

我々の実験は属性抽出とentity resolution(存在解決)の２つのACEアプリケーションに焦点を置いている。Entity resolutionでは２つのホテルのデータが与えられ、その２つの名前や位置や電話番号が同じであるかそうでないかなどを判断することを作業員は頼まれる。

　属性抽出では、一つは子供か大人かの年齢カテゴリーを選択する。後の２つはブランドや、モデルを製品についての記述から選択し、自由記述する。我々がこれら４つのアプリケーション選んだ理由は、これらが人手でラベル付けされたデータが必要なYahoo!Marketplaceのバックエンドデータ処理システムの中のコンテンツ収集アプリケーションを代表するものであったからである。（実際にマーケットプレイスでラベル付けデータを用いている）

　この実験に使われるデータセットは人手でラベル付けされた優良データセットの一様乱数サンプルである。

4. EXPERIMENTS

   1. System M Qualification Tests

最初の実験として、我々は４つのアプリケーション（ホテルの解決、年齢抽出、ブランド名抽出、モデル抽出）それぞれに対して資格テストをシステムMに投稿した。資格テストには料金は支払われない。

　ホテル解決テストは２０個のホテルの記録のペアが与えられ、作業員はそれが「同じホテル名かどうか」、「同じ位置にあるが名前が違うか」、「同じホテル名であるが場所が違うか」、「完全に異なるものか」、「その他」の５つを選択する。

　年齢、ブランド、モデルについてはまず製品の記述が与えられる。年齢では「大人」か「子供」か、「判定できない」かを選択する。ブランド、モデル抽出テストについては作業員は製品のブランドやモデルをタイプする。

2. System M Experiments

   1. Experiment Settings

資格テストにより作業員の能力がわかったので今度は作業員の能力別にグループ分けをして資格があるグループと、無いグループを分ける事の有効性を確かめる。まず能力、実験別に１１のグループに分け、それぞれのグループに対して３００のタスクを課した。

また１つのタスクに付き１セントが支払われる。実験で設定したパラメータは表２の最上部にある通りである。

2. Accuracy Results

実験結果を表２に示す。

図３～６は作業員の正確さの離散分布であり、正確さを[0,0.05]~[0.95,1],[1,1]の２１分割で離散化してグラフで表している。

図７は作業員のタスクでの正確さと作業員のテストでの正確さの関係を示している。これによるほとんどこの２つには相関がない。

3. Worker Productivity Results

図８は回答数で上１０％に入っている人が、全体のタスクのどれだけをこなしたかを示したグラフであるが、これを見るとおよそ２０～４０％のタスクを上１０％でこなしていることがわかり、データが不均一である事がわかる。

図９は作業員の正確さと３００問のタスク中何％答えたかの関係であり、１０％未満しか質問に答えていない作業員は正確さにかなりばらつきがある事がわかる。

　また仕事を請け負った時間と提出した時間を計ることで、作業員の時給を計算し、分析した。その結果が表３のようになる。この表から

1. 資格の制限が無くなれば無くなるほど時給が増える

2. ３００問中の５％以上の質問に答えている人は時給が他の人に比べて高く、正確さも若干高くなる傾向がある。

3. 高時給の人ほどたくさんの質問に答えており、回答も正確である場合が多い。

4. ほとんどの場合最低賃金率（アメリカではどれくらいか知らないが）を大きく下回っている。

という事が分かった。

4. Worker Accuracy Across Task Types

図４は作業員が１１種類のタスクのうち何種類のタイプのタスクに従事したかを示す図である。全体と、各タスク５％以上の質問に答えた作業員で場合分けしている。我々はさらにタスクのタイプ別に作業員の答えの正確さを調査した。どのタイプのタスクでもコンスタントに正確な作業員もいた。一方でタスクのタイプによって正確さが大きく変わる人もいた。２つ以上のタイプに回答していた人は、全体と各タスク５％以上答えていた人両方とも、正確さが高い人が多かった。

5. Yahoo! ANSWERS

巨大なオンラインのソーシャルネットワークサイトを人手により評価されたデータの収集に使えないだろうか？そこでYahoo! Answersで実験してみることにする。Yahoo!Answersはトピック別ディレクトリで構成された巨大Q＆Aサイトである。これは、ユーザーの献身的行為であり、ユーザには報酬が支払われないという点でGoogle Image Labelerと類似している。２つの疑問が浮かび上がった、一つ目はYahoo!Answersのコミュニティに我々のアプリケーションを導入できるかどうか。もう一つはAnswersの技術プラットフォームが我々のアプリケーションに活用できるかどうかである。これらの質問に答えるため４日間８１個の資格テストの質問を手動でYahoo!Answersに投げかけた。それぞれの質問の有効回答期間は３日であった。

　その結果９５％の質問に対して最低１つの答えが返ってきていた。我々は手動でそれらがスパムかどうか、役に立つか、質問に答えているか、機械可読可能か、正解かを調べた。表５はその詳細である。

　最も大きい課題は構文解析である。これはまずスパムや役に立たないデータと役立つデータに分類する。次に冗談や、文法的な曖昧さを解消しユーザの意図を解析する。そもそもYahoo!Answersは人的交流を意図して作られているため機械可読にするのは難しい。ブランドやモデルの抽出においてテンプレートマッチングを用いる事もできるが余すところ無くマッチングする事は不可能で明らかな限界がある。

　しかしそれでもある程度の有効回答を得ることができる。またYahoo!Answersの質問に「機械処理するので余計な文章を書かないで」と明記する、あるいは選択形式で質問に答えられるようにするなどYahoo!Answersのインフラを変えていけば、巨大Q&Aサービスを使う事はより人手により批評されたデータを得るのに有効な手段となるはずである。

　

6. CONCLUSIONS

この研究で、我々は人手により評価されたデータを集めるために、人手により評価されたデータの質、人間の処理能力、ユーザの行動を解析する実験を行った。この研究の主な貢献は、実際に実験して得たのデータセットを使ったことと、その結果得られたデータの質とユーザの行動の徹底的な解析にある。我々の出した正確さのデータは実際のACEアプリケーションにとって非常に励みになるものである。機械学習のためのトレーニングセットのラベル付けや質の確かさを保証するためのモニタリング（quality assurance monitoring）を行いたい場合、これらのデータは参考になる。

　将来的には未来のWeb情報統合システムや内容収集システムは人手により評価されるデータを収集するインターネットベースのシステムと整合を取るようになるだろう。例えば必要に応じてデータ処理システムが、データ収集システムに人間のレビューを要求するようになるであろう。将来の課題として、より大規模に人手により評価されたデータを収集するシステムと作業員のやる気を起こさせるような設計について調査し、より大規模な実験をしていきたいと思っている。またYahoo!Answerからうまくデータを取り出せるような構文解析法や、データを機械で取り出しやすくするようなリッチなインターフェースを考えて行きたい。

6.1 Data Validation Application

この節では人手により評価されたデータを用いるアプリケーションについての議論をデータ検証に拡張させることを考える。人間こそがラベル付けを行う唯一の権威であるから、人間により評価されるデータはACEアプリケーションにとって非常に重要である。しかし人間の判断もあいまいであるし、そもそもデータそのものに曖昧さを含むものがあるためラベルデータはそれ自体完璧なものではない。そこで人間が以前の人手により評価されたデータを検証して、それをフィードバックしていくことによりデータの質と信頼性を向上させることができる。

テキストの自動分類の簡単なまとめ

テキストの自動分類について研究で調べる必要があったので整理してみた.何かの役に立つかもしれないです.

テキストの自動分類に関する研究は1960年にMaronが行った事例が発端とされている.その後1990年代に入り,Webで大量のデータが手に入るようになり,活発に研究されるようになった.
テキスト分類は大きく分けて２つあり,一つは予めカテゴリを定めずに,類似する主題を持つテキスト集合をグループ化する手法であるクラスタリング,もう一つは予めカテゴリを定めておいて,そのいずれかに新たに入ってきた文章を振り分けるテキストカテゴライゼーションである.
テキストカテゴライゼーションにおいて,どの語を分類ルールの生成に使うか,という問題があるが,これについてはN-gramという文章をN個ずつ,単語を一つずつずらしながら区切っていき,それらを語とする方法と,形態素解析という,予め辞書に単語を登録しておき,文章中の文字を辞書と照合することにより,文章を単語に分解していく手法がある.さらに分類精度を高めるために,より文書分類に重要な語を抽出しようという試みもある.これには言語特徴を用いた手法と,統計的特徴を用いた手法の２通りがあり,通常は両方を合わせて使う事が多い.言語特徴として,言語には語と語の関係を表し,それ自体は意味を持たない機能語と,語自体がある概念を表現している内容語に分けられる.機能語は助詞や助動詞を指し,内用語は主に名詞や動詞である.形態素解析を用いている場合は品詞情報を得ることが可能であるので簡単に機能語と内用語を分類する事ができる.一方でN-gramを用いている場合は全てカタカナや,全て漢字が使われている語は内容的に意味を持つ可能性が高い,特に漢字は主題的特徴を現している事が多いという事で,これらを重要語として抽出することが多い.次に統計的特徴として,該当カテゴリにおける語の出現頻度TFや,ある語が出現するテキストがカテゴリに属しているテキスト数DF,あるいは相互情報量,カイ２乗統計を使ったもの,またそれらを組み合わせて使ったものなどが存在する.また統計的特徴を用いたものとしてLSI(Latent Semantic Indexing:滞在意味インデキシング)という方法もあり,これはカテゴリ内で同時に出現する傾向のある複数の語を一つにまとめてしまうもので,例えば「情報センター」という言葉を「情報」と「センター」という２語ではなく１語として捉えることを言う.
分類ルールの作成に関しては,1980年代までは知識ベースのアプローチが主であり,人手で書かれた規則を用いる方法が一般的であったが,1990年代に入ると機械学習を用いた手法が多くなりサポートベクターマシン等が使われるようになった.

クロスレコメンドの効果は？

２００６年の春から始まったディレクトリサービスにクロスレコメンドというものがある。これはWebサイトを複数の大手ポータルサイトのディレクトリに登録するサービスである。４万２０００円を払い審査に通るとgooやexcite,biglobeなど相当たるサイトのディレクトリに登録される。さてこのサービスにはどれ程のSEO効果があるのだろうか？ちなみに巷ではアクセスアップおよびSEOに対して効果があると様々なメディアで取り上げられていたり、あるサイトではほとんど検索順位が上がらずSEO効果はなかったと書かれていたりと賛否両論である。まあしかし実際にクロスレコメンドに登録して順位が上がったとしても今の検索エンジンは複雑なのでそれがクロスレコメンドへの登録によるものなのか他の要因によるものなのかなどは分かる術はない。そこで検索エンジンのアルゴリズムを考慮してクロスレコメンドの効果について考えたいと思う。
　まず効果があると思われる点が、信用の置ける大手ポータルサイトからのリンクされるという点、それも複数のドメインからのリンクであるという点である。
　質の低いスパムサイトに多数リンクしているようなページからのリンクであればほとんどSEO的には効果がないが、大手ポータルサイトのような質の非常に高いサイトからのリンクは非常に有用なものとなる。さらに複数の大手ポータルサイトからのリンクを受けることになるのでその効果はかなりのものであると言える。また相互リンクではSEO的な効果は半減してしまうが（検索エンジン側でアルゴリズムを公開しているわけではないのでおそらくとしか言えないが常識的に考えればそうだろう）受けるのは一方的な被リンクなわけであるからこれもかなりSEO的にプラスに働いてくるといえる。さらにヤフーディレクトリと比べて登録サイトが少ないのでこの点でもSEO的にプラスである。
　逆に効果が減少してしまうんじゃないかという懸念要素として、検索エンジンの高度化によるクラスタリング機能がまず第一に考えられる。クラスタリング機能とは検索エンジンが内容の似通ったページを類似ページ、ミラーページとしてみなすことである。類似サイトとみなされたページからのリンクはSEO効果が下がるかあるいは全くリンクとしての価値がなくなってしまう恐れがある。ところでこのサービスのリンク集はクロスレコメンドが作っているので、リンク集はgooであってもexciteであってもniftyであってもほとんど同じとなる（リンク先ページとその説明は完全に同じ、サイトのデザイン部分が違うだけ）。すなわちこれらのリンク集は互いに類似ページとみなされてそのSEO価値を失う可能性は大いにある。現在グーグルではクロスレコメンドのディレクトリに対してこのクラスタリングがなされていると思われる節がある。グーグルのバックリンク情報を調べたときにクロスレコメンドと契約しているポータルサイトからのリンクが１つしか出てこない場合が多いからである。(gooからのリンクだけバックリンクとして表示されている場合が多い、ただし実際にクラスタリングされているかどうかはイマイチよくわからない）、YSTに関しては今のところそのような節は見当たらないが、ヤフーディレクトリ側としてはクロスレコメンドは競合サービスといえるのでヤフーディレクトリに登録するよりクロスレコメンドに登録した方がYSTに効果があるなんて事になっては絶対にいけない。だからYSTのアルゴリズムを近々変更してクラスタリング機能を強化してくる可能性は大いにあり得る話だと思う。
　その他のSEO効果が減少する要素としてはリンク集サイトのSEO価値の低下、ディレクトリサービスが始まってから経た年月が少ない（２００６年サービス開始、検索エンジンは昔からあるサイトを重視する傾向がある）ということなどが挙げられる。まあこれは最初のクラスタリングに比べたらあまり重要な要素ではないが。
　で、結局総合して考えてクロスレコメンドの効果はどうなんだって事なんですけどグーグルの検索エンジンに対しては割と大きな効果が期待できそうです。クラスタリングに引っかかるとしてもページランクの値の配分に関してはクラスタリングとは何の関係もないです。クラスタリングで他の要因がマイナスになるんでしょうけどそれでもYahooディレクトリに登録するよりはクロスレコメンドに登録したほうが効果が高いと思います。またYSTに関してですけど、こちらはヤフーディレクトリへの登録よりは効果が薄い気はしますがYSTはポータルサイトからのリンクを重視する傾向があるのでそれなりには効果が望めそうです。下手すればヤフーディレクトリを上回る効果が得られるかもしれません（まあ後々上回らないように手を打たれるような気もしますがｗ）
　まあ複数の大手ポータルサイトがそれぞれ独自にディレクトリを作っていたと仮定してそれに全部登録するよりはSEO効果が薄いけれどもそれなりのSEO効果は十分に望めるのではないかというのが私の見解です。審査もヤフーと比べれば優しく値段も安いので試しにクロスレコメンドに登録してみたらどうかと思います。

　

検索連動広告の掲載順位の決定法など・・ Predicting Clicks

今回の話は検索エンジンの検索連動広告についてである。どの広告をどの順番で表示すれば検索エンジン側の収益の最大化、ユーザの満足度の向上が図れるかという問題についてが書かれてある。クリック率が分かっているならば話は早いのであるが新しい広告に対してはクリック率は過去のデータがないのでわからない。そこで新しい広告に対するクリック率を様々な手法を用いて推定してやるというのが本論文の核となるところである。ちなみにこれはマイクロソフトからの研究発表であるがビジネス要素が強いこのような研究を表に出してもいいのか？と疑問が残る・・・まあ取り合えず貴重な論文ということで・・・邦訳・要約しておいたのでブログに載せときます。論文の詳細はhttp://delivery.acm.org/10.1145/1250000/1242643/p521-richardson.pdf?key1=1242643&key2=0763889911&coll=GUIDE&dl=GUIDE&CFID=49087471&CFTOKEN=54138199です。具体的な表や計算式はこちらを参照願います。またまた図や式が汚くて申し訳ないです。ワードからグーグルdocに移してそこからブログに投稿しているので汚くなるわけです。もう少し互換性をどうにかして欲しいものです。ちなみに検索連動広告を考えている人に一言いっておくと、この論文のような内容が既に検索エンジン側で実装しているとしたら、たとえ個人運営のサイトが大手の会社より多くのクリック単価を払ったとしても大手より検索順位が低くなってしまう事がかなりありそうです。クオリティの低いサイトはお金を払っても認めてもらえないということですね、頑張ってコンテンツの充実などを図りましょう！

１．イントロダクション

ほとんどの主要な検索エンジン会社は今日検索結果の隣に配置されるテキスト広告によって利益を得ている。これはクリックがユーザによってされる度に料金が広告主から検索エンジン会社へ支払われるという仕組みをとっている。このモデルをクリック単価型成果主義と呼ぶ。検索エンジン側の収入とユーザの満足度を最大にするためには、システムがそれぞれの広告に対するユーザの挙動を予測して、可能な限りユーザにクリックを促さなければならない。サーチエンジンは過去に広告がクリックされたかでユーザの挙動を予測することができる。例えば100回広告が表示されてクリックが5回されたならば、その広告のCTR(click-through rate)は０．０５と推測することができる。しかしこの予測は新しい広告が入ってきた場合、すなわち過去のデータが利用できない場合は使うことができないという問題がある。

この論文では、私たちは新しく作られた広告がクリックされる可能性を予測する。我々は広告それ自体（広告の長さ、使用されている単語）、広告が指し示すページ、関連する広告の統計情報などを用いて新しい広告の将来的なCTRを合理的に予想する。

２．モチベーション

検索エンジン広告システムの主要な仕事は、サーチエンジンが受け取ったそれぞれのクエリに対してどんな広告を表示するかと、その順番をどうするかを決定することである。大抵広告主は広告が現れる状況をクエリ指定などにより既に指定してしまっているのでサーチエンジン側はマッチした広告を減らすことさえ考えれば良い。

　ユーザが広告をクリックする確率は広告の表示位置によって大きく変わってしまうので、サーチエンジンにとって最も効果的な広告を最も目立つ位置に持ってくることが収入増を考える上で非常に重要な要素になる。しかも広告数が増加傾向にあり、与えられたクエリに対して適合する広告の数は効果的な広告表示枠の数を大きく上回ってしまうことが多くさらに広告の表示位置決定は重要さを増してきている。

　広告の質（ユーザのクリックによって計測される）と総収益を最大にするためにほとんどの検索エンジンは期待収益（クリック率とクリック単価の積）の順に広告を並べ替えている。例外としてYahooはクリック単価の順番のみで並び替えているが今後期待収益の順に並び替びかえる事を検討している。それゆえ理想的な広告の並び替えを実現するには広告のクリック率を推定することが必要となる。

　表示回数が多い広告ではクリック率は単純にクリック数を表示回数で割ったものと推測できる。ところが広告のクリック率は基本的にかなり低い（２．６％程度）ため推定の誤差が非常に大きくなってしまう。例えば真のクリック率が５％であるとして８５％の信頼区間でクリック率が４％～６％だと判断するには１０００回広告が表示されなければならない。

不正確な広告掲載順位のランキングはユーザと広告主の満足度を低下させ、収益もダウンする。それゆえ新しくて広告表示回数が少ない広告に対して我々は過去履歴を見る以外の手段でクリック率を予測する方法を発見しなければならない。新しい広告や広告主のために広告がクリックされる確率推定することがこの論文で述べられるシステムの目的である。

　先行研究としてRegelsonとFain[19]が同じ入札語や同じトピックのクラスタによって新しい広告のクリック率を推定するというものがある。しかし我々の経験上同じ語であっても広告のパフォーマンスは大きく異なると言う事を知っている。このことを説明するために入札語以外の特徴を取り入れて考える必要がある。後述するが我々のモデルではそのような特徴を自然な形で取り入れている。

３．検索広告の骨組み

広告がクリックされるには

1. ユーザが広告を見る

2. ユーザが広告をクリックする

の２つの段階を経る必要がある。ここでユーザが広告を見るかどうかは広告の掲載位置のみに依存し、見られた上で広告がクリックされるかは広告の掲載位置に依存しないと仮定すると、あるポジションである広告がクリックされる確率は次のように表される。

ここでCTRをと定義する。

CTRとの減衰曲線からすべての場所での広告のクリック率を推定することができる。

　何度も表示された広告に対しては簡単にCTRを予測することができる。

広告が見られた回数＝広告がクリックされた回数＋クリックはされていないが見られたと思われる回数であり、広告掲載位置ごとの広告が見られる確率は実験で調べることができ、クリックされていないが見られたと思われる回数は推定することができる。最後にクリック数を広告が見られた回数で割るとCTRを求める事が出来る。

　我々の目的は新しい広告に対してこのCTRを予測することである。次のセクションではモデルの学習・テスト用のデータについて述べて、その後モデルの詳細について述べていく。

4. データセット

我々はマイクロソフトのサーチエンジンで実際に使われている広告についての情報を集めた。それぞれの広告には以下の情報が含まれている。

• Landing page：クリック先のURLの情報

• Bid term(“keywords”):広告が表示されるのに必要なクエリ（広告主が事前に入力しておく）

• Title:広告のタイトル

• Body:広告についてのテキストの説明

• Display URL:広告下に表示されるURL

• Clicks:広告が何度クリックされたか

• Views:広告が何度閲覧されたか（第３章で述べた仮定を用いる、広告の表示回数ではなく、閲覧回数は表示回数に広告掲載位置による減衰係数を掛けたものになる。）

広告主は１万、５０万を超えるキーワードに対して広告の数は１００万以上、１０万を超える広告のテキスト

トレーニングセットとして広告主の７０％、検証用として広告主の１０％、テスト用として広告主の２０％を選んだ。

広告のViewがあまりに少ないと実験で求めたCTRと真のCTRがかなりずれてしまうのでViewが１００以下の広告は除くことにした。（トレーニングセットで学習するにあたりView数が大きい方がCTRの予測精度はノイズが少なくなるため良いが、一定のView数を獲得できなかった広告を排除してしまうため偏ったデータとなってしまう。そこでバランスを考えて100という数字を設定した。）

4. モデル

我々はCTRを予測するためにロジスティック回帰を使うことを考える。ロジスティック回帰は値を０～１の間で予測するため本質的に確率の問題に適している。

　

（モデルのここからははっきり言って良くわからない取り合えず様々なツールを使い、情報を精度が出やすいように正規化している）

ここでは広告のi番目の特徴の値であり、は特徴の学習した重みである。

特徴はある単語が含まれているかどうかやタイトル中の単語の数などであるが詳しくは後述する。

ロジスティック回帰はL-BFGS手法[16]を用いて訓練された。我々はゼロ平均ガウス重みを用いてクロスエントロピー損失関数を使い最適な標準偏差σの値を求めた。（よくわからない）最適なσの値は検証セットからσ＝０．１であった。よく行われることだが我々はいつも１にセットされるようなバイアス特徴を加えた。

それぞれの特徴に対して我々はの生成された特徴と、を加えた。１を加えた理由は最低の値を０にするためである、我々は特徴をゼロ平均になり、単位標準偏差を持つように正規化した。異常値を持つ特徴もあったので、偏差値５５以上のものは５５、偏差値４５以下のものは４５となるように調整した。これらの調整により制度の向上が見られた。

　我々の計測方法は、モデルにより予測されたCTRと真のCTRのKL-divergenceをとるというものである（KL-divergenceは低いほうが良い）。この場合KL-divergenceは一回の広告のビューの結果をエンコードするために必要となるビット数を示している。我々のベースラインモデルは単純にトレーニングセットの平均のCTRを予測することである。（トレーニングセットのCTRの平均　＝　テストセットの広告のCTR　とする？）

4. 入札語のCTRの予測

全体の平均のCTRとある入札語のCTRの間にはかなりの差異がある。よって広告のCTRを予測するに当たって、他の同じ入札語、あるいは関連した語のCTRを用いるのが有効である。

6.1 語のCTR

最初の特徴は、同じ入札語の他の広告のCTRである。これをトレーニングセットの広告の平均とうまく組み合わせると次のような式になる。

ここではある入札語を与えている広告主の数ではそれらの広告の平均のCTRである。またはすべてのトレーニングセットの平均のCTRを表している。

我々はロジスティック回帰に（の事だと思う）も特徴として加えた。この２つの特徴をTerm CTR feature setと呼ぶことにする。結果はテーブル１のようになり、誤差を１３％減らすことが出来た。

2. 関連語のCTR

RegelsonとFain[19]の場合と同様に、ある広告の入札語と関連した入札語を持つ広告のを利用したい。そこで入札語の部分集合と上位集合を考える。広告集合を考える、広告の入札語をtとすると、tにm語付け加えたものをと表し、tからn語を取り除いたものをと表し、t からm語付け加えてn語取り除いたものをと表す、これらの集合の総数はで与えられる。ここでこれらの集合のCTRの平均値を次の式により取る

これが関連広告の平均クリック率となり、6.1のをで置き換えて同様の計算をしたところさらに６％の精度の向上が見られた。

4. 広告の質を予測する

前章ではCTRを入札した語だけに基づいて推測したが、それだけでは十分ではなく、入札語が同じでも図３のようにCTRにはかなりの差が生じていることが分かる。そこでこの章

では広告そのものの特徴がよりよいCTRの予測に使えるのかを試したい。そこで広告をクリックするかどうかの判定基準となるような要因を考えてみた。その結果次のようなものが挙がった。

Appearance	広告が審美的に喜ばしいか	title,body内のの単語数、効果的に大文字を取り入れているか？、エクスクラメーションが多すぎないかなど
Attention Capture	広告がユーザを引き込むかどうか	title,body内にbuy,join, subscribeなど行動を示す言葉が入っているか、値段が書かれているかなど
Reputation	広告主が知られているか？または有名なブランドであるか？	ファーストドメイン(.comなど)、ドメイン長、セグメント数(books.comだと２セグント,books.something.comだと３セグメント)、短くて良い.comドメインは広告主が大きくて一流である場合が多い
Landing page quality	クリック先のページの質	フラッシュを含んでいるか、イメージの割合、W３Cの規定を遵守しているか、スタイルシートを使っているか、広告で覆われていないかなど
Relevance	どれだけ検索クエリが広告と関連しているか	入札語がtitleに現れるか？bodyに現れるか、bodyに現れるならその割合は？

全部で８１の特徴を５つのカテゴリから挙げた。

我々はユニグラムの特徴も加えた。広告のトレーニングセットのtitleとbody中で最も使用頻度が高い１００００の語に対して、語が存在したら１の値を、存在しなければ０の値をつけた。これらの特徴は我々が手動でとった特徴の機械版を意図している。これにより我々が発見できなかったような特徴もカバーできるかもしれない。

この結果さらに４％精度が向上した。しかしユニグラムの特徴を使わない場合わずか１％しか精度が向上しなかったのが驚きであった。

4. 命令の詳細さを計測

例えば

Title: Buy shoes now,

Text: Shop at our discount shoe warehouse!

Url: shoes.com

Terms:{buy shoes,shoe,cheap shoes}

というように広告主が命令を与えておくと、広告主は靴を買いに来る人のみを限定的に狙っているということになる。ところが

Title:Buy [term] now,

Text: Shop at our discount warehouse!

Url:store.com

Terms:{shoe,TVs,grass,paint}

と命令を与えるとより広い層の顧客をターゲットしていることになる。ターゲットの絞込みが弱いともいえる。そしてターゲットの絞込みが弱いとCTRも下がってしまうのではないかと我々は考えているのでこれを実証してみる。

ターゲットの広さを測るために、我々は語のカテゴリーエントロピーを計測することにする。方法はまずTermsの語をWebサーチにかけ、その結果得られるスニペットをテキスト分類アルゴリズムにかけることでそれぞれの語を７４のカテゴリーに分類する。そのあと入札語のカテゴリの分布のエントロピーを測り、それを特徴として用いる。我々は入札語の個数も特徴として加えた。エントロピーの特徴と入札語の数の特徴は命令の特異性を扱ったものである。この結果はテーブル３のようになりさらに５．５％程度精度が向上した。

９. データの外部ソースの利用

さらに広告が持つデータ以外のデータを使って２つの特徴を加える。検索ヒット件数と検索回数である。我々は検索回数とCTRの関係を発見した。この関係は図５のようになる。図５より検索回数の多い語はクリック率が高いことが分かる。これらの特徴を考慮して実験したところテーブル４のようになった。ベースラインからだと３％精度が向上したにも関わらず、前章までの組み合わせで実験すると０．５％しか制度が上昇しなかった。これは前章までの特徴の何かと今回の特徴とがオーバーラップしているからである。

１０　結果の討論

10.1 特徴の有用性

それぞれの特徴セットを独立してCTRの予測に用いると、どの特徴がより予測に有効なのか興味が出るところである。そこでそれぞれの特徴セットを独立に計測してKL-divergenceをとったところ広告の質が１２％（人手でつけた特長とユニグラムの特徴、ユニグラムだけだと１０．２％）でエントロピーの特徴が８．９％でサーチデータのセット（検索回数とヒット件数）が３．１％であった。

ロジスティック回帰モデルなので、我々はそれぞれの特徴の重みを知ることができる。その結果はテーブル５のようになった。

ユニグラムの特徴はテーブル６のようになった。これによるとofficialなどがトップに上がってきていることから、ユーザはより権威ある、一流のサイトを好んでクリックする傾向があるといえる。またquotes（見積もり）,trial（試用）,compareなどより限定的なユーザをつかむような単語が使われている場合のクリック率は低くなった。

それぞれの特徴の有用性をつかむのも面白いが、最も実用的なことはできる限り最終的なモデルに多くの特徴を含ませる事である。これによりどんな広告に対しても的確に予測できるようになるのである。

１０．２　初期化後の進化？

我々のモデルはCTRをいくらか正確に予測することができるが、いったいどれくらいのViewがあればCTRが十分に推測できるのであろうか？ベースラインモデルと特徴を用いたモデルの、Viewの数とCTRの誤差の関係を表したグラフは図６のようになる。これによると１００回のView、表示回数に換算すると約２００～３００回の表示でベースラインモデルの誤差と特徴を用いたモデルの誤差が同じになることが分かる。特徴を用いたモデルは１００回Viewがあるまでの期間でうまく作用し、収益増をもたらしてくれる事が分かる。

１０．３　より多くのViewを持った広告

よりView数を多く持った広告をトレーニングセット、テストセットに選びCTRの予想に用いるとより正確なCTRを予測できる。よって１０００Viewを超えた広告のみをトレーニングセット、テストセットに選び同様の実験を行ったところテーブル７のような結果が得られ精度が向上した。しかし１０００Viewを超えるような広告は優良な広告が多くデータにかなりバイアスがかかってしまっている。

１１　将来への考察・展望

• この分野の研究があまりなされていないので、誰でも研究、比較できるように標準となるデータセットが必要である。

• 将来的にはユーザのクエリ情報を用いて、ユーザのクエリと入札語が完全に等しい場合、緩く当てはまる場合などを考慮する必要がある。（緩い例：広告主がパソコンという語が入ったクエリに対して広告を表示するという条件を与えておくと、“パソコン”というクエリ以外にも“中古パソコン”、“パソコン修理”といったクエリに対しても広告が表示される。）例えばクエリと入札語の類似度などを特徴として用いれば、今回のモデルをそのまま適用することができる。

• RegelsonとFain[19]の手法を追加の特徴として取り入れて我々の手法と比較してみたい。

• 実際に実用化させるにあたっては、CTRの予測を広告の表示順位を決めるために使う以外に、広告主にCTRを向上させるアドバイスを与えるために使いたい。

• その他、人による直感的な判断、広告サイトへの再訪問率、滞在時間、またデータを蓄積することで得られる広告主の質などを特徴として加え、さらなる精度の向上を図りたい。
  

最新のSEO関連研究 コンテンツスパムの発見法

検索エンジンのコンテンツに関してスパムにならないようにはどうしたら良いか、キーワードが５％が最適とか言っている前に最新の論文を読んだほうが良いだろう。ということでWorld Wide Web Conference2006からそれに該当する論文を読んで要約してみた、これを理解すればどのような行為がスパムになるのかが良くわかるはずである。SEO業者も必見かと思います。

論文はこちら　このグラフはこの論文中のものを指しています。 また計算式がみにくいですけどこれも論文中のものを見てもらえれば助かります。

Detecting Spam Web Pages through Content Analysis

1. Introduction

サイトのクオリティを高める努力をせずに検索エンジンのランキングを外部リンクや人気キーワードのサイトへの埋め込みなどによって不正に上昇させるような行為を検索エンジンスパムという。英語のサイトの１３．８％はスパムサイトであるといわれているがこれを看破できないサーチエンジンはリソースの約7分の１を浪費してしまい、更にはサーチエンジンのクオリティの低下でユーザが離れてしまうのでどうにかしなければならない。

これらを防ぐために

1. Webの大きさを考ると人手を介さず自動でスパムサイトを発見しなければならない

2. 正統な（スパムでない）サイトをスパムとみなしてはいけない。

3. クエリーをユーザーが投げる前にはスパムを発見したい（そうすることで無駄なロボット巡回、クエリー処理、インデキシングを省くことができリソースを有効活用できる。）

この論文で我々はスパムを発見する様々な方法、また効率、精度よくスパムサイトを発見するアルゴリズムを作るために、如何に個々の方法を統合する機械学習技術を使ったかを示す。

この論文の構成は次のようになる

§２：実験概要、実世界データセットの紹介

§３：データセット中のスパムの蔓延度合いをドメイン、言語別で比較

§４：スパムの発見する方法を説明

§５：我々の手法の評価

§６：関連研究

§７：結論と将来への展望

２．実験概要とデータセット

データセット：MSNサーチエンジンが収集したサイトデータから105,484,446(約１億)のページをランダムで取ってきたもの。

厳密にはMSNサーチが取り込むデータ自体もスパム排除プログラムを潜り抜けたものであるからランダムとは言えないが。しかし実際にユーザが目にするのはそのようなサイトであるし、我々の実験で得られた結果も、真の意味でランダムでとってきたのよりも悪くなるはずなので控えめな見積もりということができるので十分にこの論文の価値はあるといえる。

3. どれくらいスパムがあるの？

この章では、どれくらいスパムがWeb上に蔓延しているのかと、トップドメイン名、国などで区切った時あるページの集合が他のページの集合に比べてどれくらいスパムが多いのかを調べていく。Figure2はどのトップレベルドメインにスパムが多いかを調べた結果であり、Figure3は言語によるスパムサイトの割合である。この二つの実験からスパムはかなりの割合でWebに蔓延しており、また特定のドメインはスパムだらけである。これらの調査はスパム発見手法に生かしていく。

3. 内容に基づいたスパムの発見

我々のWebDBの論文[8]で、我々はスパムの発見手法を数多く説明したが、その中には完全にページの内容と独立したものもある。（リンク構造やDNSレコードを使ったもの）また一方で内容が解釈されていないもの（ページの進化状況、（構造的に？）似たようなものをクラスタリングする）もある。

　この論文では、我々は全てコンテンツに基づいたスパム判定を行う。

　我々は1億のデータから最も多数ある（５４％）英語のページをランダムで１７１６８ページ取得してそのそれぞれに対して人手でスパムページかそうでないかを仕分けした。そのうち１３．８％がスパムページで８６．２％がスパムページでなかった。この章の残りで我々が研究したコンテンツに基づくスパム発見手法を詳細に説明していく。

1. ページ中の単語数

スパムページは人気キーワードをとかく詰め込む傾向があるので、過剰な数の単語がスパムの指標になるのかを調べ、その結果は図４のようになった。確かにページ数が多いほどスパムの割合は高くなるが全ての範囲でスパム率は５０％を切っているのでこれだけでスパムかどうかを判定するわけにはいかない。

2. ページタイトル中の単語の数

スパムの常套手段のもう一つとしてページタイトル中に単語を詰め込むというものがある。そこで我々はページタイトルに含まれる単語数とスパムの関係を調べ、その結果は図５のようになった。図４と図５を比べると図5のページタイトルに含まれる単語数の方がスパムを判断する上で良い指標となるといえる。

3. 単語の平均の長さ

クエリを複数語を指定して投げる時にスペースを入れない人がいるのでそれを狙って単語をつなげているページがある。例えば”freepicture”,”freemp3”などなど。そこで単語の平均アルファベット数とスパムの関係を調べてみたところ図６のようになった。単語の長さが８文字をすぎるとかなりスパムの割合が高くなることがわかる。

4. アンカーテキストの量

リンクはアンカーテキストとなっているが、単に他のページにリンクの渡すためだけのカタログページが存在する。そのようなサイトは大量の初リンクがあるのでアンカーテキストの単語が全単語に占める割合とスパムとの関係を調べた。その結果図７のようになった。ややアンカーテキストの割合が高いほどスパムの確率は上昇するがあまり顕著ではなかった。

5. 見えているコンテンツの割合

マークアップでない単語の総バイトをページの総バイト数で割ったところ図８のようになった。これからスパムページはマークアップ（スクリプトやスタイルシートなども含む）が普通のサイトより少なく人にサイトを見せるための装飾等を省いているといえる。

6. 圧縮率

冗長なコンテンツがあるページは圧縮器をかけることによりサイズを縮小できる。例えば同じ単語が何度も使われていたりすると圧縮率は高くなる。そこでGZIP[14]という圧縮器を使って圧縮率とスパムの関係を調査して、その結果が図９のようになった。　

7. ページ中で一般的に良く使われる単語が含まれる割合

スパムページは検索エンジン対策のため文章が不自然になっている可能性があるので、データセットで上位２００位までの頻出単語が全文章中でどれくらいの割合で使われているのかを調べ、それとスパムとの相関を図１０に示した。この結果スパムページは一般的に使われている単語をあまり使っておらず偏りがあることがわかる。

8. 一般的に良く使われる単語の割合

データセットで上位５００位までの頻出単語のうち何種類がページ中に含まれているかを求めスパムとの相関を調べた。４．７の場合例えばページ中に”a”とだけ書かれた文字があったとするとスコアは１となるが４．８の場合は1/500となる。うまく４．７の欠点を補う意味で調査をした。その結果図１１のようになったが全体的に控えめな結果となった。

9. 独立したN-gramの可能性

スパムページは文法的におかしい傾向が強いためn-gramにより文書の傾向を調べた。理想的には文法的かつ意味的に正確さを追求したいのだが、計算量が多くなるため統計的な手法であるn-gramを用いることにした。

という式でまずあるn-gramの発生率を求める。分母はngram全体の数、例えばngramはオーバーラッピングするので3gramで5個単語があるとすれば最初の３つ、真ん中の３つ、最後の３つで合計total number of ngram =　3　となる。分子はこれら３つの重複数で最初、真ん中、最後の全てが異なる場合１となるし、最初と最後が同じで真ん中が異なると最初と最後の値が２となり真ん中が１となる。

この式から文書全体のn-gramの発生率のようなもの（文書中にはk個のn-gramを持った文書の確率は個々のPの確率の積であると書かれているがまったく理解できない）を取り、それを文書の長さによる差がでないように正規化すると

となる、これをコンピュータの誤差が出にくいようにさらに変形して

とする。この式からわかることはngramで共起する回数が少ないほどlogPの値が小さくなる、すなわち負の値が大きくなるためIndepLHの値が大きくなる。また逆にngramで共起回数が多いほどlogPの値が大きくなり、すなわち負の値が小さくなるためIndepLHの値は小さくなるということである。（これ以上は理解不能）

図１２はこのIndepLHの値とスパムとの関係である。極端にngramでの共起が少ないときと多いところにスパムが集まっている。共起が多いときは同じ表現を繰り返し何度も使っているスパムであると判断できる、また（グラフのどこからその根拠を得ているのかは不明だが）起こりそうにないngramで構成されている文書はよりスパムである確率が高い、おそらく文法的にありえない文書を使っているからであろう。

４．１０　条件付ngramの可能性

と条件付確率を定義するとより計算量が増えるかわりに精度が上がるらしい。（どう、または精度が向上するのかはよくわからないがとにかくより良い手法らしい）そして後は４．９と同じようにして計算してスパムとの関係を調べると図１３のようになった。大体図１２とライングラフが一致している。（結局あまり大差ないやん）。

５．今までのデータを組み合わせて分類器の生成

今までのデータを用いて分類器を生成して、ページがスパムであるかスパムでないのかを求めた。これを行う技術としては決定木、ルールベース技術、ニューラルネット、サポートベクターマシンを使った。そのうちで最も分類精度が良かったのは決定木のC4.5というアルゴリズムである。C4.5は簡単に説明すると最も分類精度が高い順にルートから木を生成していくというアルゴリズムである。分類例は図１４のようになり、再現率と精度はテーブル１のようになった。

5.1　分類の正確さの改善

より分類器の正確さを上げるために我々は最も有名な2つの技術「bagging」と「boosting」を使おうと思う。

Baggingの説明

1. もとのデータセットからN個のデータセットを作る。その時各データセットはもとのデータセットからそれぞれn個のデータをランダムで選んだものとする。（それゆえデータセット間のデータの重複は許される）

2. N個のデータセットそれぞれについて分類器を作成する

3. それぞれの分類器を使ってスパムかスパムでないかを判別する。

4. 最終的な結果は分類器の多数決によって決める。

これがBaggingの概要であるが今回はN=10,n=15453で実験して行ってみたところ結果は表２のようになり正確さは上昇した。

Boostingの説明

1. 最初に全てのデータに1/nの重みを割り当てる（今回の場合n=15453）この重みはトレーニングセットの中で一つデータを取り出した時に該当するデータである確率である。

2. この重みを使って分類器を生成する

3. 分類した際にスパム・ノンスパムの分類を間違えたデータは重みを増やし、正解したデータは重みを減らす（つまり学習例として適しているデータの重みを増やすってことだとは思う）

4. ２．３を繰り返す（今回の場合10回）

5. １０個分類器ができるのでスパム・ノンスパムの判定は重み付投票で決める。

これにより分類してみたところ結果は表３のようになりかなり改善が見られた。

６．RELATED WORK

1. 機械学習の関連研究

C4.5を使ったEmailの分類[16,28]
これは人が読むものに対するスパムだが我々は検索エンジンのロボットが読むためのスパムを発見するという意味で異なる。

2. スパムの役割やシステムについて

   • Henzingerら[15]はスパムがサーチエンジンにもたらす脅威を認めた

   • Perkins[25]が数多くのスパムテクニックを定義しGyongyiとGarciaMolina[13]がよりそれを詳細に分割した。

   • DeStefano[20]はWebスパムと宣伝の関係を指摘(調べてみたらあるサイトのリンクポピュラリティを故意に上げよう（あるサイトを宣伝しよう）とした時に現れるリンク構造を発見したみたいな内容であった)

スパム手法は一般的にリンクスパム、内容スパム、クローキングに大別できる

3. リンクスパムについて

• Davison[7]は早い時期にリンクスパムについて調査しており、縁故主義のリンクについて考察している

• Amitayら[2]はリンク構造をルールベースの分類器に入れてリンクスパムを発見する手法を提案

• Baeza-Yateら[3]はページランクを上げるために示し合わせたリンク形態の研究を示し、Adaliら[1]はあるページにリンクを張るためのみにページを生成することが最も効率的なスパムの手段である事を示した。（今では古いと思うが）

• Zhang[31]らはどうやってページランクを攻撃（スパム）に耐えられるものにするかを示した

• Gyongyiら[11]は信頼の置けるサイトからのリンクを辿ることによるTrustRankというものをスパムでないページの発見のために用いた。

• Benzur[4]らは不自然にページランクを上昇させているページに対してどうペナルティーを与えるのかについて示した。

• Wu と Davison[29]とGyongyi と　Garcia-Molina[12]はリンクファームの発見手法について研究した。

• [8]で我々はリンクスパムを指数法則からの逸脱をもとに発見する方法を示した。

• Mishneら[21]らはブログのコメントにあるリンクスパムを発見するために単語の使用頻度を用いた確率的な手法を提案した。

４．　コンテンツスパム　

• [8]で我々は長いホスト名、多くのダッシュやドット、数字が入っている、単語に多様性がない、頻繁に広範囲にわたってコンテンツを修正する、ということがスパムであるかどうかの良い指標になることが多いということを示した。

• [9]で我々は切り取りと貼り付けで作ったようなサイトのスパムを調査して、そのようなページを発見する方法を提案した。

3. クローキング
   クローキングとはWebサーバに細工をして検索エンジンの巡回ロボットに一般の閲覧者とは異なる内容のWebページを見せる事を言う。（フラッシュ等を多用しているサイトでは検索エンジンとの親和性が低いためそれをカバーするため最適化したHTML構造を巡回ロボットに見せるというパターンが多い）

   • GyongyiとMolina[13]は現在のクローキングテクニックを示した。

   • WuとDavison[30]は３つの別々のページに共通する単語を計算することに基づいたクローキングの発見方法の有効性を示した。（意味不明）注目すべきはクローキングが有益なものを使うということである。例えば帯域幅やストレージコストを減らすためにサーチエンジンに対してクローキングがマークアップなしでページのコピーを返すような感じである。（サーチエンジンに有用な部分だけを見せるということだと思う）

７．結論と先への展望
Webスパムと検索エンジンのいたちごっこは続いていくであろうが我々の技術がより良い検索のために役立てばうれしいと思う。継続的な研究により効果的なスパムを行うよりもコンテンツ作りを充実させたほうがよりリスクが少ないようになるのが我々の願いである。

ここが変だよGoogle翻訳

GoogleにはGoogle翻訳というサービスがある。http://www.google.co.jp/translate_t?langpair=jaenこれは文法をきちきちと解釈して訳をつくっているのではなく、日本語文書とそれに対応する英語文書があれば、対応関係などを大量に学習して自動的に適切な訳を出してくれる機械学習を用いている。
その性能は非常に高く、別に暇な人が対応表みたいなものをつくったわけでもないのに「千と千尋の神隠し」と入れるとSpirited Awayと返すし、「バイオハザード」と入れるとRezident Evilと、固有名詞までしっかりと学習している。
ところが・・・・「JOJOの奇妙な冒険」と入力すると
WRYYY
とか返してきた。これはJOJOの最大の敵であるDIOの有名な奇声のことなのだが一体何をどう学習すればWRYYYになるのか見当もつきません。Googleなりのギャグととらえるべきでしょうか？
他にも「ニューガンダムは伊達じゃない」とかガンダムの名言でも入れてみるとKiwi is not NYUGANDAMU（ニュージーランド人はガンダムではない）とか返してきた。
今後もGoogleからは目が離せません！