2012年11月9日金曜日

DeNA一次面接のグループディスカッション受けてきました

夏は某社のインターンに参加していたため、ブログを書くことができませんでしたが、気づけばもう就活本番の時期です。

以前の記事でインターンの際の一次面接を書かせていただきましたが、今回はそのリベンジ?ということで新卒採用の一次面接を受けてきました。

インターンの選考を受けている人は、以前通ったステップに関しては免除されるようです。
僕の場合はWebテストを通って一次面接で落ちたので、今回も一次面接から。
知り合いの話を聞いていると、二次で落ちた人は二次から、三次で落ちた人は三次からスタートのようです。

で、面接の内容ですが、インターンの時とまったく一緒。
以前の記事とかぶりますが、一応詳しい流れを書いておきます。

オフィスに到着すると、空いている椅子で待っているように指示されます。
他の就活生としゃべりながら待っていると、社員さんが来て奥の部屋に通してもらえます。
そこでは、履歴書の間違い・変更点の修正と、アンケートの記入を行いました。インターンの時はこの場所でビデオを流された気がするのですが、今回はそういうのはなかったですね。

集まったのは15人弱。4~5人で構成されるグループを作り、面接の部屋に移動するまでの間、グループの人と話て仲良くなる時間があります。
ちなみに、服装は全員スーツでした。

しばらくして、小さな会議室に移動し、面接スタートです。
流れは本当にインターンの時と同じで、
  1. 自己紹介(名前、大学、学生時代頑張ったこと)
  2. ディスカッション1
  3. ディスカッション2
  4. 自己PR(テーマ:今まで経験した中で一番の困難)
  5. 質問タイム
という流れでした。自己紹介、自己PRはそれぞれ30秒ずつと言われた気がしますが、他の人を見ていると守っている人が少なかったです。

ディスカッションについて補足します。
1つ目のディスカッションは、「直前の発言を否定し、かつ新しい案を出す」というディスカッション。テーマは「○○の売上を1年間で1.5倍にするには?」というものでした。
○○に入る店の名前(飲食店が多い?)は、その場で就活生に聞いて決めるパターンが多いようです。(前回も今回もそうでした)
また、「1年間」や「1.5倍」という数字は多少変動があるようですが、全然違うテーマが出たという話は聞いたことがありません。(が、今後はどうかは知りません)
だらだら書きすぎたので、ルールをまとめると、
  • テーマは「○○(飲食店)の売り上げを1年間で1.5倍にするための手段は?」
  • 発言は挙手制
  • 発言の際は、直前の発言者の意見を否定し、なおかつ新しい案を提示しないといけない
という感じになります。

これが10~15分程度続いたでしょうか…。その後、ディスカッション2に移ります。
このディスカッションも以前の記事に書いたものとまったく同じで、「私は最近映画を見に行っていない」、「私はビールを飲むことができない」など、面接官に関する情報が与えられるので、この理由を推測するというもの。ただし、3回だけYes/No型の質問を面接官に投げることができ、持ち時間は10分。
10分間ののち、グループで結論を出した後は、答え合わせ。
その後、それぞれの人に別々の質問が飛んできました。もう一度ディスカッションをやり直せるとしたら、今と同じ方法で議論を進めますか?などです。

この後、2つ目のディスカッションに関する小さなフィードバックがありました。

いわゆる「自己分析」なことを毛嫌いしてまったく行わなかったので、自己紹介や自己PRですら話すネタがなくてあたふたしてたので、たぶん落ちました。ディスカッションでも切れのある意見が言えたとも思わないですし…。
他の人を見ていると、自己紹介になった瞬間に暗記していた文章を読んでいるかのようにスイッチが切り替わった人などもいました。そこまですることはないと思いますが、ある程度しゃべれるネタを考えておくことは必要なんでしょうね。

結果については良ければ書きます。良ければ。

2012年7月24日火曜日

LaTeXで表と本文の間のマージンのサイズを指定したい

figureやtableを [h] を使って、ソースに記入したそのままの場所に挿入した場合は \intextsep にて設定されている。
\begin{document}の前あたりに、下の行を追加すれば調整できるようになりました。

\setlength{\intextsep}{30pt}

2012年7月14日土曜日

Reading Text on a Smart Phone: Scrolling vs. Paging: Toward Designing Effective Electronic Manuals [Fukaya et al., 2011]

Reading Text on a Smart Phone: Scrolling vs. Paging: Toward Designing Effective Electronic Manuals [Fukaya et al., 2011] を読みました。
International Conference on User Science and Engineering (i-USEr) っていうカンファレンスの論文らしいんですが、このカンファレンスは聞いた事無いです。
2011年で第2回目という、新しい学会のようですね。

PCのモニタではスクロールレイアウト vs. ページレイアウトのどっちがいいの?という研究が数多くなされていますが、スマホを対象にした研究はまだそれほどなされていないので、そこにフォーカスした論文です。

1. Introduction

  • スクロールレイアウト/ページレイアウトに関する既存研究はPCのモニタに関するものが多いが、スマートフォンでテキストを読む場合はどうなのか
  • レシピやマニュアルなどの手続き的なテキストにはスクロールとページのどちらが適しているのか?
    • 手続き的な文書はWeb上ではありふれていて、スマホのようなデバイス上でより読まれるようになるだろう
  • 研究の目的は、スマホ上でのスクロールやページレイアウトがテキストの理解力、パフォーマンス、メンタルロードワークにどのように影響を与えるかを調査すること
  • 2つのタスクを用意
    • 記憶力タスク
    • 操作タスク
