4 MapReduce 粒子フィルタ
6.2 ベンチマークテスト
平坦化パラメータλと中間ユニット数M の最適値 (λ∗, M∗)を探し，この最適値におけるWRBFNNのパ フォーマンスと同じ中間ユニット数M∗における
org-RBFNNのパフォーマンスを比較した．本稿では
UCI-machine learning repositoryに収録されてある
cpu-performanceデータセットに対するパフォーマンス のみ示す2．5で述べた計算量の削減法を考察するためモ デル選択の方法に応じてパフォーマンスの比較を併せて 行った．このため，以降，簡略化されたモデル選択法を 採用するものを”-Quick”を付けて示すものとする．す なわちMixture of Gaussianを使用した分布推定に関す るモデル選択については，AIC−org と記し，その簡 略化されたものをAIC−Quickと記すことにする．
本来ならばrecording-, rehearsal-phaseを交互に何度 も繰り返す学習法ではあるが，性能を評価するには1回 のrecording, rehearsal-phaseだけで十分である．
データセットからは，その一部の100個データをラン ダムに選択したものを50セット用意した．それぞれの 100個のデータはrecording phaseにおいてバッファB に貯められるものとみなす．
分布推定にあたっては分布の分散共分散行列を簡単の ため対角要素のみ扱い，パラメータの推定を行った．λ を探す際の刻幅は0.1とした．また，中間ユニット数の 上限を20個としてある．また評価用のテストデータは 全データセットとした．ただし評価結果に関してはデー タセットの選びかたによって誤差が大きく変動するため，
(x, y) = (M SEW RBF N N, M SEorg−RBF N N) をプロットして評価する．ここに
M SE∗≡ 1 Ntotal
N∑total
b=1
(F[xb]−fθ∗(xb))2, (21) である．すなわちこのようにして打たれた点が直線y=x よりも上に分布しているならば，WRBFNNのパフォー
マンスがorg-RBFNNのそれよりも良いことを意味す
る．但し，学習が不安定に陥るのを防ぐためW(x)の値 が10以上にならないように制限を加えた．
図4は各学習データセットに対する
(x, y) = (M SEW RBF N N, M SEorg−RBF N N)
をプロットし，したものである．本手法においては各々 の学習データセットにおいて最適なλと中間ユニット 数M を探索するが，場合によってはλ = 0すなわち
WRBFNNでありながらorg-RBFNNと同一の学習法
2他のデータセットに対するパフォーマンスについては文献[14]を 参照されたい．ただし[14]では分布推定に関するモデル選択は簡略 化されたものを使用している．
を選択することがある．つまり，この場合はポイントが y=x上に配置される．しかしλ >0を選択した場合に その効果があればパフォーマンスのポイントがy=xの 上側に配置されるが悪ければ下側に配置される．
この結果よりcpu-performanceに関してはパフォーマ ンスのポイントがy =xよりも上に配置される頻度が 高いため，本手法の効果が得られていると考えられる．
また，簡略化されたモデル選択アルゴリズムを使用 した”AIC-Quick”とオリジナルのモデル選択アルゴリ ズムを使用した”AIC-org”を比較すると，概ね結果が重 なっており，計算量を抑えてもパフォーマンスに与える 影響が少ないことを示唆している．
7 まとめと考察
本研究では，追記学習が共変量シフトの一つであるこ とを指摘し，これまでに研究されてきた共変量シフトに 対処する学習戦略を組み込んだ追記学習法の構築を目指 した．これを実現するために，既に与えられたサンプル からこの先将来に渡って提示されるサンプルの分布を予 測する手法を考案し，これを使った重み付き誤差関数を 定義した．
しかしながら，既に得られたサンプルから遠い将来 に渡って提示されるサンプルを正確に予測することは不 可能である．提案手法では，近い将来，既に与えられた サンプルの近傍に提示されるサンプルの分布を予測す るものとなっている．これは次の意味において妥当であ る．すなわち，RBFNNを使用する場合，学習後のネッ トワークが対処できる入力領域(定義域)は既に与えられ た学習サンプルの近傍に限られる．したがって，既学習 サンプルから遠く離れたサンプルに対しては，いかなる 努力も果を結ばないと考えられるため，ここでの予測分 布も既学習サンプルの近傍において有効に働けば良い．
本研究ではさらにこれに合うRBFNNの中間ユニッ ト数を決定する手法も与え，常に与えられたデータセッ トにフィットし、且つ将来与えられるデータにもフィッ トするであろうRBFNNを構築することが出来る．また 実験結果よりモデル選択アルゴリズムを簡略化すること により計算量を低く抑えることが出来ることも示した．
本稿での詳述は避けたが，複数のベンチマークテスト も行っており，提案システムの効果は学習データセット に大きく依存することが分かっている[14]．つまり本手 法において3.2で予測するVirtual Concept Drift環境に フィットするデータであれば効果を発揮するものの，そ れ以外のデータ、すなわち学習データとデータセット全 体の分布とが一致する場合などでは効果を発揮しない．
だがVirtual Concept Drift環境は現実の学習環境に
おいては頻繁に発生する．例えば太陽電池の照度とパ ネル表面温度に対する最大電力点の分布は太陽の傾き と共に時々刻々と変化する．さらに学校で毎日生徒に教 える事柄に付いても，最初から全体を網羅する内容では 無くそれぞれの項目を順番に教えていくため，Virtual
Concept Driftと言える．したがってこのような現実の
学習環境において本手法が必要とされると考える．
参考文献
[1] A. Tsymbal. The problem of concept drift: definitions and related work. Technical Report TCD-CS-2004-15, Department of Computer Science, Trinity College Dublin, 2004.
[2] Takao Yoneda, Masashi Yamanaka, and Yukinori Kakazu. Study on optimization of grinding conditions using neural networks – a method of additional learn-ing –. Journal of the Japan Society of Precision Engi-neering/Seimitsu kogakukaishi, 58(10):1707–1712, Oc-tober 1992.
[3] Hiroshi Yamakawa, Daiki Masumoto, Takashi Ki-moto, and Shigemi Nagata. Active data selection and subsequent revision for sequential learning with neural networks. World congress of neural networks (WCNN’94), 3:661–666, 1994.
[4] Stefan Schaal and Christopher G. Atkeson. Con-structive incremental learning from only local informa-tion. Neural Computation, 10(8):2047–2084, Novem-ber 1998.
[5] Koichiro Yamauchi, Nobuhiko Yamaguchi, and Nao-hiro Ishii. Incremental learning methods with retriev-ing interfered patterns. IEEE transactions on neural networks, 10(6):1351–1365, November 1999.
[6] Robert M. French. Pseudo-recurrent connectionist networks: An approach to the “sensitivity stability”
dilemma. Connection Science, 9(4):353–379, 1997.
[7] Bernard Ans and Stephane Roussert. Neural networks with a self-refreshing memory: knowledge transfer in sequential learning tasks without catastrophic forget-ting. Connection Science, 12(1):1–19, 2000.
[8] Nikola Kasabov. Evolving fuzzy neural networks for supervised/unsupervised online knowledge-based learning. IEEE Transactions on Systems, Man, and Cybernetics, 31(6):902–918, December 2001.
[9] Seiichi Ozawa, Soon Lee Toh, Shigeo Abe, Shaoning Pang, and Nikola Kasabov. Incremental learning of feature space and classifier for face recognition.Neural Networks, 18:575–584, 2005.
[10] Shimodaira Hidetoshi. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Infer-ence, 90(2):227–244, 2000.
[11] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul von B¨unau, and Motoaki Kawan-abe. Direct importance estimation with model se-lection and its application to covariate shift adapta-tion. In Twenty-First Annual Conference on Neural
0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018
0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018
AIC-quick:
AIC-org:
y=x
図4: cpu-performanceに対するパフォーマンス(AIC-orgとAIC-quickを同時にプロットしてある) Information Processing Systems (NIPS2007),
Decem-ber 2007.
[12] Koichiro Yamauchi. Covariate shift and incremen-tal learning. In Advances in Neuro-Information Processing 15th International Conference, ICONIP 2008, Auckland, New Zealand, November 25-28, 2008, Revised Selected Papers, Part I, pages 1154–1162, November 2008.
[13] 山内 康一郎.共変量シフトと追記学習. Technical Report NC2008-142,電子情報通信学会技術報告, 3月2009.
[14] Koichiro Yamauchi. Optimal incremental learning un-der covariate shift. Memetic Computing, page Ac-cepted, 2009.
[15] 繁桝 算男. ベイズ統計入門. 東京大学出版会, 1985.
[16] A. P. Dempster, N. M. Laird, and D. B. Rubin. Max-imum likelihood from incomplete data via the em al-gorithm. Journal of the Royal Statistical Society, B 39(1):1–38, 1977.
[17] Hirotugu Akaike. A new look at the statistical model identification.IEEE Transactions on Automatic Con-trol, AC-19(6):716–723, December 1974.
[18] J. Moody and C. J. Darken. Fast learning in neu-ral networks of locally-tuned processing units. Neural Computation, 1:281–294, 1989.
[19] J.C. Bezdek. A convergence theorem for the fuzzy isodata clustering algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2:1–8, 1980.
[20] John Platt. A resource allocating network for func-tion interpolafunc-tion.Neural Computation, 3(2):213–225, 1991.
情報論的学習理論テクニカルレポート2009
Technical Report on Information-Based Induc-tion Sciences 2009 (IBIS2009)
機械学習を用いたスプログ検出における HTML 構造の類似性の利用
Utilizing Similarities of HTML Structures in Splog Detection by Machine Learning
片山 太一
∗Taichi Katayama
芳中 隆幸
†Takayuki Yoshinaka
宇津呂 武仁
∗Takehito Utsuro
河田 容英
‡Yasuhide Kawada 福原 知宏
§Tomohiro Fukuhara
Abstract: Spam blogs or splogs are blogs hosting spam posts, created using machine generated or hijacked content for the sole purpose of hosting advertisements or raising the PageRank of target sites. Among those splogs, this paper focuses on detecting a group of splogs which are estimated to be created by an identical spammer. We especially show that similarities of html structures among those splogs created by an identical spammer contribute to improving the performance of splog detection. In measuring similarities of html structures, we extract a list of blocks (minimum unit of content) from the DOM tree of a html file. We show that the html files of splogs estimated to be created by an identical spammer tend to have similar DOM trees and this tendency is quite effective in splog detection.
Keywords: spam blog, machine learning, HTML structure, confidence measure, SVM
1 まえがき
ブログには個人の意見情報が記されており，市場の動 向を推測するための手掛かりや製品についての意見調査 をする上で有益であるとして，近年注目を集めている．
そのため，従来からあるインデクシングのみを行う検索 エンジンとは異なる，ブログ特有の情報検索サービスが 出現している．
∗筑 波 大 学 大 学 院 シ ス テ ム 情 報 工 学 研 究 科, 〒 305-8573 茨 城 県つ く ば 市天 王 台 1-1-1, email: {katayamataichi2008, ut-suro}@ nlp.iit.tsukuba.ac.jp
Graduate School of Systems and Information Engineer-ing,University of Tsukuba, Tsukuba, 305-8573, Japan
†東京電機大学院工学研究科,〒101-8457東京都千代田区神田錦 町2-2, email: yoshinaka @ cdl.im.dendai.ac.jp
Graduate School of Engineering, Tokyo Denki University, Tokyo, 101-8457, Japan
‡(株)ナビックス,〒141-0031東京都品川区西五反田8-3-6, Navix Co., Ltd., 8-3-6 Nishi-Gotanda, Shinagawa-Ku Tokyo 141-0031, Japan
§東京大学 人工物工学研究センター,〒277-8568千葉県柏市柏の 葉5-1-5, email: fukuhara @ race.u-tokyo.ac.jp
Research into Artifacts, Center for Engineering, University of Tokyo Kashiwa, Chiba 277-8568, Japan
具体的には，ブログ解析サービスとして，Technorati1， BlogPulse2，kizasi.jp3，blogWatcher4[1]などが存在す る．多言語ブログサービスとしては，Globe of Blogs5が 言語横断ブログ記事検索機能を提供している．またBest Blogs in Asia Directory6がアジア言語ブログの検索機 能を提供している．Blogwise7もまた多言語ブログ記事 の分析を行っている．
一方で，ブログのウェブコンテンツの作成と配信は非 常に容易になっており，そのことが引き金となって，ア フィリエイト収入を得ることを目的とするスパムブログ (以下，スプログ)が急増している [2, 3, 4, 5, 6]．スプ ログにおいては，通常，広告主への誘導または対象サイ トのページランクを増加する目的のもとで，機械的な 文書作成や他サイトの引用という手段を用いて自動的
1http://technorati.com/
2http://www.blogpulse.com/
3http://kizasi.jp/(日本語のみ)
4http://blogwatcher.pi.titech.ac.jp/ (日本語のみ)
5http://www.globeofblogs.com/
6http://www.misohoni.com/bba/
7http://www.blogwise.com/
表1: スプログ/非スプログデータセット
(a)スプログ/非スプログ数
ブログホスト CC社 SS社 その他 合計 スプログ数 198 293 277 768 非スプログ数 210 259 2849 3318
合計 408 552 3126 4086 (b)大量生成型スプログ数
ブログホスト CC社 SS社
ID 1 2 3 4
スプログ数 163 26 31 33
に記事を生成し，大量のリンクを有するブログを機械的 に自動生成する．[4]は英語ブログにおいて，約88%の ブログサイトがスプログであり，それは全ブログポスト の75%を占めると報告している．このことから，[3, 7]
に述べられているように，スプログは情報検索品質の 低下やネットワークと格納資源の多大な浪費などといっ た問題を起こす要因となる．そのため，近年，スプログ の分析や検出を目的とした研究が進められている．[5]
では，TREC8Blog06データコレクションを用いて，ス プログのピング時系列特性，入力度数/出力度数の分布 特性，典型的な単語群を分析している．また，[4, 6]は，
BlogPulseデータセットを用いたスプログ分析の結果を
報告している．一方，[8, 9, 10, 4]では，スプログを機 械的に特定し，排除する技術について報告している．
以上の先行研究をふまえて，本論文では，同一のスパ ムブログ作成者が自動的に大量生成したと推測されるス プログは，HTML構造が類似していることを示す．また，
機械学習のひとつであるSupport Vector Machines [11]
(SVM)を用いた枠組みによって，スパムブログの判定
を行うタスクを設定する．未判定のブログが入力された とき，SVMの分離平面によって，スパムブログかそう でないかを決定する．さらに，SVMでは分離平面との 距離を出力できるので，分離平面との距離を信頼度とし て利用する[12]．出力である信頼度を用いて，ブログを，
高信頼度スパムブログ判定結果，高信頼度非スパムブロ グ判定結果，低信頼度判定結果の三種類に分ける．特に，
HTML構造の類似性を素性として，SVMを用いたスプ ログ検出を行った結果において，スプログ検出の性能が 向上することを示す．
8http://trec.nist.gov/
䉴䊒䊨䉫1 䉴䊒䊨䉫䋲
図1: HTML文書からのDOM系列抽出およびDOM系 列差分算出の例
2 スプログ / 非スプログデータセット
本論文では，2007年9 月∼2008年2月の期間にお いて収集した日本語スプログ/非スプログデータセット を用いる．日本語スプログ/非スプログデータセットは，
[13, 14]で提案された基準によって，スプログ/非スプロ グを判定した結果が付与されている．また，日本語スプ ログ/非スプログデータセットの中で，極めて構造が類 似するスプログを，同一作成者が自動生成している「大 量生成型」のスプログ[13, 14]として同定し，大量生成 型スパマーIDを付与している。それ以外のスプログを
「単発」スプログとした。
本論文の評価のうち，特に大量生成型スプログを対 象とした評価においては，スプログ・非スプログデータ セット中において，一定数以上の大量生成型スプログを 収集済の大量生成型スパマーIDを対象とする．具体的 には，表1に示すように，ブログホストCC社におけ るスパマーID=1の大量生成型スプログ，およびSS社 におけるスパマーID= 2, 3, 4の大量生成型スプログを 対象とする．なお，[13, 14]においては，2社以上のブ ログホストにまたがって，同一の大量生成型スパマーに よって自動生成されたと推測される大量生成型スプログ も収集されている．しかし，異なるブログホストのスプ ログ・非スプログの間では，HTML文書の構造が大き く異なることが多いため，本論文では，同一の大量生成 型スパマーによって自動生成された大量生成型スプログ のうち，特にブログホストが同一のものに限定して評価 を行う．