Active Document Layout Synthesis [Lin, 2005]

Active Document Layout Synthesis [Lin, 2005] を読みました。
論文は http://www.hpl.hp.com/techreports/2005/HPL-2005-106.html から読むことができます。

前回の記事に引き続き、Document Layoutの自動生成についての論文です。
形式も前回の記事を踏襲していきます。

[Abstruct]

• 文書レイアウト解析は長年研究されているが、その逆である文書レイアウト合成はあまり研究されていない
• テキストブロックの高さと幅のトレードオフを最適に調節するようなレイアウト合成方法を提案する

[1. Introduction]

• 文書レイアウト解析 (Documet Layout Analysis, or DLA) では、まずテキストブロックの場所を特定し、その後各ブロック内の単語をOCRで認識する
• DLAの逆のタスクである文書レイアウト合成 Documet Layout Synthesis, or DLS)も面白いのではないか
• 文書のテキストと画像が与えられた時、それらを含むブロックの適切なサイズや位置はどのようなものか？
• DLSの目標は論理的に正しく(logically correct)、綺麗な見た目(aesthetically appealing)のレイアウトを作ること
• 先行研究([Jacobs et al., 2003], [Badros et al., 2001])では、テキストブロックの幅は固定 or テンプレートで決まる
• 提案手法では、ブロックの幅は固定しない。テンプレートは相対的な幅だけを定義する。

[2. Multi-linear Text Modeling]

• ページにn個の矩形ブロック B1, B2, ..., Bn があるとする
• S(Bi): Biの幾何学的性質（e.g., 高さや幅）
• P(Bi): Biの左上の角
• S(Bi)を固定する場合 (passive DLS) は、P(Bi)のみを調整してlayout quality functionを最適化すればよく、シンプレックス法で解ける
• 論文中でのlayout quality functionの具体的な実装については4章を参照
• S(Bi)も調整する場合 (active DLS) の難しさは、高さと幅の関係の非線形性にある
• ブロックの幅を連続的に狭くしていくと、ある時行数が増え、ブロックの高さが一気に（一文字分）増えるので、横軸に幅、縦軸に高さを取ると、幅と高さの関係は階段状になる（Figure 3）
• そこで、まずはシンプレックス法が使えるようにするため、高さと幅の関係を多重線形制約条件でモデル化する
• 経験上、高さ(h)と幅(w)の関係は双曲線関数のように振る舞い、レンダリングエンジンのデータなどをもとにすると h = k/w + b と表せる。ただし、k = 8360.6, b = -1.04
• 双曲線上にいくつかのサンプリングポイントを置いて、双曲線をカバーするような直線群を求める(Figure 4)

[3. Two-pass Constraint Solving]

• 2章にて幅と高さの関係を多重線形モデルに落とし込んだので、シンプレックス法が使える
• パラメタは各ブロックの幅、高さ、左端、上端
• レイアウトは2ステップで計算する
• i) 各テキストブロックの最適な幅をシンプレックス法で計算する　→　line-breakingをしてブロックの高さを得る
• ii) テキストブロックの高さと幅を固定してもう一度シンプレックス法を実行することで、各ブロックの最適な位置を得る

[4. Experimental Results]

• 実験で用いたテンプレートが要求する条件：
• 1) B2はB1の右側にある
• 2) 画像ブロックB1とテキストブロックB2の高さは同じ
• 3) B3の高さと幅は同じ
• 4) B3, B4, B5はB1, B2よりも下にある
• 5) B3, B4, B5の上端は揃っている
• 6) B3とB6は垂直方向に並んでいる (horizontally aligned)
• 7) 画像はアスペクト比が崩れないようにスケーリングできる
• 8) コンパクトなページを目指すため、全てのブロックが占めるスペースの高さを最小化する (これが2章で触れた layout quality function ですね)
• Figure 5, 6にこの手法を適用する過程が示されています

[5. Application to Table Formatting]

• Table Formatting とは、文書中の表のグリッドと内容が与えられた時に、表の各セルのサイズを決定する問題
• 今回のactive DLSの手法がTable formattingに応用できる
• 表をXML形式で記述する
• XMLの記述から制約条件を抜き出してテンプレートを作る
• active DLSの手法を適用する

[6. Conclusions]

5章までを簡単にまとめた感じなので省略します。

こんな感じでしょうか。シンプレックス法とか細かいこと忘れてたので思わずググってしまいました。

