C07 Webコンテンツ活用に関連した離散最適化問題の研究 ○増山繁（豊橋技術科学大学） 梅村恭司(豊橋技術科学大学)、中山慎一(徳島大学)、本間宏利 (釧路工業高等専門学校)、相田 慎、(豊橋技術科学大学)、石井利昌(小樽商科大学) 科研費特定領域「新世代の計算限界 －その解明と打破－ 平成19年度第１回全体会議 平成19年5月14日(月)-15日(火) 東京大学本郷キャンパス 工学部６号館３階セミナー室A，D

取り組んだ課題 Webコンテンツ活用のためのテキストからの情報抽出及びテキスト自動要約のためのアルゴリズム

主要な成果（１） Webコンテンツ活用のためのテキストからの情報抽出及びテキスト自動要約のアルゴリズム ユーザの要約要求を反映するためにユーザとのインタラクションを導入した複数文書要約システム 論文Latex原稿からのプレゼンテーション資料自動生成 テキストマイニングにおけるある事象と原因表現抽出の汎用的手法：交通事故原因表現、企業の業績要因等

主要な成果（２） Webコンテンツ配信に関連した問題、および、その基盤としての高度情報通信網に関連した問題 最小節点ランキング全域木問題の計算複雑度 の解明：ＮＰ困難 外平面グラフ上での最小節点ランキング全域木問題に対する多項式時間アルゴリズム 外平面グラフ上での最小枝ランキング問題に対する多項式時間アルゴリズム

テキスト自動要約 ユーザの要約要求を反映するためにユーザとのインタラクションを導 入した複数文書要約システム［酒井， 増山２００５］

本複数文書要約システム アイボの販売方法 文書表題 アイボの動作･性能 キーワード ・・・ テスト販売 予約受け付け 予約 インターネット 人工知能技術 喜怒哀楽 しっぽ アイボの販売方法 文書表題 アイボの動作･性能 キーワード

スクリーンショット1 アイボの販売方法 ソニーは１１日、４本足で歩く犬に似たペットロボット「ＡＩＢＯ」を２５万円で販売すると発表した。アイボは６月１日、インターネット上で日本３０００台、米国２０００台の予約受け付けが始まる。子犬型のペットロボット。「アイボ」と読む。ペット型ロボット「ＡＩＢＯ」の予約受け付けが一日午前九時から、インターネットで始まったが、受け付け開始と同時にアクセスが殺到し、日本分の三千台は、二十分ほどで“完売”になった。日米同時に今月一日発売されたソニーのペット型ロボット「ＡＩＢＯ」。

スクリーンショット2 アイボの性能･動作 ソニーは１１日、４本足で歩く犬に似たペットロボット「ＡＩＢＯ」を２５万円で販売すると発表した。アイボの本体はプラスチック製で、足や首、あご、尾に計１８個の小型モーターがついており、関節が自由に動くため、歩くだけでなく、座ったり伸びをしたりする。アイボは学習・成長機能があり、その動作で喜びや悲しみ、怒りなどの「感情」や「本能」を表現するようプログラムされている。子犬型のペットロボット。「アイボ」と読む。日米同時に今月一日発売されたソニーのペット型ロボット「ＡＩＢＯ」。

関連キーワードの抽出 TF・IDF法を改良 TF・IDF法に基づく重み 名詞tiの出現確率に 基づくエントロピー

名詞の位置情報による重み 文書の第1文，文書集合の第1記事には重要な情報が 含まれている可能性が高い 第1記事，第1文の名詞が1になる指標 nl(d): 文書d の文の数 nlf(ti,d): 文書d において，名詞ti が最初に出現する文番号 rt(ti,S): 名詞ti を含む文書d の順位（S の文書は時系列順にソート） 文書の第1文，文書集合の第1記事には重要な情報が 含まれている可能性が高い

論文Latex原稿からのプレゼンテーション資料自動生成 [宮本、酒井、増山 2006]

テキストマイニングにおけるある事象と原因表現抽出の汎用的手法

手法の概要

派生表現

派生表現の選択

派生表現と手がかり表現の関係

企業の業績発表記事からの業績要因の抽出 業績要因が記述されている文において要因が異なっている場合でも共通して出現する部分 共通頻出表現 初期手がかり表現集合 共通頻出表現集合 手がかり表現集合 が好調 が不振 売り上げ 受注 需要 手がかり表現獲得ステップ 共通頻出表現獲得ステップ