2. Experiment
  • 被験者
    • 12人の日本人(男性8人女性4人で、平均年齢35.3歳)
    • 5人はスマートフォンをほとんど使ったことがないが、7人は使い慣れている
  • 装置
    • タッチパネル式デバイスとしてiPod Touch 4Gを使用
    • テキストの表示には、スクロール式とページ式の場合にそれぞれDocument Reader と Perfect Reader Mini というアプリを使用)
    • 操作タスクでは19インチのモニタも同時に使用(後述)
  • Materials
    • 2つのタイプのテキストを使用
      • 物語
      • 手続き的なテキスト
    • 物語は1500字程度のものを4種類用意
    • 手続き的なテキストは6ステップからなるものを5つ用意
    • どちらのタイプのテキストも、スクロール式のものとページ式のものを両方用意した
  • 記憶力タスク
    • 物語を読んでもらった後に、10個の穴埋め式の設問に回答してもらう。
    • テキストの位置が記憶力に影響するかどうかを見るために、半分の設問はテキストの端(最初と最後の3行)の部分に関する設問にした
  • 操作タスク
    • iPodでマニュアルを読んでもらいながら、仮想コンソールをPCで操作してもらう
    • 操作ミスがあったら、正しく操作できるまでやり直し
  • ワークロードの評価
    • スクロール式、ページ式の双方で操作タスクを終えたあとに、NASA-TLXを用いてワークロードを評価した
  • 実験手順
    • 実験を行う前に、5分間スクロールやページめくりの練習
    • 仮想コンソールの操作の練習も7分間行う
    • ページめくりは横方向に指をスライドさせるが、スクロールは縦方向に指をスライドさせて行う
    • 記憶力タスク --> 操作タスク の順で行う
    • スクロール式とページ式を両方つかてもらうが、どちらを先に使うかは被験者を半々に分けてバイアスがかかるのを避けた
    • 操作タスク終了後、NASA-TLXを使ってワークロードを評価
3. Results
  • 一番好まれた操作方法は、物語・手続き的テキストの双方でスクロールであった
  • 記憶力タスクの結果
    • 回答の平均スコアは、ページレイアウトで読んだ場合のほうがわずかに高かった(統計的有意差あり)
    • 回答のある位置(テキストの端か中央部分か)に関してはスクロールの場合は統計的有意差はなかったが、ページの場合は有意差があった(中心部のほうがスコアが高い)
  • 操作タスクの結果
    • 仮想コンソールの操作に要した時間に有意差はなかった
    • スクロールを好む人と、ページを好む人を別々に考える
      • スクロールを好む人は、スクロールで読んでいる場合のほうがページで読んでいる場合よりも操作時間が有意に短くなっていた
      • 一方ページを好む人の場合は、ページで読んでいる場合のほうが操作時間は少し短くなっているものの、統計的に有意な差はなかった
    • 操作ミスの回数に有意差はなかった
  • メンタルワークロード
    • Mental workloadに関してはスクロールの方がかなり少なかった
    • Temporal workload, performance, effort, frustrationについてもスクロールのほうが低いスコアだった
    • Physical workloadに関してはほとんど差がなかった
4. Discussion
  • 物語に関しては理解力はページレイアウトで読んでいる場合のほうが高い
    • PCモニタの場合と同じ結果
  • 手続き的なテキストに関しては、操作ミスの回数や操作時間に差はなかったものの、スクロールを好む人だけに注目すると、スクロールレイアウトの場合に短い時間で操作を終えていた
  • メンタルワークロードは、全体的にスクロールの方が低い
  • PCモニタの場合だけでなくスマートフォンにおいても、ページレイアウトのほうが読解には向いているのではないか
  • スマホユーザにとっては、手続き的なテキストに関してはスクロールの方が効率良く読めるのではないか
5. Conclusion
  • 教科書などの記憶力を要するテキストの場合は、ページレイアウトを使ったほうが良い
  • マニュアル、レシピ、how-to本などはスクロールレイアウトのほうが、スマホに慣れ親しんでいるユーザにとっては効率良く読める

2012年7月13日金曜日

Scrolling Behaviour with Single- and Multi-column Layout [Braganza et al., 2009]

Scrolling Behaviour with Single- and Multi-column Layout [Braganza et al., 2009] を読みました。
以下、簡単なまとめ。結構色々端折ってます。

1. Introduction

  • デジタルデバイスで文書を作成する際に決めなければいけないものの一つに、レイアウトモデルがある。
  • レイアウトモデルは大きく分けて3つ
    • 縦スクロール (vertical scroll)
      • 現在のWebブラウザ向けの文章の大半はこれ
      • single-columnの場合には良いモデルだが、multi-columnだと次のcolumnの先頭を探すために余計なスクロールが必要となる
      • single-columnの場合でも、大きなスクリーンのスペースを活用しようと思うと、テキストの幅が広くなり読みにくい
    • ページレイアウト (page layout)
      • 文書を表示する際にページのサイズや内容を動的に決定しない限りは、電子デバイスには適していないように思える
    • 横スクロール (horizontal scroll)
      • レイアウトは動的に行われるので、ページレイアウトの際に生じる画面サイズに合っていないページサイズ等の問題が避けらる
      • --> 電子デバイスでmulti-columnの文章を読むには一番適しているように思える
  • Scrolling mechanism
    • キーボード、マウスのホイール、スクロールバー、etc...
    • 1行ごとのスクロール、連続的なスクロール、page-at-a-time movement, ページの先頭へなどの機能、etc...
  • 本論文の貢献は下記の通り
    • 縦スクロールと横スクロールのユーザビリティを調査した初めての論文
    • 各scrolling mechanismに対するユーザーパフォーマンスやリーディングパフォーマンスとの関係を調査した
    • スクロールの戦略(scrolling strategy)も調査した。そのような研究は少ない。
    • 様々なscroll mechanismをもった閲覧ツールを実装した
  • 実験の結果、被験者の1/3は横スクロールを、2/3は縦スクロールを使いやすいを感じていた
    • 縦スクロールが選ばれた理由は慣れているからなのに対し、横スクロールが選ばれた理由はスクロールのしやすさや、テキストの幅が短くなることなど
  • スクロール戦略やscroll mechanismと、快適なレイアウトには関係がある
  • 縦スクロールと横スクロールでタスクをこなす時間に有意な差はなかったが、そのうちスクロールにかけた時間に関しては横スクロールのほうが短かった
2. Related Work
  • スクロールについての先行研究との違いは主に以下の3つ
    • 横スクロールを考えた初めての研究
    • ユーザにブラウザの設定(ウィンドウサイズ、フォントサイズなど)を自由に選ばせた
    • アイトラッキングで得られたデータを使ってスクロール戦略を区別した