授業で習った時も嫌いだったなーこのあたりは…なんて思いながら…。

前回の記事の論文でも言えることですが、手法のしっかりとした評価がされていませんね。

私も文書レイアウトをするようなアルゴリズムを考えてみたいのですが、その際にそのレイアウトがどれほど良い物なのかを定量的に評価する方法は無いものでしょうか。

Adaptive Grid-Based Document Layout [Jacobs et al., 2003]

Adaptive Grid-Based Document Layout [Jacobs et al., 2003] を読みました。

論文は http://dl.acm.org/citation.cfm?id=882353 から読むことができます。

この論文は、文書のレイアウトを自動で生成しようという旨の論文です。

10年近く前の論文で、内容を解説している日本語のブログ記事も存在していました。

（言語ゲーム：http://d.hatena.ne.jp/propella/20070212/p1）

今回は、私自身が論文の理解を深める意味を込め、私なりに論文を流れに沿って簡単にまとめていこうと思います。

各章の内容を箇条書きで書きなおしているだけで、流れなどがわかりにくいかとは思いますが…。精進します。

[Abstruct]

• グリッドベースの文書デザインは広く使われているが、グリッドベースの文書を任意のサイズのディスプレイ向けに自動でデザインする方法はまだ存在していない

[1. Introduction]

• グリッド(grid)とは、印刷された文書のページ内で順序付けするためのシステムである
• グリッドベースのデザイン(grid-based design)は、新聞や雑誌などで広く使われている
• grid-based designを様々なサイズのディスプレイに綺麗に表示させる方法は今のところない (雑誌などは、決められたサイズの紙面に綺麗に印刷されれば良い)
• ページの各要素（テキスト、画像、サイドバーなど）をグリッドにマップするのは手作業で行われる
• 横長の紙だったらサイドバーは右に表示すればよいが、横幅が狭く縦長の紙であったらサイドバーはページを圧迫しないように下などに表示すべきである
• grid-based designは文書の再描画ができない
• HTMLやTeXなどは文書の再描画が可能だが、文書を一次元の流れとして扱っている
• この論文では、以下のようなアプローチでgrid-based design の再描画を可能にする
• テンプレートの集まりであるスタイルを用意し、各スタイルに文書の中身（テキストや画像など）を貼りつけていくイメージ
• このテンプレートは、ディスプレイのサイズや文字サイズなどが変わっても綺麗に表示されるようにデザインされる
• そのために必要なもの
• テンプレートの表現方法
• レイアウトエンジン
• Pagenator
• テンプレートをデザインするためのツール

[2. Related work]

省略します。

[3. Representation]

• 文書の内容と表示スタイルは分けて考える。
• スタイルは、テンプレートのレイアウトとスタイルシートに分けて考える

3.1 Document content

• 文書の内容は、ストリーム（続けて表示されなければならない要素で構成される）の集合として表現する
• ストリームは<atom>タグを用いた入れ子構造も可能
• レイアウトエンジンやテンプレートにコンテンツがどのように使われるかを知らせるための attribute も指定可能
• 例: "importance" attribute
• <multi>タグを用いると、コンテンツのいくつかのバージョンを指定することができる
• 例: <multi>タグをでテキストが要約されたものを指定しておくと、小さいディスプレイには要約バージョンが表示される

3.2 Templates

• ページテンプレートは要素、制約、前提条件から成り、各ページのレイアウトを指定する
• 要素: コンテンツが置かれる位置を矩形で指定したもの。一つのストリームが複数の要素にまたがった場合はフローが生じ、複数の要素が重なった場合は、ある要素を回りこむように他の要素が配置される。
• 制約: 要素間の位置関係を制限する制約。
• 例: タイトルと本文があるテキストなら、タイトルは文書の最初に表示されなければならない
• 制約の実装方法は"3.2.1 Constraints"で触れられています。興味の有る方はそちらを読んでください。
• 前提条件: テンプレートが使えるための条件。
• 例: このテンプレートが使えるのは、図が2枚とページサイズがA4からU.S.-letterサイズの時のみ
• ページテンプレートを集めたものをレイアウトスタイルと呼ぶ

3.3 Style sheets

• 太字などの修飾ができるように、CSSに似た言語を提供

3.4 Bringing it all together

• Document content, templates, stylesheetsの3つがpaginatorの入力となり、実際にページがレンダリングされる

[4. Layout]