共通頻出表現の選別 適切な共通頻出表現を選別 例： が好調 売り上げ が回復 が不振 様々な手がかり表現に係る共通頻出表現は適切 例： が好調 売り上げ が回復 共通頻出表現 が不振 手がかり表現 共通頻出表現が手がかり表現に係る確率に基づくエントロピー H(e)を計算 エントロピーが高い共通頻出表現→適切な共通頻出表現

手がかり表現の選別 手がかり表現候補から適切な手がかり表現を選別 例： 売り上げ 需要 が好調 受注 様々な共通頻出表現が係る手がかり表現は適切 例： 売り上げ 手がかり表現候補 需要 が好調 受注 共通頻出表現 手がかり表現候補に対して共通頻出表現が係る確率に 基づくエントロピー H(s) を計算 エントロピーが高い手がかり表現候補⇒適切な手がかり表現

不適切な手がかり表現の除去 が成り立つ手がかり表現を除去 業績発表記事以外の文書集合Sn（SVMで業績発表記事と識別されなかったもの）におけるスコアを計算し， 業績発表記事集合におけるスコア 業績発表記事以外の文書集合におけるスコア が成り立つ手がかり表現を除去 不適切な手がかり表現にはW(s,Sp)，W(s,Sn)，ともに高いスコアが付与

Webコンテンツ配信に関連した問題、および、その基盤としての高度情報通信網に関連した問題 最小節点ランキング全域木問題の計算複雑度 の解明：ＮＰ困難 外平面グラフ上での最小節点ランキング全域木問題に対する多項式時間アルゴリズム 外平面グラフ上での最小枝ランキング問題に対する多項式時間アルゴリズム

最小節点全域木問題の応用：センサネットワーク 通信可能なセンサ間を「枝」(線分)で結んでいる。

センサネットワーク （※）一般に通信ネットワーク上でのトラフィック監視 2 1 2 1 1 1 2 1 3 1 1 2 1 4 1 2 2 3 1 1 1 1 1 1 1 2 2 2 1 1 2 1 1 1 1 1 3 3 1 2

節点ランキング 5 3 1 4 2 1 2 3 同じラベルを持つ節点を結ぶどの路上にも、そのラベルより大きな値の For example. For each path between any two vertices with the same rank, there exists at least one vertex whose rank is greater than the rank of these two vertices. 2 3 同じラベルを持つ節点を結ぶどの路上にも、そのラベルより大きな値の ラベルを持つ節点が必ずあるような、節点への自然数によるラベル付け

最小節点ランキング問題 4 3 2 1 グラフGの最小節点ラン キングにおける最大 ラベルの値 与えられたグラフの節点ランキングのうちで最大ランクを最小にする ような節点ランキングをみつける問題

最小節点ランキング全域木問題 1 3 2 4 1 2 3 Gの全域木Tのうち、　　　　を最小にするものを求める 問題

最小節点ランキング全域木問題に関連した問題 最小節点ランキング問題 最小辺ランキング問題 最小辺ランキング全域木問題

節点ランキングと辺ランキング 節点ランキング 辺ランキング 1 2 3 4 1 2 5 3 4 節点ランキングの定義で｢節点｣とある ところを｢辺｣と変えたもの

最小節点ランキング問題 　元々工場での製造工程における組み立て段階のスケジューリング問題が動機[Iyer, Ratliff, Vijayan 1988] ・ VLSIレイアウトへの応用[Leiserson 1980],[Sen, Geng, Guha 1992] ・一般のグラフ・・・NP困難[Pothen, 1988] ・多項式時間アルゴリズム －木 [Schaffer, 1990] －区間グラフ，置換グラフ，台形グラフ[Deogun et. al., 1999] 　－k-木グラフ [Bodlaender et. al., 1998] (※)節点ランキングという用語は用いられていないが、最小節点ランキング問題自身を最初に扱ったのは、 VLSIレイアウトへの応用[Leiserson 1980]

最小辺ランキング問題 ・やはり、元々製造工程における組み立て段階のスケジューリング問題が動機[Iyer, Ratliff, Vijayan 1991] 　一般のグラフ・・・NP困難[Lam, Yue, 1998] 多項式アルゴリズム 　木 [Torre et. al., 1995]

最小時間組み立てスケジューリング問題 （※）最小辺ランキング問題に定式化 1 2 5 3 4

最小辺ランキング全域木問題（１） 1 2 3