3. Browser
  • HTML/CSSのサブセットをサポートする独自のブラウザを実装した
  • 横スクロールレイアウトの場合は、以下のような挙動をする
    • ユーザはコラムの数をボタンで選択できる
    • ウィンドウ幅が変わった場合、コラムの幅も変わる
    • 様々なscrolling mechanismを実装 (詳細略)
      • Grab-and-drag
      • Scroll ball
      • Scrollbar
      • Keys
      • Overview
    • 上記scrolling mechanismの最後の2つに関しては、コラムの左端と画面の左端がくっつくようなシステムを採用
4. The Experiment
  • 実験概要:被験者にそれぞれ縦、横スクロールレイアウトで表示されている2つの物語を読んでもらい、さらに設問に回答してもらう。回答の際には、物語を再度読みなおすことができる。
  • 検証したい仮説
    • 横スクロールは多くの人に気に入ってもらえる
    • 横スクロールは目的の場所を探しやすい
    • 横スクロールレイアウトでの"自然な"スクロール方法は、ひとつのコラムごとにスクロールすることである
    • ユーザにとっては、スクロール回数やスクロールに費やす時間を少ないほうが良い
    • スクロール戦略の選ばれかたは、レイアウト(縦or横)によって異なる
  • 被験者は24人の大学生or院生。データ不備等の為、多少データを捨てた。
  • 使用した物語は2000語程度の英語の文章
  • 実験の前後に質問に回答してもら
    • 前の例: 週に何時間程度コンピュータのモニタで文書を読みますか?
    • 後の例: 縦スクロールと横スクロール、どちらが気に入りましたか?またその理由は?
  • 実験の流れは以下を縦と横レイアウトについて、繰り返す(順番はバイアスがかからないように被験者ごとにシャッフルされる)
    1. 操作の練習
    2. 実験の説明
    3. アイトラッカー(FaceLAB)のcalibration
    4. 物語を読む
    5. 設問に答える
5. Data Analysis and Results
5.1. Dana analysis
  • 各ユーザのログから以下のアクションの順番と所要時間を解析した
    • ブラウザのリサイズ
    • フォントサイズの変更
    • コラム数の変更(横スクロールレイアウトのみ)
    • Grab-and-dragによるスクロール
    • Scroll ballによるスクロール
    • Scrollbarによるスクロール
    • Page up, page down, スペースキーによるスクロール
    • その他のキーによるスクロール
    • Overviewによるスクロール
5.2. User preference
  • Layout model preference
    • 24人中、8人は横スクロールの方を好み、16人は縦スクロールの方を好んだ
    • 縦スクロールのほうが良かった理由としては、縦スクロールには慣れているが横スクロールには慣れていないというものが主だった
    • 3人の被験者は、横スクロールの場合視線を上下に動かさないと行けない(次のコラムに移るときなど)のが嫌だと言っていた
      • 縦スクロールの場合は、スクロールして好みの高さに読みたい文章を持ってこれる
      • 視線の移動は上下よりも左右のほうが楽?
  • Preferred scrolling mechanism
    • 使用したscrolling mechanismを分析しても、縦スクロールと横スクロールの場合で統計的に有意な差は得られなかった
    • ただし、縦スクロールの場合はscroll ballやscroll barを使う人が多かったのに対し、横スクロールでは矢印キー、scroll ball、grab&dragを使う人が多かった
    • grab-and-dragを使った人は6人中5人が縦スクロールのほうが快適だと回答。矢印キーを使った人は6人中5人が横スクロールのほうが快適だと言っている。
      • どのレイアウトが好まれるかは、使われるscroll mechanismに依存しているのではないか
5.3. Performance
  • 横スクロールのほうが少ないスクロール回数・時間だと予想していたが、 リーディング、設問への回答のどちらの場合にも、実際そうだった(統計的有意差あり)
    • その理由としては横スクロールのほうが縦スクロールよりも文書全体を表示するのに必要なスクロール量が少ないことが考えられる
  • 横スクロールの場合には、コラムが目印となって設問の回答時間が短くなる(関連箇所を探すのに要する時間が短くなる)と予想していたが、そのような結果は得られなかった
5.4. Scrolling strategies
  • スクロール戦略は、大きく分けて次の3つが観察された
    • Page: 画面に表示されているテキストを(ほとんど)全部読んでから、一画面分スクロールする
    • Continuous: 画面の中のごく限られた位置のみのテキストを読む。細かくスクロールを駆使して、読みたいテキストがその位置に来るように調整する。
    • Region: PageとContinuousの中間。ある一定の範囲(だいたい画面の半分程度)にあるテキストを読みきったら、その範囲に次のテキストが来るようにスクロールする戦略。
  • 被験者は物語を読む間に一貫した戦略を使う傾向がある(途中で戦略を変えたりしない)
  • 縦スクロールと横スクロールの場合に、似た戦略を使う傾向がある
  • それぞれの比率
    • 縦スクロール
      • page: 13%, continuous: 46%, region 31%
    • 横スクロール
      • page: 50%
      • 64%は見えてるコラムのうち幾つかを読んで、その分スクロール 
      • 一人だけcontinuous
  • 横スクロールの場合は、テキストは画面中央で読まれることが多い
  • 縦スクロールの場合は、画面の下の方で読まれることが多かったが、上から3分の1程度の箇所にもピークがあった
6. Discussion
  • 得られた所見をまとめると次の通り。
    • 被験者の1/3は横スクロールのほうが快適だと感じた。読むこと自体や設問への回答のパフォーマンスは、どちらのレイアウトでもほぼ同じだった。
    • 縦スクロールの際、46%の被験者は視線の動きが最小限で済むようなスクロール戦略を採用している。逆に、ページ全体を読んでからスクロールという戦略を採っていたのは13%しかいなかった。画面の下の方が注視されやすい。
    • 横スクロールに関しては、64%の被験者が1or2個のコラムを読んでからスクロールをしていた。表示されているコラム全部を読んでからスクロールという戦略も50%いた。画面の中央が注視されやすい。
    • 横スクロールでは、スクロールの頻度は少なく、スクロールにかける時間も少ない。縦スクロールに比べ、キーでのスクロールはよく使われるが、scroll ballやscrollbarはあまり使われない。
    • 縦スクロールで使うスクロール戦略は、レイアウトの好みに影響する(continuous scrollをする人は縦スクロールを好む)。Scrolling mechanismも同様に影響する(grab-and-dragを使う人は縦スクロールを好み、keyを使う人は横スクロールを好む)。
  • タッチスクリーン式のデバイスには、grab-and-dragを使う人に好まれる縦スクロールが適している?

