評価結果

図3および図4において，「ベースライン」のプロット は，従来からの素性だけを用いて訓練した分類器の性能 を示す．「+DOM系列差分(大量生成型)」のプロットは，

従来からの素性にDOM系列差分(大量生成型)素性を 追加して訓練した分類器の性能を示し，「+DOM系列差

分(ブログ)」のプロットは，従来からの素性にDOM系

列差分（ブログ）素性を追加して訓練した分類器の性能 を示す．図3および図4の(a-1)，(a-2)において，「2素

性＋DOM系列差分(ブログ)」のプロットは，ホワイト

リストURL素性，名詞句素性，DOM系列差分(ブログ) 素性を用いて訓練した分類器の性能である．一方，図3 および図4の(b-1)，(b-2)において，「2素性＋DOM系

列差分(ブログ)」のプロットは，ホワイトリストURL

素性，ブラックリストURLへのアウトリンクを持つア ンカーテキスト名詞句素性，DOM系列差分(ブログ)素 性を用いて訓練した分類器の性能である．

図3において，(a-1)および(b-1)のスプログ検出性 能においては，ベースラインからの改善は達成できてい ないが，(a-2)および(b-2)の非スプログ検出性能にお いて，DOM系列差分(大量生成型)素性を用いた場合，

ベースラインからの改善が達成できている．(a-2)にお いては，DOM系列差分(ブログ)素性についても，ベー スラインからの性能改善が達成できている．

これらの結果から，訓練データ中で大量生成型スプロ グの情報を付与すれば，未知のスプログ検出の性能を確 実に改善できることが分かる．ブログホストによっては，

大量生成型スプログの情報を付与しなくても，未知のス プログ検出の性能を改善できる場合もある．

一方，図4においては，「大量生成型スプログ」検出 性能および「単発スプログ・非スプログ」検出性能の両 方において，ベースラインからの改善が達成できてい る．また，DOM系列差分(大量生成型)素性だけでなく

DOM系列差分(ブログ)素性においても，ベースライン

からの改善が達成できている．この場合は，訓練事例中 において大量生成型スプログの情報を用いていることが その大きな理由であると考えられる¹²．

また，図3および図4を通して，「2素性＋DOM系列 差分(ブログ)」および「+DOM系列差分(ブログ)」の

12図3および図4の検出分類器のサポートベクター数は，「+DOM

系列差分(大量生成型)」および「+DOM系列差分(ブログ)素性」の

モデルは，ベースラインの4/5程度に減少していることが分かった．

これによって，サポートベクターの観点からみても，ベースラインに 比べて，「+DOM系列差分(大量生成型)」および「+DOM系列差分

(ブログ)素性」のモデルが改善していると言える．

(a-1)スプログ検出性能(CC社) (a-2)非スプログ検出性能(CC社)

(b-1) スプログ検出性能(SS社) (b-2)非スプログ検出性能(SS社)

図 3: スプログ/非スプログ検出性能

(a-1)大量生成型スプログ検出性能(CC社) (a-2)単発スプログ・非スプログ検出性能(CC社)

(b-1) 大量生成型スプログ検出性能(SS社) (b-2)単発スプログ・非スプログ検出性能(SS社)

図 4: 「大量生成型スプログ」/「単発スプログ・非スプログ」検出性能

性能の比較においては，極端に大きな差は見られない．

この結果から，DOM系列差分(ブログ)素性を用いれ ば，それ以外の従来からの素性を全て用いなくとも，従 来からの素性2種類を適切に選定さえすれば十分である ことが分かる．

以上の結果より，従来からの素性と比較して，DOM 系列差分(大量生成型)素性およびDOM系列差分(ブロ グ)素性が高い性能を示すことが確認できた．

7 ^おわりに

本論文では，同一のスパムブログ作成者が自動的に 大量生成したと推測されるスプログの検出において，

HTML構造の類似性が効果的であることを示した．機 械学習のひとつであるSVMを用いた枠組みによって，

スパムブログの判定を行うタスクを設定し，HTML構 造の類似性を素性として，SVMを用いたスプログ検出 を行った結果において，スプログ検出の性能が向上する ことを示した．本論文のDOM系列差分の定式化にお いては，例えば，木構造カーネルを用いる方式[21]等，

理論的に裏付けされた方式を採用することにより，より 汎用的な定式化が可能と考えられるため，今後検討を進 める．