最小辺ランキング全域木問題（２） 　[Makino, Uno and Ibaraki, 2001]により提唱。その中に以下の結果が示されている。 　 ・NP困難である 　 ・近似アルゴリズムが開発されている 応用：関係データベースにおける並列結合処理等 Split graphに対する多項式時間アルゴリズム [Makino, Uno, Ibaraki　2006]

（＊ 最適値を求めるのではなく，yes / no を求める問題．） MVRSTのNP困難性の証明 [Miyata, Masuyama, Nakayama, Zhao　2006] 3次元マッチング問題（NP完全） 決定問題版＊のMVRST 多項式時間帰着可能 （＊ 最適値を求めるのではなく，yes / no を求める問題．）

帰着のためのgadget

計算量： O(|V|・(|V|+|E|)) 近似アルゴリズム 与えられたグラフをG=(V,E)とする。 1. V　の各要素vに対して、ｖからGの他のすべての節点に対する最短路を求める。 　　　　　　　　　　　　 但し、d(u,v)はu、vの距離 2. となるsを選び、ｓから幅優先探索を行い木Tを得、それに対し　　　　を求める。 計算量： O(|V|・(|V|+|E|)) 近似率 （ 　　はGの全域木の直径の最小値）

外平面グラフ上でMVRSTを多項式時間で求めるアルゴリズム 　[Nakayama, Masuyama 2006]

外平面グラフ上のMVRST 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 (1) (2) (3) Given a outerplanar graph G, we find an minimum vertex ranking spanning tree like this.

アルゴリズムの方針 外周上の連続する節点からなる部分グラフ Gi ,i=1,・・・,l, を求める ある節点 v に各部分グラフ Gi ,i=1,・・・,l, における最小節点ランキング全域木を接続する．その場合，各部分グラフ Gi における最大ランクを 　　とすると，節点 v には ランク k+1　を割り当てる

全域木 3 2 4 1 5 (1) (4) (2) (3) 6 15 14 7 Like tree, we divide a outerplanar graph to some subgraphs and find each minimum vertex ranking spanning tree in each subgraph. After that, we join the minimum vertex ranking spanning trees to a vertex. In this case, we join these trees to vertex 7. 8 13 12 9 10 11

今後の課題 MVRSTに対して多項式時間アルゴリズムを持ち、かつ、センサネットワークへの応用上意味のある他のグラフのクラスを求めること

外平面グラフにおける，最小辺ランキング [Nakayama, Masuyama2007] 外平面グラフGにおいて，Gの部分グラフも外平面グラフなので， 部分グラフの最小節点ランキング全域木を再帰的に求めていくことが可能となる． そのために必要な補題が次の通りである． この補題を基に再帰的にアルゴリズムを構成できる．

最小辺ランキング問題 辺ランキング問題 一般のグラフ・・・NP困難[Lam, Yue, 1998] 多項式時間アルゴリズム 　木 [Torre et. al., 1995] 木以外のクラスで多項式時間アルゴリズムが存在するか？

最小辺ランキングと極小カット 極小カット

最小辺ランキングと極小カット [　補題　]　グラフ G は連結グラフとする．また，C を G の極小カット全体からなるクラスとする．最小辺ランキングと極小カットについて次の式が成り立つ． ただし，G1,G2 はC ∈ C により分離された部分グラフである．

最小辺ランキングと極小カット 1 3 5 2 6 4 3 7 4 1 1 2

外平面グラフ 12 11 10 13 14 9 15 8 1 7 2 6 3 4 5

外平面グラフ 12 11 10 13 14 9 15 8 1 7 2 6 3 4 5 極小カット

外平面グラフ 12 11 10 13 14 9 15 8 1 7 2 6 3 4 5 極小カット

計算量 Step 1.部分グラフ G[x,y;z,w], x,y,z,w=1,・・・,n の数が O(n4) であり，各部分グラフに対し極小カットを求めるのに O(n) 時間かかるので，全体として O(n5) 時間かかる． Step 2. O(n4) 個の部分グラフに対し， 最大O(n2) 個の極小分離辺集合が存在する．よって，全体としてO(n6) 時間かかる．

まとめ 最小辺ランキングと極小カットの関係 2連結外平面グラフにおける最小辺ランキング問題を解く多項式時間アルゴリズム

今後の課題 最小辺ランキングと極小カットの関係を用い，他の部分クラスにおける効率の良いアルゴリズムの開発

ご清聴ありがとうございました。