画面の下の方が注視されやすいということが結構書かれていたけれど、見やすい場所って頭の高さや、画面の高さに大きく影響されると思うんです。
そのあたりの装置の配置状況などは書いてないですし、画面下が注視されやすいという点に関してはこの結果を見ただけじゃなんとも言えない気がします。

2012年7月8日日曜日

eshellのalias登録したコマンドで引数が処理されない

[環境]
OS: Windows 7 Home Premium Service Pack 1
Emacs: emacs 23.3-3

[背景]
JDK SE 7u5をインストールし、eshell上で java や javac などのコマンドを入力すると出力が文字化けする。
こちらの記事などを参考にしたところ、java には -Dfile.encoding=UTF-8 というオプションを、 javac には -J-Dfile.encoding=UTF-8 というオプションをそれぞれ指定して、出力されるメッセージの文字コードを指定してあげれば良いことが分かった。
eshell上で java -Dfile.encoding=UTF-8 と打っても、文字化けせずにヘルプが表示される。

alias java 'java -Dfile.encoding=UTF-8'
alias javac 'javac -J-Dfile.encoding=UTF-8'

と alias を登録し、いざ javac Foo.java と何かをコンパイルしようとしたら、表示されるのはヘルプのメッセージ。(ただ javac と入力した場合と同じメッセージ)
何度試しても同じ結果で、どうやら引数を受け取ってない模様…。

[問題]
eshellで
alias java 'java -Dfile.encoding=UTF-8'
alias javac 'javac -J-Dfile.encoding=UTF-8'
などとエイリアス登録し、 java foo とコマンドを入力しても、fooなどの引数がプログラムに渡されない

[解決策]
EmacsWikiに書いてありました。
alias java 'java -Dfile.encoding=UTF-8 $*'
alias javac 'javac -J-Dfile.encoding=UTF-8 $*'
最後に $* をつけて、引数をjavaなりjavacなりに渡しますよということを明示的に書かないといけないらしい。
bashとかだと、aliasって単純に 'java'って文字列を'java -Dfile.encoding=UTF-8'って文字列に置き換えるだけだったと思っていたので(違ったらすいません)、eshellも同じかと思い込んでおりハマリました。

2012年7月2日月曜日

CSS3の Multi-column Layout Module を使ってみる

CSS3にはMulti-column Layout Moduleというものがあります。
http://www.w3.org/TR/css3-multicol/

私は従来のHTMLは遊び程度に少し触っていた程度の経験しかないのですが、CSSのfloat機能を使うかtableなんかを使ってmulti-columnを実現することが多かったのではないでしょうか。

その場合大変なのは、コンテンツを各columnにどう振り分けるか、という処理。
動的に生成されるテキストだったりすると、はじめからテキストを振り分けることもできず、なかなか美しいレイアウトを作るのは難しかったんではないでしょうか。

CSS3で提供されるMulti-column Layout Moduleを使えば、コンテンツの各columnへの割り当てはレンダリング時に自動でやってもらえます。
細かい使用等の説明は他のサイト等に譲るとして(私用の忘備録なので)、例えば次のようなcolumnクラスを定義し、divタグなどでこのクラスを指定してあげると、画像のサイズを変えてもちゃんとmulti-columnのレイアウトになってくれます。

.column {
    column-width: 30em;
    -webkit-column-width: 30em;
    -moz-column-width: 30em;
    column-gap: 5em;
    -webkit-column-gap: 5em;
    -moz-column-gap: 5em
}

ちなみに-moz-*はFireFoxで表示させるのに、-webkit-*はGoogle ChromeやSafariで表示させるのに必要みたいです。

2012年7月1日日曜日

DeNAインターン一次面接で落ちました

タイトルの通り、DeNAのインターンシップ、一次面接で落ちました。
一次面接は渋谷ヒカリエにて行われました。 私が参加した時間帯は、1グループ5人程度で、3グループ同時に面接が行われました。
全員の人数はちゃんと数えてないけど、おそらく15人、そのうち私服は2人でした。ちなみに面接官や部屋まで案内してくれた社員さんは私服でした。

面接で行われた内容は、まずは30秒で簡単に自己紹介(過去の面接で行われたことがあるらしい、自分の過去の人生で映画を作るとしたら~みたいなものはなく、普通の自己紹介でした)。

次に、「みなさんの共通点を3つ見つけてください」と言われ、3分間時間を与えられる。3分間グループで話し合い、3分後に1人が面接官に報告するという形。


それが終わったらいよいよグループディスカッションです。一つ目は、面接官に関する情報(例えば、「私はお酒を飲むことができません」や「私は最近映画を見ていません」など)が与えられ、その理由を10分間で推測するものです。10分間のうち、どのタイミングでもいいのですが、3回だけYES/NOで答えられる質問を面接官にすることができます。
これが結構難しかったですね~。直後にもらったフィードバックによると、質問はなるべく解空間を半分にするような質問を選ぶことが大事とのこと。YESだったら理由が特定できるけど、NOだったらほとんど解空間が減らせない…みたいな質問を投げると評価が高くないようです。ちなみに、うちのグループはそういう観点からいくと全然ダメな質問を結構投げていましたね。
10分間が終わったあと、本当の理由を説明される前に、参加者に一人ずつ別々の質問もされました。「最初の質問を変更できるとしたら変更しますか?」「4つ目の質問をするとしたら、どのような質問をしますか?」などなど。

その後はグループディスカッション2つ目です。これは過去の面接について書いてあるブログにもあった、「直前の相手の発言を否定し、なおかつ新しいアイデアを出す」という制限つきのディスカッション。テーマは「○○の売上を2年間で2倍にするにはどうすればよいか」というようなものが与えられ、アイデアはできる限り具体的であることが求められます。抽象的な発言をすると、「ということは、どういうことですか?」みたいに突っ込まれます。