大量生成したと推測されるスプログのHTML構造は 類似性があるという特徴を用いれば，訓練事例となるス プログを用意しなくても，DOM系列の差分の割合が極 端に小さいブログの組を自動収集することにより，教師 なしスプログ収集を実現できる可能性がある．現在，こ の考え方に基づいて，数百万件のブログをクロールした 結果から，スプログの候補を収集し，人手によるスプロ グ・非スプログ判定を行う作業を進めており，DOM系 列の差分の割合が極端に小さいブログの組の中にスプロ グが含まれることを確認済みである．この結果の詳細に ついては，別の機会に報告する予定である．

参考文献

[1] T. Nanno, T. Fujiki, Y. Suzuki, and M. Okumura.

Automatically collecting, monitoring, and mining Japanese weblogs. In WWW Alt. ’04: Proc. 13th WWW Conf. Alternate Track Papers & Posters, pp.

320–321, 2004.

[2] Z. Gy¨ongyi and H. Garcia-Molina. Web spam taxon-omy. InProc. 1st AIRWeb, pp. 39–47, 2005.

[3] Wikipedia, Spam blog.

http://en.wikipedia.org/wiki/Spam blog.

[4] P. Kolari, A. Joshi, and T. Finin. Characterizing the splogosphere. In Proc. 3rd Ann. Workshop on the Weblogging Ecosystem: Aggregation, Analysis and Dy-namics, 2006.

[5] C. Macdonald and I. Ounis. The TREC Blogs06 col-lection : Creating and analysing a blog test colcol-lection.

Technical Report TR-2006-224, University of Glasgow, Department of Computing Science, 2006.

[6] P. Kolari, T. Finin, and A. Joshi. Spam in blogs and social media. InTutorial at ICWSM, 2007.

[7] Y.-R. Lin, H. Sundaram, Y. Chi, J. Tatemura, and B. L. Tseng. Splog detection using self-similarity anal-ysis on blog temporal dynamics. InProc. 3rd AIRWeb, pp. 1–8, 2007.

[8] 石田和成. スパムブログの推定と抽出. 日本データベー ス学会Letters, Vol. 6, No. 4, pp. 37–40, 2008.

[9] 石田和成. 共起クラスターシードと連鎖的抽出にもとづ くスパムブログのフィルタリング. Webとデータベース に関するフォーラム(WebDB Forum)2008論文集.情報 処理学会, 2008.

[10] P. Kolari, T. Finin, and A. Joshi. SVMs for the Blo-gosphere: Blog identification and Splog detection. In Proc. 2006 AAAI Spring Symp. Computational Ap-proaches to Analyzing Weblogs, pp. 92–99, 2006.

[11] V. N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.

[12] S. Tong and D. Koller. Support vector machine active learning with applications to text classification. In Proc. 17th ICML, pp. 999–1006, 2000.

[13] 佐藤有記,宇津呂武仁,福原知宏,河田容英,村上嘉陽,中 川裕志,神門典子.キーワードの時系列特性を利用したス パムブログの収集・類型化・データセット作成. DEWS2008 論文集, 2008.

[14] Y. Sato, T. Utsuro, T. Fukuhara, Y. Kawada, Y. Mu-rakami, H. Nakagawa, and N. Kando. Analysing fea-tures of Japanese splogs and characteristics of key-words. InProc. 4th AIRWeb, pp. 33–40, 2008.

[15] 吉田光男,山本幹雄. 教師情報を必要としないニュース ページ群からのコンテンツ自動抽出. 日本データベース 学会論文誌, Vol. 8, No. 1, pp. 29–34, 2009.

[16] 片山太一,佐藤有記,宇津呂武仁,芳中隆幸,河田容英,福 原知宏.機械学習を用いたスパムブログ検出における信頼 度の利用.データ工学と情報マネジメントに関するフォー ラム—DEIMフォーラム—論文集, 2009.

[17] T. Katayama, Y. Sato, T. Utsuro, T. Yoshinaka, Y. Kawada, and T. Fukuhara. An empirical study on selective sampling in active learning for splog de-tection. InProc. 5th AIRWeb, pp. 29–36, April 2009.

[18] Y.M. Wang, M. Ma, Y. Niu, and H. Chen. Spam double-funnel: Connecting web spammers with adver-tisers,. InProc. 16th WWW, pp. 291–300, 2007.

[19] D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. InProc. 17th SIGIR, pp.

3–12, 1994.

[20] G. Schohn and D. Cohn. Less is more: Active learning with support vector machines. In Proc. 17th ICML, pp. 839–846, 2000.

