Extracting Relevant Snippets from Documents through Language Model based Text Segmentation Web Intelligence, 2009 Qing Li, K. Selcuk Candan, Yan Qi ( Oct.15,2010, 柳 沢 担 当 )
目 的 言 語 モデルを 用 いたSnippetの 抽 出 方 法 提 案 文 書 から 適 切 な 文 の 抽 出 RELEVANCE LANGUAGE MODELS 言 語 モデルの 利 用 Curvature analysis 曲 線 からのテキストセグメント
関 連 研 究 TextTiling 法 [Hearst,1997] 領 域 内 における 語 彙 の 重 なり 尺 度 に 基 づく 類 似 度 により 境 界 を 決 定
言 語 モデルを 用 いたアプローチ RELEVANCE LANGUAGE MODELS 言 語 モデルによる 境 界 d P(w M) d w d P(w Mr) w P(w ) w snippet Non snippet
言 語 モデルを 用 いたアプローチ RELEVANCE LANGUAGE MODELS d snippet P(w ) Non snippet w collection: 全 document 内 の 単 語 の 集 合 cfw :collection 内 のwの 出 現 頻 度 coll.size :collection 内 の 総 単 語 数
言 語 モデルを 用 いたアプローチ RELEVANCE LANGUAGE MODELS 仮 説 : snippet 内 の 単 語 の 出 現 確 率 はqueryの 共 起 確 率 と 類 似 [Lavernko] クエリ q={q1,q2,q3 qk}を 用 いて P(w Mr)をP(w ( q q1,q2,q3 qk)で q 近 似 d Mr P(w Mr) snippet w Mrはクエリによるドキュメントの 集 合 から 抽 出
言 語 モデルを 用 いたアプローチ RELEVANCE LANGUAGE MODELS 手 順 1. クエリq で 上 位 ランキングされたページRqを 取 得 2. 与 えられたDocumentの 単 語 出 現 確 率 p(w d)を 計 算 Pml(w d):ドキュメント 内 での 単 語 wの 出 現 確 率 Pbg(w):スムージングのため 3. P(w Mr)をP(w Rq)で 近 似
言 語 モデルを 用 いたアプローチ SNIPPET EXTRACTION CUTS[Yan2006] [ ] Blogのトピックセグメンテーション i 日 目 とi+1 日 目 のEntry 間 の 類 似 度 の 差 に 応 じてトピックが 変 わったか 判 断 Entry : blog ページから 一 日 分 の 記 事
言 語 モデルを 用 いたアプローチ SNIPPET EXTRACTION CUTS[Yan2006] [ ] Blogのトピックセグメンテーション» Step1: 各 Entry 内 に 含 まれるキーワード 単 語 の 重 みづけ» Step2: 各 Entry 間 で 非 類 似 度 Dを 取 得 今 回 は 時 系 列 (Straight line)
言 語 モデルを 用 いたアプローチ SNIPPET EXTRACTION CUTS[Yan2006] [ ] Blogのトピックセグメンテーション i 日 目 とi+1 日 目 のEntry 間 の 類 似 度 の 差 に 応 じてトピックが 変 わったか 判 断 Entry : blog ページから 一 日 分 の 記 事 連 日 で 同 じトピックを 書 いていると 想 定?
言 語 モデルを 用 いたアプローチ SNIPPET EXTRACTION 今 回 トピックセグメンテーション» Step1: 文 内 のキーワード 単 語 の 重 みづけ» Step2: 文 内 での 非 類 似 度 Dを 取 得 今 回 は 時 系 列 (Straight line)
言 語 モデルを 用 いたアプローチ 曲 線 における 変 動 のセグメンテーション 理 想
言 語 モデルを 用 いたアプローチ 曲 線 における 変 動 のセグメンテーション 理 想 近 似 値 を 用 いた 確 率 モデル
言 語 モデルを 用 いたアプローチ Curvature analysis[y.qi,2006] 曲 線 の 傾 きに 応 じたセグメンテーション Dminated: 比 較 的 水 平 部 分 Drifting: 傾 いている 部 分 (セグメント) Interrupted: 一 時 的 な 遮 断 部 分 Case1: 近 似 による 一 時 的 な 遮 断 Case2:Drifting 部 分
言 語 モデルを 用 いたアプローチ Curvature analysis[y.qi,2006] 曲 線 の 種 類 Dminated: 比 較 的 水 平 部 分 Drifting: 傾 いている 部 分 (セグメント) Interrupted: 一 時 的 な 遮 断 部 分 Case1: 近 似 による 一 時 的 な 遮 断 Case2:Drifting 部 分
言 語 モデルを 用 いたアプローチ Curvature analysis[y.qi,2006] 一 時 的 な 遮 断 部 分 とDrifting g 部 分 の 区 別 e1からe4 間 での 傾 き 方 で 区 別 s1の 線 について 定 義
言 語 モデルを 用 いたアプローチ Curvature analysis[y.qi,2006] Adaptive curve segmentation[david.g,1987] プログラムコードの 効 率 的 に 処 理 するためセグメント 端 から 端 まで 線 において 垂 線 が 最 大 となる 点 を 取 得 上 記 で 得 た 点 から 端 まで 線 を 引 き 同 様 に 点 を 取 得 セグメント( 線 ) 間 の 点 が 与 えられた 数 (MinSpan)になるまで 同 様 な 作 業 を 繰 り 返 す セグメント( 線 ) 間 の 点 が 与 えられた 数 (MinSpan)になるまで 同 様 な 作 業 を 繰 り 返 す ( 上 記 の 例 :MinSpan=1) 最 初 から 点 iと 点 i+2で 線 を 引 けば 一 緒?
言 語 モデルを 用 いたアプローチ Curvature analysis[y.qi,2006] それぞれの 部 分 を 傾 きにより 識 別 k: 傾 き(e) λdrifting:パラメタ 上 記 の 場 合 Interruptの 条 件 に 当 たるのは h=2
有 用 性 の 検 証 実 験 1 正 解 データとの 比 較 (preciotion, recall,f measure) 使 用 データ Internet 上 から 収 集 30 queries 一 般 によくつかわれる 名 詞 RM Curve or FS win queries ans 30 queriesに 対 してのanswers 詳 細 不 明 200 単 語 ごと 上 記 の 手 法 でセグメントを 行 い 最 も 多 くqueryを 含 む 部 分 を 選 択 RM Curve: Curvature analysis FS Win:googleの 検 索 結 果 テキストデータのSizeを 増 やしての 検 証
実 験 結 果 正 解 データとの 比 較 (preciotion, recall,f measure) 200 単 語 ごと 上 記 の 手 法 でセグメントを 行 い 最 も 多 くqueryを q y 含 む 部 分 を 選 択 Ls: 正 解 データの 単 語 の 総 数 Le: 抽 出 したSnippetの 単 語 の 総 数 Lo: 正 解 データと 抽 出 Snippetの 単 語 の 重 複
実 験 結 果 有 用 性 の 検 証 正 解 データとの 比 較 (preciotion, recall,f measure) answerのサイズ 変 更 Precision Recall
有 用 性 の 検 証 ノイズを 含 めた 実 験 実 験 2 内 容 の 異 なる2つのドキュメントにqueryを 挿 入 (ノイズ) ズ RM Curve or FS win queries ans queries queries
有 用 性 の 検 証 ノイズを 含 めた 実 験 実 験 結 果 2 内 容 の 異 なる2つのドキュメントにqueryを 挿 入 (ノイズ) ズ F 値 (Noise 考 慮 あり)
考 察 1 FM Win: Noiseが 入 ると 精 度 が 低 い RM Curve: queryに 関 する 文 脈 上 の 語 を 考 慮 可 能 Noiseの 適 切 でないセグメントのフィルタリングが 可 能
考 察 2 文 書 の 件 数 と 精 度 (F 値 ) ページRqの 理 想 の 数 文 書 は5~40の 間 が 良 い 特 に15 件 が 一 番 良 い
結 論 適 切 なスニペットを 抽 出 するモデルの 提 案 RM Curve 正 解 データとの 比 較 queryに 関 する 文 の 語 を 考 慮 可 能 Noiseの 適 切 でないセグメントのフィルタリングが 可 能
関 連 研 究 LEASED WITH YOUR GOOGLE DESCRIPTION? ( 抜 粋 ) Where is Google pulling the snippet description? Snippetの 抽 出 エリア(googleの g 話 ) METAタグ ALTテキスト( 画 像 説 明 ) 文 頭 テキスト 追 加 Headタグ 追 加 Bodyタグ 追 加 ALTタグ ナビゲーションバー( 左 隅 ) Copyright 情 報 キーワードのフレーズ
TextTiling 法
クエリとの 共 起 確 率 共 起 確 率 P(w Q) の 例 q1 q2 q3
クエリとの 共 起 確 率 共 起 確 率 P(w Q) の 例 q1 q2 q3
LEASED WITH YOUR GOOGLE DESCRIPTION? Where is Google pulling the snippet description? ( 抜 粋 ) 1. META description tag (although Google doesn t use contents to dt determine relevancy). 2. First ALT text found on the page. 3. First text found on the page pg (which may be a heading tag, body text, etc.). 4. Additional heading tags on the page. 5. Additional body text found on the page. 6. Additional ALT text on the page. 7. Navigation bar on the left hand side of the page (which is rarely a relevant description of a site!). 8. Copyright information at the bottom of the page. 9. Wherever the keyword phrase is found.
言 語 モデルを 用 いたアプローチ Curvature analysis[y.qi,2006] Adaptive curve segmentation[david.g,1987] 空 間 内 の 点 をbinary treeのデータとして 保 持