最後に自己PRが30秒(私の時は、今までに頑張ったこと、というテーマが与えられました)あり、挙手制で手を挙げた人から順に自己PRをして、質問タイムがあって終了という感じでした。

私自身が落ちたので、私の主観が入っているところはあまり参考にしないほうがいいかもしれません。

2012年6月13日水曜日

Wide vs. Narrow Paragraphs: An Eye Tracking Analysis [ D. Beymer et al., 2005]

Wide vs. Narrow Paragraphs: An Eye Tracking Analysis [ D. Beymer et al., 2005] を読みました。IBMの研究所の方の論文で、PC上でテキストを読む際に、そのテキストの幅(パラグラフの幅)が、reading behavior にどのような影響を与えるか、ということについての論文です。
以下、説明の際に i) のように区切って説明していますが、この区切りは私が勝手に考えたもので論文の章などとは直接は対応していません。

i) Introduction

  • 紙上での研究では、パラグラフの幅は狭いほうが良いという研究結果がある。逆に、PCの画面上の場合はパラグラフの幅は広い方が良いという研究もある。結局どっちがいいの?
  • 今回は、アイトラッキングという手法を用いてこれを検証する。
ii) アイトラッキング
  • 人間の視線の動きを計測する装置
  • FixationやSaccadeなどを検出できる。基本的に人が何かを読む際の視線情報は、このFixationとSaccadeが交互に観察される。
    • Fixation: 人はテキストを読む際、250msほどある点を注視し、そして視線を動かす、という動作を繰り返す。この注視する動作のことをFixationという。
    • Saccade: あるFixationから次のFixationに移る間に、素早く視線を動かす動作のこと。
  • 特殊な装置(メガネなど)を体に装着する必要のないリモート型のアイトラッカー(視線検出装置)を使用
  • ブラウザ上でのアクションや視線の動きを自動で計測・解析するツール(WebGazeAnalyzer)を作って使用した
iii) 実験
  • 次の2つのテキストを用意して、それぞれ8人ずつの被験者に読んでもらう
    • A (Wide): 画面の幅の80%(9インチ)で表示されているテキスト
    • B (Narrow): 画面の幅の40%(4.5インチ)で表示されているテキスト
  • テキストを読んだ後には、問題にも答えてもらう
iv) 結果
ざっくりとした結果のみを紹介します。細かい数字を知りたい方は、グラフなどを使ってわかりやすく説明されているので、ぜひ元論文をあたってみてください。
  • テキストを読むのに要した時間と、読まれたテキストの範囲
    • Aの方が読むのに時間がかかっているが、より多くの範囲が読まれている
    • Bは逆に、読むのにかかる時間は短いが、読み飛ばされる箇所も多い
  • 読むスピード
    • Instantaneous measures: 同じ箇所を複数回読んだら、読んだ回数だけ距離をカウント。左から右への視線の動きしかカウントしない。
    • Overall measures: 同じ箇所を複数回読んでも、1度だけ距離をカウント。
    • Instantaneous measuresに関しては7%ほどBの方が早く、Overall measuresに関しても15%ほどBの方が早い
  • Return sweeps
    • Return sweep とは、行の末尾から次の行の頭まで視線を移動させる動きのこと
    • Aの方が平均的にReturn sweepに時間がかかる
    • Aの場合は、return sweepが長くなるので、途中で余分なfixationが入ってしまうことが多い --> ヒストグラムに2つの大きな山
  • Return sweepsに要する時間
    • 上で見たように、1度のreturn sweepに要する時間はAの方が長かった
    • しかし、Bの場合はテキストの幅が狭く、その文高さが高くなっている(=行数が多くなっている)ので、パラグラフ全てのreturn sweepに要する時間を合計すると、トータルではBの方がreturn sweepに時間がかかっている
  • Regressions
    • Regressionはバックジャンプとも呼ばれ、テキストを読んでいる際に前に(左に)戻る視線の動きのこと
    • Regressionは難しい文章を読んでいる際に起こりやすい
    • Aの方が時間あたりにRegressionの起きる割合が多かった
  • Retention
    • テキストを読んでもらった後に実施した問題の平均スコアはBの方が高かった (スコアは3点満点で、B: 1.75 > A: 1.25)
    • テキストを読むのにかかった時間で上記スコアを正規化しても、A: 0.081 points/sec, B: 0191 points/secと有意な差があった

2012年6月10日日曜日

夏季インターンシップ申し込みの季節です

今はちょうど夏季インターンシップの申し込みが盛んに行われている時期です。
私も修士1年なので、今年の夏はどこかの企業に参加してみたいと思い、少しずつ応募し始めています。

修士を卒業した後の進路については、現時点では就職するつもりです。
博士課程に進むのもありだけど、経済的な理由や研究を一生職業にしていくほどの適性が現時点で私にはあるとは思えないのが主な理由です。
修士で研究を進めていくうちに、研究が面白くなってきたらまた考えが揺らぐかもしれませんが。。
就職するとしたら研究職じゃなかったらIT系のエンジニアを考えているので、その方向で今年の夏働ければいいなあと思っています。

現時点で応募した企業はGoogle, 日本Microsoft, DeNAです。
Googleは応募して1週間ちょい立ちますが音沙汰なし(ダメっぽいですねorz)、Microsoftは先程Webテスト受けて今結果待ち、DeNAは今月中に1次面接を受けるっていう感じです。
出来れば長期でそれなりに報酬も出るところに行きたいのでGoogle, Microsoftという順で希望しているのですが、どちらにも引っかからなかったら片っ端から日本の企業受けてどこかに潜り込むつもりです。(DeNAはその日本企業のうちの一つ)

上記の3社のうちMicrosoftとDeNAはWebテストがありましたが、圧倒的にDeNAの方が難しかったです。
難しかったというか、時間が足りなかったというか…。
全然出来なかったんですが、Webテストは通ったところを見ると、あれは飾りなんでしょうか。就活関連の事情は詳しくないのでよくわからないです。

2012年4月27日金曜日

