Comments
Description
Transcript
F - 知識ベース研究室
知識ベース研究室概要
• 教授：原口誠
• DC：２
MC：９
准教授：吉岡真治
B：３
助教：大久保好章
研究生：２
キーは情報の類似性・抽象化
膨大なデータから，有用な
知識や情報を発見・抽出し，
既存の知識とともにそれら
を組織化・体系化した後、
再利用するためのキーは，
情報の類似性・抽象化にあ
るとの問題意識のもとに，
知識ベース研究室では，理
論的・実験的側面から様々
な研究を行っています．
文書化された知識
作業記録
DB
身体動作のような
動きのある情報
膨大な文書・Web
ページ管理のための
物語データベース
情報検索＋
知識管理
「差異・派生現
象」の発見・マ
イニング
身体動作ＤＢ＋モーショ
ン合成・編集
複数国の新聞からの他観点比較による分析
～GDELTデータを用いた分析～
○吉岡真治（北海道大学）
神門典子（NII）
背景：複数国のニュースサイトの分析
地域ごとに取り上げるニュースが違う
– 国連の会議のような全世界的に興味をもたれる事象
の報道内容は、地域（読者）の興味の影響を受ける
複数ニュースサイトの比較による世界ニュース
分析システムの提案
世界ニュース分析システム
異なる国から発信されたニュースを統合
言語横断検索
世界
ニュース
DB
日本の主張が
海外で
あまり報道さ
れていないな
情報源分析
観点の整理
情報要求に
応じた要約
異なる特徴：言語（他言語（自国語・他国語））
興味（想定読者の興味：発行元の国の興味）
報道されるニュースの量（自国語版と他国語版の違い）
情報源の違いの分析
地球温暖化に
関する世界中
の意見は？
様々な観点から
新聞の分析
NSContrastの機能
複数国のニュースサイトの比較
– 各国が関心を持つトピックの比較分析
• 各国におけるメジャーなトピックの違い
– バースト解析の比較
– 相関性の高い共起語による関連語の抽出
• 各国の比較によるトピックの分析
– 相関性の比に注目した関連語の抽出
マイナーメジャーな関連語や無視されている関連語を抽
出
– 様々な観点による分析
• 意見分析の結果を考慮した比較
– 意見の賛否を考慮した比較
• マルチファセットによる結果の提示
NSContrastの機能（１）
各国におけるメジャーなトピックの発見・比較
– 今日の話題
• 記事のクラスタリング結果によるトピック発見
– 国別注目単語比較
• 単語の出現回数に注目し、通常時よりも多く出現し
ている単語に注目し、各国の注目トピックに関する
情報を発見
日本
・インフルエンザ
・エジプトのデモ
・大雪
韓国
・エジプトのデモ
・口蹄疫
・KTXの脱線
中国
・春節
・インフレ
・エジプトからの
引き上げ
NSContrastの機能（２）
同一トピックに対する興味の違いの分析
– 関連語の関係性分析
• トピックに関する新聞記事を検索結果として絞り込
み、各国で、その記事群に特徴的な単語を関連語
として抽出し、その関係をネットワークとして可視化
– 関連語の時間遷移分析
関連語の関係性分析
核兵器問題に注目
（北朝鮮とセット）
インドのテロ事件の報道
多くの新聞の共通の興味
アルカイダに注目
NSContrastの機能（３）
複数の情報の集約
– 国別比較
• バースト期間とその記事数の繊維の可視化＋関連
語の関係性分析の可視化結果を表示
エジプトを含む
記事数の遷移
・中国は記事
が少ない
システムの機能（４）
複数の情報の集約
– 多観点分析(マルチファセット分析)
• 人名・地名・意見など様々な条件でデータを絞り込
み、結果をグラフとして可視化
GDELT
Global Database of Events, Language and Tone
– 全世界規模で集めた新聞記事（GoogleNewsが主なリ
ソース）から作成した世界中のイベントやその報道の
トーン（賛否）のデータベース
GDELTデータの詳細
２つのデータベース
– Global Event Database
世界中で起こったイベントに関するデータベース、特
定の月（２０１３年４月１日以降では、特定の日）に起こ
ったイベントのリストと、その関連情報のデータベース
（１９７９年〜現在）
– GDELT Global Knowledge Graph (GKG)
Global Event Databaseのイベントに関するより詳細な
データベースで、主に記事を単位として作成され、そ
の記事中で参照されているイベントやその関連情報
のデータベース（２０１３年４月１日〜現在）
Global Event Database
イベントに関するデータベース
–
–
–
–
–
–
イベントの起きた日時
同一のイベントを報じている記事の記事数
報道が開始された期日
イベントのタイプ（CAMEOコードの利用）
関連する人物、組織、地名
数値化したトーン（正の値が賛成、０が中立、負の値
が反対で、絶対値がその度合いを示す）の平均
Global Event Databaseの例
Event and Date
323738695 20141116 201411 2014 2014.8658
Actor attribute
JPNELIGOV SHINZO ABE JPN ELI GOV SGP
013:楽観的なコメント
イベントのインパクト（GoldSteinScale)0.4
SINGAPORE
SGP
情報源は１つ、３つの記事で報道、トーン2.4822…
Event Action Attribute
1 013 013 01 1 0.4 3 1 3 2.4822695035461 4
Event Geography
Queensland Australia AS AS04 -27.5 153.017 1561728 1 Brunei BX BX 4.5 114.667 BX 4 Brisbane
Queensland Australia AS AS04 -27.5 153.017 1561728 20141117
URL
最初にイベントが現れたURL１件のみ
Global Knowledge Graph
記事を単位としたデータベース
–
–
–
–
–
記事中で述べられているイベントのリスト
ほぼ同じ内容を報じている記事の記事数
記事の分類コード
記事中に含まれる人物、組織、地名
数値化したトーン（正の値が賛成、０が中立、負の値
が反対で、絶対値がその度合いを示す）の平均
Global Knowledge Graphの例
Primary attribute
20141117 1
Topic
PROTEST#10##1#Singapore#SN#SN#1.3667#103.8#SN
TAX_ETHNICITY;TAX_ETHNICITY_JAPANESE;...
Location and count
1#Peru#PE#PE#-10#-76#PE;1#Australia#AS#AS#27#133#AS;
Person name, organization name shinzo abe pacific
トーン（賛否）、賛成スコア、否定スコア、
partnership;foreign
ministry;united states
極性、活性度、他の情報源への参照度合い
Tone score
1.73010380622837 2.422145329 0.692041522
3.114186851 19.03114187 0.346020761245675
Event id
323861826 323861741 323861743 …
URL
記事のURL
GDELTデータの利用
記事をベースに分析
→ Global Knowledge Graphの利用
GKGから抽出可能な情報
–
–
–
–
–
日付
人命、組織名、地名
賛否
サイト名
URL
サイト国の情報
– 各国のニュースサイトに関するポータルサイト
http://www.world-newspapers.com/ の情報を利用
サイトの属する地域
– 国名から、アメリカ合衆国、北アメリカ、南アメリカ、アジア、
ヨーロッパ、中東、アフリカ、オセアニアの８地域に分類
Global Knowledge Graphの問題
同じサイトの異なるURLの記事は異なる記事とし
て判定
– 多くの場合、以下のようなURLで、内容は同じ
• http://サイト名/分類１/記事名
• http://サイト名/分類2/記事名
– このような記事については、代表URLを１つだけとっ
て、１記事として利用
記事データベースの構築
２０１３年４月１日から２０１３年１２月２５日のデー
タを利用して分析
地域ごとの記事数の分布（国名が分類できなか
ったものは、分類不能と判定）
– 総記事数：11,177,775件
– 38%の記事は国名の分類に失敗
地域
記事数
地域
アメリカ合衆国
2,933,282 アジア
ヨーロッパ
1,258,470 中東
記事数
1,295274
343,462
アフリカ
392,768 オセアニア
383,462
北アメリカ
254,204 南アメリカ
35,552
分類不能
4,280,168
分析の事例（注目話題の比較）
分析の事例（注目期間の比較）
Nawaz Sharif(パキスタンの首相)
分析の事例（関連人物）
分類の事例（多観点分析）
検索条件
地域の時間遷移
国名の時間遷移
人名の時間遷移
賛否の時間遷移
人名
nawaz sharif
期間：
2013/4/1以降
分類の事例（多観点分析）：各国比較
検索条件
全体の賛否
国名=インドの賛否
人名
nawaz sharif
期間：
2013/4/1以降
国名=パキスタンの賛否
国名=アメリカの賛否
分類の事例（多観点分析）：検索語の追加
検索条件
地域の時間遷移
国名の時間遷移
人名の時間遷移
賛否の時間遷移
人名
nawaz sharif
期間：
2013/4/1以降
人名(追加)
Imran khan
考察
従来のNSContrastと比較して、大量の記事を利
用して、世界中の動向を分析可能
データについての問題点
– サイトの所属する国の判定精度の向上
– ニュース記事のタイトルの情報を追加
現時点では、記事検索をしても、実際のURLにアクセ
スしないと意味を理解しづらい。
まとめ
NSContrastとGDELTを紹介し、GDELTデータを
NSContrastで利用する方法を提案した。
大規模な情報を用いることにより、従来と比較し
て、広範囲の記事を用いた分析が可能となった。
今後は、データの利用方法について、さらなる検
討を行う必要がある。
Top-N 形式概念に基づく
タグ情報を用いた楽曲クラスタリング
北海道大学工学部
情報エレクトロニクス学科
情報理工学コース
大久保 好章・原口 誠
膨大な楽曲データ(1/2)
飽きた曲
お気に入りアーティスト
好きな曲
整理整頓
期待外れ
膨大な楽曲データ(2/2)
検索
整理整頓
楽曲クラスタリング(1/2)
クラスタリング
クラスタリング
クラスタリング
クラスタリング：似たもの同士にグループ化
楽曲クラスタリング(2/2)
(ジャンルを超えた)意外な
共通性の認識
新たなお気に入り
アーティストの開拓
検索結果
形式概念分析に基づく
楽曲クラスタリング
クラスタリング：似たもの同士にグループ化
如何なる意味で類似？
楽曲クラスタの解釈は極めて感覚的
明確な説明を与えるのは困難
形式概念分析により明確な説明を与える
形式概念としてのクラスタ
形式概念分析(Formal Concept Analysis)[Ganter;99]
の枠組みでクラスタ抽出を議論 [Haraguchi;06]
形式概念 … 個体集合 X と 属性集合 Y の組
X
Y
X ： 外延(個体集合 ）
Y ： 内包( 属性集合 )
※ X 中の個体が共有する属性の集合は Y である．
※ 属性集合 Y を有する個体は，X 中の個体以外にない．
形式概念としてのクラスタ ：
クラスタ(外延)を内包の言葉で明確に解釈可能
形式概念(Formal Concepts) (1/2)
E = ψ・φ : 固体集合→固体集合
Closed
{ 1, 2, 3, 4 } ψ
E
{ 2, 4 }
φ
{ b, e }
I = φ・ψ : 属性集合→属性集合
φ
{ 1, 4, 6 }
a, b, c, d, e, f
2
b, c, e
3
b, e
4
a, b, d, e, f
5
b, d
6
a, d, f
7
c, d, f
{ a, d, f }
I
ψ
1
{ a, f }
Closed
E, I … 閉包演算子
形式概念(Formal Concepts) (2/2)
形式概念 : ( E(O), φ(O) )
あるいは，(ψ(A), I(A) )
{ 1, 2, 3, 4 } ψ
E
{ 2, 4 }
φ
{ b, e }
外延(extent)
内包(intent)
1
a, b, c, d, e, f
2
b, c, e
3
b, e
4
a, b, d, e, f
5
b, d
6
a, d, f
7
c, d, f
形式概念 : ( { 1, 2, 3, 4 }, { b, e } )
1, 2, 3, 4 の共有属性は b, e であり，かつ，
b, e を有する固体は 1, 2, 3, 4 以外にない．
形式概念束 (Formal Concept Lattice)
( 1234567, φ )
( 12345, b )
( 14567, d )
( 1234, be )
( 127, c )
( 1467, df )
( 145, bd )
( 12, bce )
( 14, abdef )
( 1, abcdef )
( 146, adf )
1
a, b, c, d, e, f
2
b, c, e
3
b, e
4
a, b, d, e, f
5
b, d
6
a, d, f
7
c, d, f
( 17, cdf )
( X’, Y’ )
⇔
( X, Y )
X ⊆X’ かつ Y’ ⊆ Y
形式概念に基づく Top-N クラスタ
内包評価値：制約条件(共有属性数が一定以上)
外延評価値：目的関数(できるだけ大きな外延)
求めるべきクラスタ(形式概念)：
内包に関する制約を満たすものの中で，
外延評価が上位 N であるクラスタ．
※ ある度合いの品質が保障された上位 N のクラスタ
クリーク探索による
Top-N クラスタの抽出
Top-N 形式概念抽出をクリーク探索で実現
内包制約を考慮した重み付き無向グラフにおけ
るクリーク探索
効率的な深さ優先分枝限定探索
高速な最大クリーク探索アルゴリズム MCQ
[ Tomita 03 ]の拡張
形式概念の性質，および，クリークの性質を利用
した枝刈り規則
タグ情報を用いた
形式概念クラスタ抽出
Million Song Dataset [T. Bertin-Mahieux; 2011]
100万曲の楽曲データ
音楽情報検索のベンチマークデータ
各楽曲を55の属性で表現
タイトル，アーティスト，発表年，国，
クロマベクトル(信号処理後のデータ)，etc.
Last.fm 提供のタグ情報
音楽好きユーザーのための SNS・インターネットラジオ
ジャンル，雰囲気，楽曲の特徴，etc. のタグ付け
楽曲タグ情報データ
楽曲データ
タイトル・アーティスト：個体
タグ情報(タグのリスト)：属性
楽曲総数：9330
Beautiful, Love, Rock, Awesome, …
Million Song Dataset の一部
タグ総数：33354
抽出クラスタ例(1/2)
外延(楽曲クラスタ)
Radiohead：Subterranean Homesick Alien
Snow Patrol: Chocolate
Snow Patrol: Chasing Cars
Maroon 5: She Will Be Loved
Maroon 5: Sweetest Goodbye
3 Doors Down: Here Without You
Howie Day: Collide
内包(共有属性)
Beautiful, Love, Male_Vocalists, Pop, Amazing,
Mellow, Emotive_Hardcore, Sad, Chillout,… (21)
抽出クラスタ例(2/2)
外延(楽曲クラスタ)
Rihanna, Don't Stop The Music
Britney Spears, Break The Ice
Beyonce, Single Ladies (Put a Ring on It)
Chris Brown, Forever
Lady Gaga, Poker Face
内包(共有属性)
Love, Pop, 00s, Awesome, Energetic, American,
Party, Dance, USA, Catchy, Fun, … (20)
まとめと課題
Top-N 形式概念に基づく楽曲クラスタ抽出
Last.fm 提供のタグ情報を用いた楽曲クラスタ抽出
楽曲コンテンツ(音に関するデータ)を用いたクラス
タ抽出
インタラクティブな楽曲推薦
End
情報理工学入門
20150526 A21
知識ベース研究室
主題別主題別科目
科学・技術の世界：ロボットは感情を持つか
ーロボット（人工知能）は学べるか？
変わるもの変わらないもの．
変わらないものが多分多いであろう．だとすると，
変わった部分をコントラスト法で高速にマイニングできるハズ …
レポート
• ４００字程度のレポート（出欠を兼ねる）
• 分量が増える分には構わない．
• 提出場所: ＩＳＴ棟６Ｆ 6-03 室ドアに設置したレポートボックス
• 本日の資料（ＰＰＴ）は
http://www-kb.ist.hokudai.ac.jp/~mh-j/csit-mh.pdf
（本日の夜までにアップしておく）
そもそもグラフデータ or 共起グラフ等の場合１
地方票
党友
落選議員名
健闘
etc.
全国の新聞記事
2006年9月の選挙において、ある政党の議員が
全国的には圧勝であったが、北海道では別の政
党の議員も健闘していたという記事が見られた。
Lsim = D −1/ 2 L D −1/ 2 = D −1/ 2 ( D − W ) D −1/ 2
λ1 0
V ' LsimV = V = (v1 ... vn )
グラフラプラシアンで
0 λ
n
D
距離空間に射影（次元縮
v / d v / d
約）し，そこでのクリーク
(v ... v ) =
v / d v / d
（独立集合）を見つける
11
1
1k
1
n1
n
nk
n
−1 / 2
1
k
北海道の新聞記事
2012/4/4 –
2012/4/6
…
…
ある施
設の再
稼働
…
…
…..
…
…
ある政党
の議員
…
…
…
…
グラフにおける変化の検出２
2012/4/13 –
2012/4/15
Before で（疑似）独立集合
After で （疑似）クリーク
両制約を満たす頂点集合の検出・列挙
「統合グラフ」における疑似クリーク検出
外部への接続性： 単調評価関数も利用
疑似クリークとしては k-Plex
自己を含めて未接続数は高々 k 個
クリーク同様の単調性と枝刈
(重複クリークを無駄なく列挙する)
同時制約のために，k が小さいときは高速
しかし，k-Plex を使った研究は多くない
文書要約・理解
• 文書の全体像把握に向けた重要文抽出のために
概要をつかむための視点を追加
猪が国を荒らしました。
文書は複数の話題から構成
誰も猪のいる森には入りませんでした。
森
猪
森 王様は猪を倒すように頼みました。
兄と弟は森を探しました。
森
兄・弟
兄・弟
単語による文の関係
兄は弟の命を狙っていました。
話題
兄は弟を襲いかかりました。
話題間の構造
橋
兄は弟の遺体を橋の下に埋めました。
ひとりの羊飼いが歩いていました。
羊飼い
羊飼いが橋で骨を拾いました。
橋
話題をつなぐ役割に重要度
文脈語
羊飼いは骨で笛を作りました。
橋
シーンへの分節化（セグメンテーション）
1
2
3
4
5
6
7
A
A
A A
B B
B
B
C C
C C
D
D
E
E E
F F
F F
k =3
Point to compare the
left and right k
sentences
類似度
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
2
4
6
8
10
12
基準点
出現する単語の出方（パターン、分
布）が位置により変化する。同じ話題
の中では、その変化は少なく、異なる
話題・シーンへ移ると、その変化は極
大化 （類似性極小）
文脈的な言葉： トピックを繋ぐ
トピック：中心語彙群：…
兄と弟のシーン
w1
兄と弟は森を探しました。
兄
兄は弟の命を狙っていました。
兄は弟を襲いかかりました。
兄は弟の遺体を橋の下に埋めました。
中心的な役割を演じ
るもの、人、で、相互
に共起しあう語彙群
w2
弟
共起グラフにおけるクリー
ク（密結合な部分）
目立たない語もシーンを繋ぐことがある
場所，文脈等を表す言葉は，省略されることが多い
シーンの最初で述べておけばわかる．．．．
OR 次のシーンに移動する前に一言述べておく ．．．
多くの中心語彙と結合される、
中心語彙ではない言葉
猪 －森 －兄・弟
兄・弟 －橋 －骨(笛)
猪が国を荒らしました。
猪
誰も猪のいる森には入りませんでした。
森
森 王様は猪を倒すように頼みました。
兄と弟は森を探しました。
森
兄・弟
兄・弟
兄は弟の命を狙っていました。
兄は弟を襲いかかりました。
話題連結語 （キーグラフ）
キーワード： 中心語彙群と話
題連結語の２種類
橋
兄は弟の遺体を橋の下に埋めました。
ひとりの羊飼いが歩いていました。
羊飼い
羊飼いが橋で骨を拾いました。
橋
羊飼いは骨で笛を作りました。
橋
マルコフ連鎖による、確率的重要度の付与： PageRank モデル
近
接
性
の
重
み
兄、弟、森
共起語を介して、文から文
へ渡り歩く： マルコフ過程
兄、弟、橋
q = (1 − α )Mq + αp
猪が国を荒らしました。
猪
誰も猪のいる森には入りませんでした。
森
森 王様は猪を倒すように頼みました。
兄と弟は森を探しました。
森
兄・弟
兄・弟
兄は弟の命を狙っていました。
羊飼い、橋、骨
話題連結語を含む文に一
定の重要度を与える
骨、王、歌う
兄は弟を襲いかかりました。
橋
兄は弟の遺体を橋の下に埋めました。
ひとりの羊飼いが歩いていました。
羊飼い
羊飼いが橋で骨を拾いました。
橋
羊飼いは骨で笛を作りました。
橋
新聞社説の要約： 文脈語の重要性
圧縮率 12/33 = 36 %
2.
8.
会談では，○○半島の恒久的平和体制の確立が，
主要議題になる．
これを平和の状態に変えるには
「平和協定」の締結が不可欠だ．
感情の身体表現
モーション
データベース
標準動作
重たい気分で歩いていた。
悲しさ、憂鬱さの身体表現
体がだるいとき、膝を痛めたと
きも、外形的にはそうなる。
変換
「歩く」
動作データ： real robot と同じ座標系
• 動作データ M はフレームF i の列 1
M = ( F ,, F ,, F )
i
F = { p ,θ ,,θ }
i
i
0
i
1
j
K
i
22
pelvis
j+1
• Pi0: 腰の基本座標系に関する位置
• Θij: 関節jの方向（体節の姿勢： 相対座標系）
• 間節（に筋肉駆動のモータがついていたとして、力やトルクの値を、座標系
列から計算できる ： ロボット工学における動力学）
F1
F2
Fi
状態列とエネルギー,実コスト
d
W = P = Fv
dt
t2
W = ∫ Fvdt
t1
関節を動かしたときに生じる
力： Newton-Euler 法など
体節の動きは隣接した体節
に影響を及ぼし …
コスト： 仕事量： エネルギー使用量
コストは，状態系列（力，速度）を時間に関して足しこむ
（トルク，角速度）
人工知能を用いたモーションプランニング
標準的な動作
負荷のかかる（たくさんのエネルギーを要する）関節に対して、負荷分散すべく、
隣接した関節を少しづつ動かし、負荷分散に寄与する動作系列があればそれを挿入する
F1
例：
膝のコストが最大
g(F0 ,F1)
見積もりコスト： 体節の相互作用を無
視した近似的なコスト
h(FV,F1)
実コスト
Fｖ
腰を曲げる
F0
g(F0 ,FV)
If g(F ,F ) > g(F , F ) +h(F ,F )
0
1
0
V
V
1
FVを経由状態の候補とする
筋骨格系パラメータが異なる場合に適用
標準キャラクタ Ｓ
強度パラメータを
変えた場合の処理： 強い
人はそれなりに、弱い人
もそれなりに ….
膝への負荷をかけたくないとき，
背筋を伸ばして歩く人はない．
膝の弱い人
各部は繋がっている ….
目標キャラクタ Ｔ
悲しげに、重たげに
見えるだろうか ….
まとめ
• 感情の身体表現の可能性（認知的には重要だが、情報処理技術として
は未発達。要素技術・理論： ロボット工学。ヒューマノイド工学、３Ｄ表
現）
• シナリオ、要約の可能性（言語処理の中心課題。現在進行中。要素技
術・理論： 計算言語学、グラフ理論、データマイニング，機械学習）
• シナリオ、要約に基づき、アニメーション表現する可能性（開発途上。試
験的研究はあるが、これといった決定版は未だない