[21] J. Suzuki, H. Isozaki, and E. Maeda. Convolution ker-nels with feature selection for natural language pro-cessing. InProc. 42nd ACL, pp. 110–126, 2004.

情報論的学習理論テクニカルレポート2009

Technical Report on Information-Based Induc-tion Sciences 2009 (IBIS2009)

ベーテ自由エネルギーと Loopy belief Propagation に現れる グラフのゼータ関数について

渡辺 有祐

Yusuke Watanabe

福水 健次

Kenji Fukumizu

Abstract: In this paper, we show a new formula which connects the Hessian of the Bethe free energy and the multivariable graph zeta function. Utilizing this formula, we show new methods for analyses of Loopy Belief Propagation (LBP) algorithm. We mainly prove and discuss the formula in the case of binary pairwise model. First, we give a sufficient condition that the Hessian of the Bethe free energy is positive definite, which shows non-convexity for graphs with multiple cycles. The formula clarifies the relation between the local stability of a fixed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP fixed point, and show various conditions of uniqueness. Finally, we discuss the extension to more general class of graphical models including multinomial models and Gaussian models.

Keywords: Loopy Belief Propagation, Bethe free energy, graph zeta function

1 _導入

Pearlによるビリーフプロパゲーション（Belief Prop-agation, BP）アルゴリズム[1]は、木構造を持つ確率モ デルに対して効率的に分配関数や周辺確率分布を厳密計 算することが知られていた。さらにサイクルをもつよう なグラフ上の確率モデルに対してもこのアルゴリズムを そのまま適用すると、各種の応用において非常に高い近 似性能を与えることが経験的に知られている[2]。この ように拡張されたアルゴリズムは通常ルーピービリーフ プロパゲーション(Loopy Belief Propagation, LBP)と 呼ばれている。LBPはBPとは違って、複雑なふるま いをするアルゴリズムであり、それについて理解を深め ることは重要な問題である。

このLBPアルゴリズムはベーテ自由エネルギーと密 接に関係している[3]という大変興味深い性質を持って いる。すなわち、LBPアルゴリズムの固定点がベーテ 自由エネルギーの勾配がゼロの点と一対一に対応する。

この論文ではまず最初に、バイナリかつペアワイズな モデルに対して「ベーテ自由エネルギーの行列式は、正 の因子を除いて、グラフの多変数ゼータ関数の逆数に等 しい」という公式を証明する。その後でこの公式を三つ

∗総合研究大学院大学 複合科学研究科 統計科学専攻、統計数理 研究所, 106-8569東京都港区南麻布4-6-7, tel.03-3446-1501, e-mail [email protected],[email protected]

Institute of Statistical Mathematics, 4-6-7, Minami-Azabu, Minato-Ku, Tokyo, 106-8569

の問題に応用する。

まず第一に、この公式をベーテ自由エネルギーのヘッ セ行列の正定値性に関する議論に応用する。ベーテ自由 エネルギーは一般には凸でないことが知られており、こ れがLBPの振動現象や固定点が多数出現することの一 つの原因になっている。したがって、ヘッセ行列が正定 値である範囲を知ることは興味のある問題である。この 論文ではヘッセ行列が正定値である簡単な十分条件を与 える。そしてさらにベーテ自由エネルギーが凸である必 要十分条件はグラフがツリー、又はただ一つのサイクル を持つグラフであることを証明する。

第二の応用として、LBPの固定点の安定性とその点 でのベーテ自由エネルギーの局所的な構造の関係を議論 する。LBPはベーテ自由エネルギーを単純に小さくする ようなアルゴリズムではないため、その関係は非自明で ある。それについてHeskes [4]は、局所安定なLBPの 固定点はベーテ自由エネルギーの極小であることを示し ている。本論文では、グラフのゼータ関数に現れる行列 のスペクトルについて考え、Heskesの結果を拡張する。

第三に、LBPの固定点の一意性について議論する。

まず、「LBPの固定点の指数の和は1」という定理を示 し、それとゼータ関数とヘッセ行列の公式を組み合わ せるというアプローチで一意性を議論する。特にこの 方法で「二つの一次独立なサイクルを持つグラフ上で、

attractiveでない相互作用の場合」を考えると、LBPの

固定点は一意的であるということを示す。

ここまではバイナリペアワイズのモデルに対する話で あった。本論文の一番最後では、ゼータ関数とベーテ自 由エネルギーの公式が一般の有限状態のグラフィカルモ デルや、ガウス型のモデルに拡張できることを述べる。