Ubuntu 12.04 にアップグレードしたら ibus.el がうまく動いてくれなくなった

Ubuntu 12.04 がリリースされたので、11.10 からアップグレードしました。
使い勝手が良くなっている箇所が多々有り非常に良いと思うのですが、Emacsを起動してみると、日本語入力がうまくいかない。
正確にいうと、日本語入力自体はなんとかできるようですが、先日設定したばかりの ibus.el が正しく動いてないようです。

結論から言うと、Ubuntu 12.04 には .Xresources ファイルに書いた内容が emacs に反映されないというバグがあるらしいです。
試しに、端末から

XMODIFIERS=@im=none emacs

として起動してみると、たしかに ibus.el が動いた!

というわけで、しばらくはこれをエイリアスとして登録して使うことになりそうです。


2012/6/13追記
久々に調べてみたところ、emacs23を使っている方は .Xresources に

Emacs23*useXIM: false

と記述すれば動くようです。私の環境でもこれで動作を確認しました。

2012年4月17日火曜日

color-themeでEmacsの見た目を変える

http://www.nongnu.org/color-theme/index.html

上記サイトにアクセスして、指示通りcolor-themeをインストールし、.emacsに設定を記述するだけ。
テーマ一覧なんかは以下でみれる模様。

http://gnuemacscolorthemetest.googlecode.com/svn/html/index-el.html

ibus.elを使ってEmacsで快適日本語入力

本当にただの忘備録です。
恥ずかしながら今まで知らなかったのですが、Emacsで日本語入力を行うなら ibus.el というものを使うと快適に日本語入力が行えます。


入れてみて少し使ってみましたが、結構おすすめ。
今までは -nw コマンドでターミナル内で起動することによって日本語入力がおかしいの回避してました。

2012年3月31日土曜日

Exploring the Effects of Visual Cognitive Load and Illumination on Pupil Diameter in Driving Simulators.[O. Palinko and A. L. Kun., ETRA2012]

Exploring the Effects of Visual Cognitive Load and Illumination on Pupil Diameter in Driving Simulators.[O. Palinko and A. L. Kun., ETRA2012] を、ざっくりと読みました。
軽くまとめておきます。

ETRA2012に参加して、ポスターの説明を加担に聞いてきたので、現時点で理解している範囲でまとめておきます。


  • 瞳孔のサイズは以下の2つの場合に変わることが知られている
    • 網膜に届く光量が変わった時
    • 何らかのタスクにより、cognitive loadが増加したとき
      • ※cognitive loadが何なのかよくわかりません。そのうちまた論文読みます。
  • これら2つの要素を切り分けることはできるのか?
  • 運転シミュレーションソフトとアイトラッカーを使って実験
  • 3つのタスク
    • Illumination Task: 運転シミュレーションソフトに、黒、グレー、白の3色のトラックを表示(それぞれプロジェクタの最大輝度の10, 50, 90%)。この3つのトラックを順に見ていく。
    • Visual Vigilance Task: モニターに1から順番に数字が表示される。1つの数字が表示される時間は1.5秒。ただし、6の倍数の場合だけ、間違った数字が表示される可能性がある。もし間違った数字が表示されていたらボタンを押す。
    • Combined Task: トラックの後ろの部分に数字を順に表示していく。3つのトラックのに表示される数字は同期されている。トラックの視線を移させるタイミングと、6の倍数が表示されるタイミングをずらすことで、2つの原因による瞳孔の大きさの変化が同時に起こらないようにする。
  • 結果
    • Illumination Task: 白のトラックを見ているときに比べて、グレー、黒のトラックを見ているときはそれぞれ約0.3mm, 0.7mmほど瞳孔の直径が大きくなった
    • Visual Vigilance Task: 6の倍数を見るときは瞳孔の直径が大きくなった(論文中のFigure 5参照)
    • Combined Task: このタスクで測定した瞳孔の直径と、Illumination Taskで測定した瞳孔の直径の差分を取ると、Combined Taskの中の Visual Vigilance Taskによる瞳孔の大きさの変化だけが取り出せる。実際にやってみると、差分のグラフはVisual Vigilance Taskで測定した瞳孔のサイズのグラフを似た形になる。

2012年3月5日月曜日

Review of Automatic Document Formatting [N. Hurst et al., 2009]

Review of Automatic Document Formatting [N. Hurst et al., 2009] を読みました。
論文は http://dl.acm.org/citation.cfm?id=1600217 から読むことができます。

前回、前々回と文書レイアウトをどのように自動で生成するかということを論じた論文を読んできましたが、この分野を概観するのによさそうな論文を見つけたので、早速読んでみました。

[Abstruct]
  • 文書自動整形の一般的な解決法は、制約最適化問題に落としこむことである
    • 決定変数は要素の配置や幾何的関係の制約などをエンコードしたもの
    • 目的関数はレイアウトのクオリティの基準となる
  • 本論文では、上記テクニックを使った文書整形にフォーカスを当てる
  • 関連した問題である自動テーブルレイアウトも扱う
[1. Introduction]
  • World Wide Web (WWW) とVariable Data Printing (VDP) によって、文書自動整形の関心は line breaking などのミクロのものから、ページレイアウトのようなマクロのものへと移っている
  • 文書を読む媒体の多様性が増している → 文書自動形成の需要は高まっていくだろう
  • 本論文で扱う問題: テキストの文書レイアウト、テーブルレイアウト
  • 扱わない問題: ウィジェットレイアウト、ダイアグラムレイアウト、画像のリサイズなどの一時的な問題
  • 文書自動形成は、次の3つの点で難しい
    • 良いデザインの定量化
    • レイアウトの計算は難しい (サブタスクであるテーブルレイアウトですらNP-hard)
    • レイアウトツールのデザインと実装が複雑
  • 文書自動整形と解く良い方法は制約最適化問題に違いない (Abstruct参照)
[2. Constrained Optimization]
  • この章では、文書自動整形で用いられる制約最適化問題の解法を見ていく
  • 変数の変域が実数である連続問題と、離散値をである離散問題、実数と離散値のどちらも取れる混合問題を分けて考える
