Document

A02 計算理論的設計による知
識抽出モデルに関する研究
徳山 豪 (東北大学)
塩浦昭義 (東北大学)
全眞嬉
(東北大学)
河原林健一(東北大学→NII)
研究の目的
• 知識抽出システムでの計算理論的設計や解析の手
法を探る
–
知識抽出: データマイニングだけではない
• 計算幾何学でのパターン抽出
• Voronoi図: 点集合データ→理解しやすい知識形態
• 全列挙→マイニング→最適化 (目的がはっきりするに従い)
• 計算困難性を打破するためのモデルの検討
–
入力の性質を利用した高速アルゴリズム
• パラメトリック複雑度
• アルゴリズム的グラフマイナー理論
–
–
数理経済学での価格決定のモデル
離散凸解析
プロジェクトと成果(2004-2007)
1: 最適曲面近似とデータマイニング(直接のテーマ)
–
–
全,徳山+浅野,加藤他
Journal:5(Algorithmicaなど) Conf(ISAACなど):6
2: Voronoi図とZone図
– 徳山+浅野,Matousek他
– Journal :2(SICOMP, Adv. Math), Conf: 2 (STOC,
SODA)
3: パラメトリック複雑度
–
–
徳山+Halldorsson他
Journal: 2(TCSなど), Conf: 1(WADS),IETA:2
プロジェクトと成果:2
4: アルゴリズム的グラフマイナー理論
–
–
–
河原林+海外研究者等
Journal 多数(30くらい)、Conf 多数
STOC2、FOCS,SODA、ISAAC(Best Paper)
5: オプションの価格決定でのモデルと解析
–
–
塩浦、徳山
Journal :2(Algorithmica, IPL), Conf :1
6: 離散凸解析
–
–
塩浦+室田他
Journal 多数(10くらい)
7: その他: アドホックネットワークのモデルなど
最適曲面近似についての進展
• 非負行列データ: A = (a(i,j) ) i,j = 1,2,..,n
– 2次元格子上の関数と思う
• Aの単峰近似: F = (f(i,j)) : 単峰関数
– Fの水平切断が「良い形」
– Minimize |A-F|2 : L2距離
• 等高線で書かれた地図から「山」を切り出す
単峰近似 (1次元(上図) 2次元(下図))
単峰近似の手法
• グラフの「最大重み支配閉包」問題に帰着する
– G =(V, E): 有向グラフ、
• 頂点に重み w(v) (負の重みもある)
– G の支配閉包: 頂点の集合X
•
uがXの要素で(u,v)が有向辺ならばvもXの要素
– 最大重み支配閉包 (山の等高線に対応)
•
重み和が最大になる支配閉包
• 最大流問題に帰着(多項式時間解法)
中心点に向いた格子グラフでの支配閉包
-1
-1
-2
1
0
-2
1
2
2
-1
1
2
2
0
2
1
1
-1
2
--2
1
0
--3
-4
4
--4
最近の進展(1)
• 「山」の水平断面として自然なのは?
– 星型領域 (技術的困難があった)
– 凸領域 (未解決)
– 星型領域の輪
• 星型領域(輪)についての解法の提案
– 難しさ: グリッドでの星型領域は何か?
– 星型領域: 各点から中心点へ向かう直線
分を含むような領域
– グリッドでの「直線分」の定義が難しい
• 通常の定義だと「星型」らしくなくなる
グリッド星型領域を定めるグラフ(木)
(Martin Noellenburg製作)
最近の進展(2)
• 多峰近似は多項式時間で出来るか?
• 2つのグラフの最大重み支配閉包和問題
– 頂点集合Vと重み(入力行列の要素に対応)
– G=(V, E), G’ =(V, E’) : V上の有向グラフ
•
2つの山に対応
– X: Gでの支配閉包,Y: G’での支配閉包
– X∪Y の形で最大重みのものを求める
• NHCの会議(06調布)でのOpen Problem
– NP困難か?G, G’が根付き有向木の場合にはどうか?
– 木の場合は、支配閉包=根付き部分木
残念ながらNP困難
• 2つの根付き有向木(グリッドの部分木に向き
をつけたもの)に対してすらNP困難
– MAX2SATを帰着する
•
→ 現在の定式化だと2次元での多峰近似
は難しそう
• 多峰近似問題の近似アルゴリズム??
– 最大支配閉包和の形だと近似できない
M+N
M+N
M+N
M+N
M+N
M+N
S3 ∨S2
-N
S3
-N
S3
S3 ∨S1
S2 ∨S3
1/2
S2 ∨S1
-N
S2
S3 ∨S2
1/2
1/2
-N
S2
1/2
1/2
S2∨S3
1/2
-N
S1
-N
S1
S1∨S2
S3
-M
-M
M
S3
-M
M
-M
S2
-M
-M
M
S2
-M
M
-M
S1
-M
-M
M
S1
-M
M
-M
-M
-M -M
1/2
1/2
S1∨S3
-N
M+N
-N
-N
M+N
-N
-N
-M
-M
S1 S1 S2 S2 S3 S3
M+N
M+N
-N
-M
M+N
S1 S1 S2 S2 S3 S3
M+N
M+N
M+N
M+N
M+N
M+N
総重み=
M+N
S3 ∨S2
-N
S3
-N
S3
S3 ∨S1
S2 ∨S3
1/2
S2 ∨S1
-N
S2
nM+MAX2SAT
S3 ∨S2
1/2
1/2
-N
S2
1/2
1/2
S2∨S3
1/2
-N
S1
-N
S1
S1∨S2
S3
-M
-M
M
S3
-M
M
-M
S2
-M
-M
M
S2
-M
M
-M
S1
-M
-M
M
S1
-M
M
-M
-M
-M -M
S1 S1 S2
1/2
1/2
S1∨S3
-N
M+N
-N
-N
M+N
-N
-N
-M
-M
S2 S3 S3
M+N
M+N
-N
-M
M+N
S1 S1 S2 S2 S3 S3
M+N