• レイアウトエンジンは、コンテンツ、テンプレート、スタイルシートを受け取って、ページのレイアウトを羅列する
• まず、各テンプレートの前提条件を見て、使うことのできるテンプレートセットを羅列
• 次に、各テンプレートに対し、要素のサイズや位置などを決める

4.1 Flowing into elements

• コンテンツを矩形領域にどう流し込むか
• 画像は、単純にリサイズして矩形に収まるようにする
• テキストはKnuth and Plass's optimal line-breaking algorithm を使って矩形領域に流しこむ
• アルゴリズムは Breaking paragraphs into lines [Knuth and Plass, 1989] 参照。私もまだ読んでないのですが、読んだら記事にするかもしれません。

4.2 Self-sizing elements

• 要素の矩形領域の高さは自動で調節する。画像の場合は画像のアスペクト比を参考に調節。テキストの場合は、最初は高さを最大にして流し込み、矩形領域が余ったら高さ減らす。両方が組み合わさったコンテンツの場合はtemplates.outheightなる値を使う（？）。

4.3 Template scoring

• ページエンジンは各テンプレートに対して、どの程度コンテンツがテンプレートにフィットしているかを示すスコアを計算する
• paginatorは全てのページについての各テンプレートのスコアを受け取り、一番良いテンプレートの並びを計算する

[5. Pagination]

• Paginationとは、文書のストリームから、各ページにコンテンツをマップするタスク
• ページへの割り当てを決める際に、その割当がどの程度"良い"のかを決める指標が欲しい
• 例: 文書を通して読む際に、 （文書の続きを読んだり、本文中で参照されている図などを見るための） ページめくりの回数が少なくなるようにしたい

5.1 Original algorithm

• nページのpaginationの最適解は、最初のn - 1ページのpaginationの最適解に依存する　→　動的計画法が使える
• 今回の手法では、イテレーションの中で制約を解消するために多くの計算が必要になるので、従来の動的計画法はそのままでは使えない

5.2 Our algorithm

• 重要なところなのに理解できていないです。すいません…。

5.3 Analysis

• ページめくりの指標を使って、良いpaginatorができたという話だと思います。（ここはあんまりちゃんと読んでいません）

[6. Authoring templates]

• ディスプレイのサイズが変わるとどう表示されるかを考えながらテンプレートを作るのは難しいので、それをサポートするツールを作成した

6.1 Creating and arranging layout elements

• 要素の位置は様々なサイズの画面に対応できるように相対位置で指定
• 要素のリサイズに対応できるように、制約は1次元的に指定（e.g., 高さは指定せず、幅だけを指定する）

6.2 Template selection

• テンプレートの前提条件は、要素に関連付けられているストリームから自動的に計算される（どういうこと？）
• ダイアログボックスを使って前提条件を追加できる
• 要素にattributeを追加できる → テンプレートのスコアに影響

[7. Results]

• 論文は、提案手法を用いてデザインされている
• 文書はMicrosoft Wordからマクロを使ってマークアップフォーマットに落とし込んだ

[8. Conclusion and future work]

• コンピュータでのリーディングが盛んになってきているが、グリッドベースでの文書デザインには様々な環境にどう対応するかという問題があった
• 今回の論文は、その問題に対する最初の一歩

以上。

だらだらと書いてしまった上に、ところどころ理解が甘かったりでもう…。

というか、未だに全体の流れもちゃんとつかめていません。この処理は全体でどういう処理になるんでしょう。

マークアップ形式で書かれたコンテンツ（テキストやらイメージやら）があるとします。テンプレートも予め用意しておく。

その後にどのページにどのコンテンツを割り当て、どのテンプレートを使う、という候補を洗い出し、スコアを付けておく（4章）。

その後、ページ割り当ての指標や、テンプレートのスコアを参考にして、実際にコンテンツを割り当てるページとレイアウトを決める（5章）。

っていう流れでいいんですかね…？

「どのページにどのコンテンツを割り当て、どのテンプレートを使う、という候補を洗い出し、スコアを付けておく」って部分が、具体的にどんな処理をしてるのかよくわからないです。書いてあります？自分の英語力が足りてないだけな気もしますが…。

いきなり私の頭の足りなさを露呈する形になってしまいましたが、今回はこれにて。

省略した部分や、理解できていなかった部分が分かった場合は、後日追記する可能性もあります。

講演「Wikipediaマイニング」を聴いてきました

