マルコフ連鎖とは
マルコフ連鎖は未来の挙動が現在の値だけで決定され、過去の挙動と無関係であることを利用した確率統計モデルです。定義としては次のような形を取ります。
マルコフ連鎖は、一連の確率変数 X1, X2, X3, … で、現在の状態が決まっていれば、過去および未来の状態は独立であるものである。形式的には、
であるような過程をいう。一般の、時間的に均一でないマルコフ連鎖は、この等式を満たさない。(Wikipedia:「マルコフ連鎖」より)
はい、難しい数式が出てきましたね。私もこの中身は完全には理解していません。しかし、このマルコフ連鎖を使うと、現在のデータを一定の出現率で並び替えるアルゴリズムを作成することも可能という事を憶えておいてください。実はGoogleのページランクアルゴリズムなどにもマルコフモデルが応用されています。
日本語形態素解析とは
日本語は単語と助詞を中心に、日本独自の文法ルールに従って文章が構成されています。中学校の時に、国語の授業で文節分けとかをやりましたよね。あのような作業をコンピュータ(サーバー)に行わせるのは少し厄介です(コンピュターに日本語の単語と文法を教えなければならないので)。
このコンピュータに日本語の文章の構造を解析させることを日本語形態素解析といいます。最近では、辞書とアルゴリズムを使って日本語形態素解析を比較的簡単に実現する方法が、オープンソースやWEB API(Yahoo日本語形態素解析APIなど)で多数提供されています。
Mecabとは
オープンソースの日本語形態素解析エンジンにMecabがあります。Mecabは、 京都大学情報学研究科−日本電信電話株式会社コミュニケーション科学基礎研究所共同研究ユニットプロジェクトで開発されたオープンソースの形態素解析エンジンです。他の日本語形態素解析エンジンと違い、辞書に依存しない汎用的な設計が特徴で、解析モデルにbi-gramマルコフモデルを使っています。このため今まで日本語形態素解析の主流であったKAKASIやChaSenに比べて扱いやすく、精度も高いです。もちろん、辞書をインストールすることもできます。
Mecabのインストールは簡単です。
wget http://mecab.googlecode.com/files/mecab-0.996.tar.gz
tar -zxvf mecab-0.996.tar.gz
cd mecab-0.996/
./configure --with-charset=utf8
make
sudo make install
これでインストールは完了です。IPA辞書もインストールしておきましょう。
wget http://mecab.googlecode.com/files/mecab-ipadic-2.7.0-20070801.tar.gz
tar zxvf mecab-ipadic-2.7.0-20070801.tar.gz
cd mecab-ipadic-2.7.0-20070801
./configure --with-charset=utf8
make
sudo make install
sudo ldconfig
sudo /sbin/ldconfig
64bitの場合は、/usr/local/etc/mecabrcを次のように編集します。
dicdir = /usr/local/lib64/mecab/dic/ipadic
これでインストールは完了です。さっそくmecabでテストしてみましょう。mecabとコマンドを叩いて、「すもももももももものうち」(李も桃も桃のうち)と打ち込んでみます。
mecab
すもももももももものうち
すもも 名詞,一般,*,*,*,*,すもも,スモモ,スモモ
も 助詞,係助詞,*,*,*,*,も,モ,モ
もも 名詞,一般,*,*,*,*,もも,モモ,モモ
も 助詞,係助詞,*,*,*,*,も,モ,モ
もも 名詞,一般,*,*,*,*,もも,モモ,モモ
の 助詞,連体化,*,*,*,*,の,ノ,ノ
うち 名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ
EOS
正常に日本語形態素解析できました。丁寧に品詞の種類まで出力されます。
マルコフ連鎖と日本語形態素解析の組み合わせ
Mecabのインストールでサーバー設定は完了です。次はスクリプトです。
PHPで簡単にマルコフ連鎖とMecabによる日本語形態素解析を実装されている方がいます。以下のサイトのソースをご参照ください(Mecabコマンドを呼び出して、形態素解析し、マルコフ連鎖で並び替えるクラスを用意しています)。
今回このPHPを使って、以下の文章をマルコフ連鎖で並び替えてみます(下記の文章は私が大学1年生の時、東京大学総長杯争奪弁論大会に出た時の、「アジアの世紀」という青臭い文章です)。
伝統の発見のためには、アジアの大衆に根ざした学術体系が必要です。アジア各国は、アジアの政治学、経済学、歴史学、文化人類学などの諸分野を統合したアジア歴史政策学の確立を急ぐとともに、大衆レベルでのアジア的価値観の議論が可能となるようにするべきです。さらに、それがアジアの唯我独尊に陥らないよう、欧米近代の普遍的部分やアジアの欠点を素直に認め、より高度で現実的な学術体系を築いていく必要があります。そして、以上の過程を経て完成した現代版アジア的価値観を、今の政治システムの中に、各国が協調して段階的に取り入れていくのです。
アジアは、世界で最も古い歴史と伝統を持ち、常に世界に貢献しうる思想や政治システムを生み出してきました。近代世界システムで病んだ世界を建て直す。私はこれこそが今のアジアに課せられた、古く、そして新しい使命であり、その方向へ総力を傾ければ、必ずや21世紀はアジアの世紀になるであろうと思います。経済成長という一面的な変化でのみアジアの世紀が語られてきたことを反省し、新たな方面からアジアが次世紀をリードできる可能性が高いことを再度指摘しつつ、弁論を終えたいと思います。ご清聴ありがとうございました。
PHPを実行した結果、以下の文章が自動生成されました。
伝統の発見のためには、アジアの政治システムの中に、各国が協調して段階的に取り入れていくのです。アジア各国は、アジアの欠点を素直に認め、より高度で現実的な変化でのみアジアの大衆に根ざした学術体系を築いていくのです。さらに、それがアジアの世紀になるであろうと思います。ご清聴ありがとうございました。近代世界システムで病んだ世界を建て直す。私はこれこそが今のアジアに課せられた、古く、そして新しい使命であり、その方向へ総力を傾ければ、必ずや21世紀はアジアの政治学、歴史学、経済学、文化人類学などの諸分野を統合したアジア歴史政策学の確立を急ぐとともに、大衆レベルでのアジア的価値観を、今のアジア的価値観を、今のアジア的価値観を、今の政治学、経済学、経済学、経済学、経済学、歴史学、経済学、歴史学、経済学、歴史学、歴史学、歴史学、文化人類学などの諸分野を統合した現代版アジア的価値観の議論が可能となるようにするべきです。アジア各国は、世界で最も古い歴史と伝統を持ち、常に世界に貢献しうる思想や政治システムの中に、各国が協調して段階的に取り入れていく必要があります。そして、以上の過程を経て完成した現代版アジア的価値観の議論が可能となるようにするべきです。さらに、それがアジアの欠点を素直に認め、より高度で現実的な学術体系が必要です。さらに、それがアジアの世紀が語られてきました。近代世界システムで病んだ世界を建て直す。私はこれこそが今の政治システムの中に、各国が協調して段階的に取り入れていくのです。アジア各国は、世界で最も古い歴史と伝統を持ち、常に世界に貢献しうる思想や政治システムの中に、各国が協調して段階的に取り入れていくのです。
アジアは、アジアの欠点を素直に認め、より高度で現実的な学術体系を築いていく必要があります。そして、以上の過程を経て完成した現代版アジア的価値観を、今の政治システムを生み出してきたことを再度指摘しつつ、弁論を終えたいと思います。経済成長という一面的な学術体系を築いていく必要があります。ご清聴ありがとうございました。
オリジナルの文章を元に、微妙にちょっと違った内容の文章ができました。少し日本語としておかしな部分もありますが、全体的に正常な日本語のように見えます。単語の出現回数も違います。これが、マルコフ連鎖と日本語形態素解析を使ったダミー文章の生成です。
SEOへの応用(ワードサラダ)
オリジナルの文章を元に、さらに別な独自の文章を生成する。この手法を使って、ネット上にある膨大なテキストをクローラーなどで収集してマルコフ連鎖で並び替えれば、大量の独自のダミーテキストを自動生成することも可能です。そうすると検索エンジンではそれをコンテンツマッチ(重複)ではなくオリジナルページとして見てくれる可能性があるので、SEOで外部リンク獲得のためのダミーサイトを簡単に大量に立てることができます。たとえ、それが日本語として少しおかしくても。
XML-RPCや投稿APIを提供しているブログならば、ブログ記事としてマルコフ連鎖の文章を自動投稿させることも可能です(顧客リンク付きで)。メジャーなブログサービスからのリンクはけっこうSEO効果が高かったので、大量のブログアカウントを作って、そこに一気に色々な種類のダミーテキスト文章を投稿したこともあります。
このテクニックは、俗に「ワードサラダ」と呼ばれます。ワードサラダは、特にYahooが独自検索エンジン(YST)を使っていた時には有効でした。私はマルコフ連鎖を使って自動生成した約100万ページをYahooにインデックスさせることに成功しています。しかし、検索エンジンがGoogle一強体制になってからは、スパムサイト発見技術は日々向上しており、ワードサラダの技術は通用しなくなりつつあります(まだアルゴリズムを変えると一部は認識されるのですが)。
こんなの元々ゴミサイトですしね。ダーティーな手法でSEO目的でスパムサイトを大量生成する仕事は本当は私のポリシーに反するのでやりたくなかったのですが、仕事で沢山作ったことがあります。今となっては黒歴史ですw ネットを巡回していて、たまに日本語としておかしい文章に出くわしたら、それはSEO業界のワードサラダの残骸の可能性があります。