2.1 Continuous problems
  • 主な解法は変数消去法(Variable elimination)と反復法(Iterative techniques)
  • 変数消去法
    • 線形制約のような簡単な問題には適する、複雑な非線形問題には適さない
    • 例: ガウス・ジョルダン法、シンプレックス法
  • 反復法
    • 極小値が最小値と保証されている凸包問題などに使われる
    • 例: 最急降下法
2.2 Descrete problems
  • 主な解法は Constructive Search と Local Search
  • Constructive Search
    • 参考文献: Artificial Intelligence: a Modern Approach [S. Russell and P. Norving, 2002]
    • 例: A*アルゴリズム
  • Local Search
    • 参考文献: Handbook of metaheuristics [F. Glover and G. Kochenberger, 2003]
    • 例: Trajectory method
  • 上の2つの解法の詳細は、理解できていません。必要なら参考文献を読んだほうがいいかも。
[3. Micro-typography]
  • カーニング、行分割、justificationなど、低レベルな構成のレイアウト
  • 自動化された技術が実用化されている
3.1 Kerning
  • 隣接文字との距離をどの程度取るかという問題
  • 文字の Bounding Box だけを使って等間隔に配置すると、視覚的には文字間の距離が一定には見えないので、文字の見た目も考慮に入れる
  • 文字間の距離を教えてくれるフォントも存在する
  • しかし、以下のような理由で、カーニングを自動で行う需要はある
    • 全てのフォントが、全てのフォントサイズでの文字間の距離を提供しているわけではない
    • 提供された文字間隔では、矩形でなカットアウトに対処できない
    • 提供された文字間隔では、複数のフォントが混ざったテキストに対処できない
  • hz typesetting の kf-module や Adobe InDesign が自動カーニングを提供している
    • 参考文献: 論文 References の [46, 81, 53, 32]
3.2 Line breaking
  • どの単語(ハイフネーションが可能な場合は単語の途中も可)を行の終わりに置くかという問題
  • first-fit 戦略
    • 行に限界まで単語を順に詰めていく (Constructive Search の一種)
  • Knuth-Plass アルゴリズム
    • 参考文献: Breaking paragraphs into lines [D. Knuth and M. Plass]
    • 行分割とハイフネーションを最適化問題として定式化し、動的計画法で解く
    • TeXでも使われている (Knuthさんは、御存知の通りTeXの開発者です)
    • 段落ごとに適用し、行の長さを均等にする
    • ワード数がnで、1行に入る最大ワード数がkの時、最悪計算量 O(kn)
3.3 Line justification
  • 行分割が決まったら、行の中での文字や単語の位置の微調整が必要(行の長さが多少は違っても良い場合はこのステップは省略可)
  • フォントの大きさを変える、単語間/文字間のスペースの大きさを変える、alternative ligatures and glyphsを使う(?)、などの方法がある
  • 一次元の連続最適化問題としてモデル化される
    • TeXの場合、行はglue glopで仕切られたboxで構成されていると仮定
    • 行に入る単語の長さに多じて、glue glopが伸び縮みする
[4. Macro-typography]
  • レイアウトの見た目すべてを決める
    • 文書の要素の配置方法、コンテンツの選び方、カラムの位置やサイズなど
4.1 Document and page layout models
  • 閲覧メディアの違いにより、文書レイアウトのモデルも異なってくる
  • 本論文では、次の4つのモデルを考える
    • 固定サイズの1ページに使われるレイアウト(例:ポスター)
    • 固定サイズで、枚数制限のないページに使われるレイアウト(例:PDF文書)
    • 固定幅、自由な高さの1ページに使われるレイアウト(例:HTML)
    • 固定高さ、自由な幅の1ページに使われるレイアウト
  • ページレイアウトモデルは、要素がとれる配置を規定する
    • 座標(Coordinate):各要素の位置を座標で指定。postscript, pdfなどで使われている。
    • Flow:ページ上の一つのストリームに順に要素を置いていくモデル。
    • Grid:テンプレートによって規定される軸に沿ったグリッドラインを使って各要素が配置される。雑誌やMicrosoft PowerPointなどで使われている。
    • VH=Box:階層モデル。Boxは単純なオブジェクトか、垂直スタック、水平なシーケンスのいずれかとなる(?)。TeXで使われている。
    • Guillotine:直交空間分割木(orthogonal space partition tree)という構造を使う。
    • Box:ページを矩形領域の集合で表現する。VH=Box, Guillotine, Gridモデルの一般化。5章で扱うテーブルも、Boxレイアウトとみなされる。
  • Macro-typographは2つのタスクで構成される
    • ページレイアウトを選ぶ(つまり、ページに含まれる要素と、要素間の関係を選ぶ)
    • レイアウトの微調整
4.2 Fine-tuning
  • 基本的なページレイアウトが与えられた時に、それをどのように調整して違うコンテンツや違うスタイル、違うページサイズに適用させるか
    • 連続的最適化が使われる
  • One-way constraints
    • $ x = f_x (y_1, \cdots, y_n) $
  • Hierarchical multi-way propagation constraints [78, 79, 28]
  • Linear arithmetic constraints [12, 43, 3, 4, 58]
  • ... and so on... (すいません、よくわかんなかったです)
  • イメージとしては、[Lin, 2005] のように工夫してページ内での制約を解くんだけど、その工夫の仕方はいろいろあるよ、ってことを言ってる?
4.3 Choosing a page layout
  • ページにどのような要素を、どのようなレイアウトで配置するかを決める問題
  • ページレイアウトの部分問題の中で一番難しい。離散的な問題。
  • この節では、ページレイアウト選択の様々な方法が紹介されていますが、私の理解が追いついていいないこともあり、以下かなりかいつまんだまとめになっていますので、興味の有る方は是非元論文をあたってください。
  • 浮動的な図をどう配置するか?
    • 本文の参照箇所の近くに配置したい
    • グリーディーに、一番最初に配置できる箇所に配置(TeXやHTMLで使われている)
  • 図が参照と同じページに、無理な場合は次のページのなるべく近い位置に表示されるように最適化する方法も提案されている
    • Optimal pagination techniques for automatic typesetting system [M. Plass, 1981]
    • Pagination reconsidered [A. Bruggemann-Klein et al., 1995]
  • 多段組での図の配置方法
    • Automatic float placement in multi-column documents [K. Marriott et al., 2007]
  • グリッドを用いた自動レイアウト
    • A grid-based approach to automating display layout [S. Feiner, 1988]
  • グリッドのようなレイアウトのテンプレートから良いものを選ぶ
  • 遺伝的アルゴリズムを使ったGuillotineページレイアウトの自動生成
    • Automatic layout of variable-content print data [E. Goldenberg, 2002]
  • ページレイアウトを記述する文法 [79, 44, 6, 51, 21]