東京大学知の構造化センターの中山浩太郎特任助教による「Wikipediaマイニング」という講演会に参加してきました。

Wikipediaに蓄積された知識をどのようにして利用するかというようなお話でした。
私が理解した範囲で、印象に残った箇所のみ簡単にまとめておきます。
理解が間違っている箇所もあるかもしれないので、あまり内容を当てにしないでください。

Wikipediaをリソースとして利用する利点は講演でたくさん挙げられていたのですが、主なものとして次のようなものが挙げられていました。

・データ量が膨大である
・半構造化された知識が蓄積されている
・URLにより概念が一意に定まる

・密なリンク構造が存在している
・アンカテキストの質が高い

Wikipediaのデータ量が膨大である点は言わずもがなだと思います。

半構造化された知識、というのは、Wikipediaの各ページはTitle, Infobox, Categoriesなど、ある程度構造化された状態で知識が保持されている、という意味です。

3つめのURLにより概念が一意に定まる、というものは、例えば "Apple" という単語は現実世界では曖昧性がある（果物のリンゴを指すこともあれば、Mac OSを販売している企業を指すこともある）が、Wikipediaの場合は同じAppleの場合でも、指すものが違う場合は異なるページが用意されており、URLから何を指すのかを区別できる、という利点です。
途中で挙げた Apple の例であれば、
果物のリンゴ：http://en.wikipedia.org/wiki/Apple
企業：http://en.wikipedia.org/wiki/Apple_Inc.
というように、同じAppleに対しても異なるURLで記事が用意されています。

密なリンク構造と、最後のアンカテキストについては密接に関連していると思うのですが、Wikipediaは記事間に多くのリンクが存在しています。
URLにより概念は一意に定まるので、このリンクから成るネットワークは概念間のネットワークと捉える事ができ、それをうまく使うことが出来るのではないか、ということでした。
また、そのリンクを貼る際には、何かの文字列にリンクが貼られる（例えば Apple という文字列に対して http://en.wikipedia.org/wiki/Apple_Inc. というURLへのリンクが貼られる）のですが、その文字列も有効に使えるのではないか、とのことでした。

あるページへのバックワードリンクが、どのような文字列に対して貼られているか（どのような文字列のリンク先が、"あるページ"になっているか）を解析すると、URLによる概念の一意性より、ある概念を指す様々な表現を得ることができます。
これは、類義語を探すのに役立つとのことでした。表記ゆれのデータベースなんかもこれから作れそうですね。


このような背景をもとに、中山さんが今まで携わってきた研究をいくつか紹介していただきました。
詳細は省略させて頂きますが、連想シソーラス(http://dev.sigwp.org/WikipediaThesaurusV3/)や、翻訳辞書(http://dev.sigwp.org/WikipediaBilingualDictionary/)、Wikipedia API(http://sigwp.org/en/index.php/Wikipedia_API)などを紹介して頂きました。
触っていみると結構面白いので、みなさんも是非触ってみてください。


もう一つ大きな話題として、MIGSOMというものを紹介して頂きました。
脳科学の分野で知られている神経細胞移動を応用して、クラスタリングのアルゴリズムを作れないかというものでした。

私は脳科学は全くわからないのですが、どうも脳の神経細胞というのは自ら動いて最適な場所を見つけ出すらしいです。
脳のしわというのは、この移動による張力によって出来るらしいですね。全然知らなかったです。
このような細胞が自ら最適な場所を動いて探す、という仕組みをクラスタリングに応用できないかという発想で考えられたアルゴリズムがMIGSOMです。
フィーチャーとしては、先程少し触れたリンク構造や、アンカテキストなどを使っているとのことでしたが、詳細は私もわからないので、興味の有る方は各自調べてください…。
講演では、Wikipediaの各ページを2次元の座標上に落としてMIGSOMを適用した結果が紹介されていました。
スポーツに関するページはスポーツで関するページごとに集まったり、都市に関するページは都市に関するページなどで集まったり、といった様子が見て取れました。

以上、簡単ですが、こんな感じで今後も忘備録を書いていければと思っています。

ブログ開設

ブログ開設しました。

この春から大学院に進学します。

これからは論文を読む量や、講演会等に参加する機会も増えるのではないかと思うので、それらの忘備録にでもなればと思っています。

自然言語処理系の研究室に配属してもらっていますが、まだ自然言語処理は素人です。

早く勉強して人並みになりたいですね。。