4.4 Retargeting a page layout
  • モバイル端末の発展により、小型ディスプレイ向けにページレイアウトを再描画する問題が生じてきている
  • 主に2つの解決方法がある
    • 全体のレイアウトを保ったまま、小さいバージョンを作る
    • 全く新しいレイアウトを作りなおす
  • レイアウトを作りなおす場合は、小型デバイス向けのレイアウトが用意されていることが多いので、そのレイアウトで作りなおす
    • 元のページの見た目だけを手がかりにするのではなく、Document Object Model (DOM)などを用いた意味構造も参考にしてレイアウトを作りなおす
    • Detecting web page structure for adaptive viewing on small form factor devices [Y. Chen et al., 2003]
    • West: a web browser for small terminals [S. Bjork et al., 1999]
    • 最近のシステムは文字色やフォントなどもレイアウトの参考にする [5, 80]
  • 小さいバージョンを作るアプローチでは、スケーリングされたページが元のページと同じように見えるように頑張る
    • 単純に小さくすると、テキストや画像などの要素が見えにくくなる
    • スケーリングしたサムネイルと、ズーム領域を使う(Supporting memory for spatial location while reading from small displays [K. O'Hara et al., 1999])などの工夫が必要。
[5. Table Formatting]

  • テーブル整形も、文書整形と同様に2ステップで考える
    • 1. 多次元データから、テーブルの論理構造を決める
      • 行や列の数、各セルの内容など
    • 2. テーブルのレイアウトを決める
      • 列の幅、行の高さなど。この時、2つの列の幅は同じ、などといった制約条件を課す。
  • テーブルの自動レイアウトは、セルにテキストが含まれると計算量が多くなる(どこで開業するかで幅や高さが変わるから) → 列の幅を決めてしまうことが多いが、決められないような状況もある
5.1 Column-driven layout
  • Line justificationのTeXのアルゴリズムを使って、固定されてない列の幅の比率を決定
  • 列の幅が決まると、各セルにコンテンツを置いてセルの高さも決定できる
  • HTMLのテーブルの作成にはこのアルゴリズムが使われている
    • HTML 4.01 SPecifiation, section 'Autolayout Algorithm'. http://www.w3.org/TR/html4/appendix/notes.html#h-B.5.2 [D. Raggett et al., 1999]
5.2 Cell-driven layout
  • この節も全然理解できていないので、読む方は注意してください。
  • 制約最適化の観点でテーブルレイアウトを捉える [8]
  • セル中のテキストの行数が複数パターンある場合も考慮 [77]
  • 高さが最小のテーブルレイアウトを見つける問題はNP完全 [1]
  • ...他にもいろいろ紹介されていますが、よくわからないので省略させていただきます…。
5.3 Mininmal configurations
  • セル中のテキストをどのように行分割するか?という話。
[6. Conclusions]
  • micro-typographyの問題に対する最適化手法は実用化できるほど効率的
  • 一方、macro-typographyの問題に対するそれは、まだ実用段階とは言えない
  • ミクロとマクロのtypographicな問題をどう自動で組み合わせるかは今後の課題
    • レイアウトの問題は相互に依存しあい、その計算量はとんでもないものになってしまう
  • 良い自動レイアウトが利用できるような文書作成支援が必要

5章あたりは体力が切れてる感が否めませんね。
必要に迫られたら読みなおして、その部分を書き直したいと思います。

でもまあ、この分野を概観することはできたのではないでしょうか。
細かい手法などは全然理解していませんが、マクロなレイアウトとミクロなレイアウトがあるということ、それらのレイアウトを整形する際には制約最適化問題を解くことが多い、など、ざっくりしたことが分かっただけでもよかったです。
今回分かったアウトラインをもとに、次回以降、個別のレイアウト合成方法の論文を読んでみたいなーと思います。
今回出てきた最適化をどのように組み合わせているかを気にしながら読みたいですね。

2012年2月28日火曜日

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章までを簡単にまとめた感じなので省略します。


こんな感じでしょうか。シンプレックス法とか細かいこと忘れてたので思わずググってしまいました。
授業で習った時も嫌いだったなーこのあたりは…なんて思いながら…。

前回の記事の論文でも言えることですが、手法のしっかりとした評価がされていませんね。
私も文書レイアウトをするようなアルゴリズムを考えてみたいのですが、その際にそのレイアウトがどれほど良い物なのかを定量的に評価する方法は無いものでしょうか。

2012年2月27日月曜日

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年近く前の論文で、内容を解説している日本語のブログ記事も存在していました。
今回は、私自身が論文の理解を深める意味を込め、私なりに論文を流れに沿って簡単にまとめていこうと思います。
各章の内容を箇条書きで書きなおしているだけで、流れなどがわかりにくいかとは思いますが…。精進します。


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

いきなり私の頭の足りなさを露呈する形になってしまいましたが、今回はこれにて。
省略した部分や、理解できていなかった部分が分かった場合は、後日追記する可能性もあります。

2012年2月22日水曜日

講演「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を適用した結果が紹介されていました。
スポーツに関するページはスポーツで関するページごとに集まったり、都市に関するページは都市に関するページなどで集まったり、といった様子が見て取れました。

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

ブログ開設

ブログ開設しました。
この春から大学院に進学します。
これからは論文を読む量や、講演会等に参加する機会も増えるのではないかと思うので、それらの忘備録にでもなればと思っています。

自然言語処理系の研究室に配属してもらっていますが、まだ自然言語処理は素人です。
早く勉強して人並みになりたいですね。。