データ発見隊

第3回予測インターフェース

はじめに

「よろしく」と入力すると「お願い」が候補に出るような「予測入力方式」が、携帯電話などで最近広く使われています。ユーザの次の行動を予測するようなシステムは「予測インタフェース」と呼ばれており、昔からさまざまなシステムが研究されてきています。

ユーザの行動を予測する方法はいろいろなものが考えられます。上の例の場合は「よろしくお願い申しあげます」という表現が世の中でよく利用されているという統計情報を利用して予測を行ったものですが、ユーザの行動履歴や現在のコンテキストなどの情報を利用することもできます。筆者の場合は「増井」という名前を入力する機会が多いため「ま」と入力すると「増井」が予測されます。時刻や位置情報のようなコンテキストを利用できる場合、渋谷で駅名検索するときは「し」から「渋谷」を予測し、新宿で検索するときは「し」から「新宿」を予測するといったこともできるでしょう。⁠123」から「4」を予測したり、⁠青森」⁠秋田」から「岩手」を予測したりといった高度な予測も可能かもしれません。

予測インタフェースが成功する要件

予測インタフェースは次のような特徴を持っている必要があります。

予測の精度が高いこと

システムの予測結果がユーザの期待と一致しないことが多ければ予測システムを利用しようとは思わないでしょう。次の入力単語を完全に予測することは不可能ですが、候補をいくつかリストすればその中に含まれる可能性が高くなるので予測の精度が上がったように感じられます。

予測により作業が邪魔されないこと

予測のための計算に時間がかかったり、予測をキャンセルするために余計な手間がかかることが多いと、予測インタフェースを使わないほうがマシだと判断されてしまいます。

予測の実行に手間がかからないこと

システムが正しい予測を行ったとき、最小限の手間でそれを採用できるようにする必要があります。手間がかかると予測を行った意味がなくなってしまいます。

予測に失敗したとき被害をこうむらないこと

入力単語を予測するような場合は予測に失敗してもそれほど困ることはありませんが、大きな編集操作を誤って予測して実行してしまったような場合、苦労して実行結果を修正しなければならないという可能性があります。予測インタフェースのために一度でも大きな被害にあえば、二度と使う気にはならないでしょう。


上述の条件をすべて満たすシステムは多くないため、予測インタフェースはまだ広く使われているとは言えませんが、入力作業の効率化に予測インタフェースを利用する例は増えてきています。最近のブラウザでは、URL入力欄に文字列を入力すると、それを含むURLを候補として表示してくれることが多くなっていますが、これはユーザのWebページ閲覧履歴を利用した予測インタフェースです。また、検索エンジンの検索枠に文字を入力すると関連した検索語を提案してくれる「Google Suggest」のような機能が使えるようになっていますが、これはあらゆるユーザの検索履歴やGoogleのデータベースを利用した予測インタフェースと言えるでしょう。

Dynamic Macro

ここでは、便利な予測インタフェースとして、テキストエディタ上のルーチンワークを効率化する拙作のDynamic Macroを紹介します。

テキストエディタ上で同じような編集操作を繰り返すことがよくあります。よくある例として次のようなものがあるでしょう。

  • ブロックをまとめて字下げする
  • 変数名を変更する
  • 連続する行にコメント記号を挿入する

上に挙げた編集操作はすべて同じ編集操作の繰り返しになっています。「行頭に移動⇒空白を挿入⇒次の行に移動」という操作の繰り返しですし、「変数名を検索⇒変数を削除⇒別の変数名を挿入」という操作の繰り返しです。

Emacsの場合、これらの作業に関してindentregion⁠、replace-string⁠、comment-regionのような関数が用意されており[1]⁠、ほかのエディタでも同様の機能が用意されていることが多いと思います。しかし、そのような機能が存在することを知らなければ使えませんし、使い方を思い出すのに時間がかかることもあります。

Dynamic Macroは、ユーザが同じ操作を繰り返したあとで「繰り返しキー」注2を押すと、繰り返されたキー操作を再実行できるシステムです。の場合、⁠行頭に移動⇒『#』を挿入⇒次の行に移動」という操作を繰り返したあとで「繰り返しキー」を押すと、この処理を再実行できます図1⁠。

図1 EmacsでDynamic Macro
画像
Emacs上でテキストファイルの最初の2行の行頭に「#」を挿入
画像 画像
「繰り返しキー」を押すと、繰り返されたキー操作がマクロとして登録されて再実行される
画像 画像
繰り返しキーを何度も押すと登録された操作が何度も繰り返される

FirefoxでもDynamic Macro

Dynamic MacroはもともとEmacs上で開発したものなので、それ以外の環境では利用できなかったのですが、最近のブラウザの「拡張機能」を利用すると、ブラウザ上のテキスト編集領域でもDynamic Macroを利用できるようになります。ここではFirefoxの拡張機能Keysnail上に実装されたDynamic Macroを紹介します。

Keysnailはmoozさんが開発したFirefoxの拡張機能で、Firefox上のキー操作を柔軟に拡張できます。またKeysnailはプラグインによって機能を拡張できるようになっており、Dynamic Macroがプラグインとして実装されています

KeysnailとDynamic Macroプラグインをインストールすると、前述のような機能をFirefox上で利用できるようになります。繰り返しキーはKeySnailの設定ファイル~/.keysnail.jsで次のように登録しておきます。ここでは[Ctrl]+[t]を繰り返しキーとして指定しています。

key.setEditKey('C-t', function (ev) {
    ext.exec("dmacro-exec");
}, 'Dynamic macro');

Twitterで投稿テキストを強調するために文字間に空白文字を入れる場合、図2の操作を行います。この例の編集操作は簡単なのでDynamic Macroを使わなくても手間はたいしたことがありませんが、ブラウザ上で大規模な編集操作を行う場合はDynamic Macroの機能は非常に有用です。

図2 FirefoxでDynamic Macro
画像
投稿テキストを入力
画像
画像
文字の間に空白文字を入れる操作を2回繰り返す
画像
画像
繰り返しキーを押すと、⁠カーソルを1文字分進めて空白文字を挿入する」という操作が繰り返される

予測とデータ圧縮

大きなファイルを配布するとき、gzip、zip、bzip2など、さまざまなデータ圧縮システムが利用されています。細かい方式はさまざまですが、データの統計的性質を利用することによって冗長な部分をなるべく省く工夫をしている点は共通しています。

多くの圧縮アルゴリズムは、現時点までに処理したデータの統計的性質から次のデータを予測することによって圧縮を行っています。たとえば「abcdefg」という文字列の出現が何度も観測された場合、これを「x」という名前で辞書に登録することにより、それ以降は「abcdefg」の代わりに「x」と表記することによってデータ量を減らすことができます。また、⁠abc」のあとには「defg」が続くことがほぼ確実なのであれば、⁠defg」の記述を省略し、それ以外の場合だけ例外として記述することによってデータ量を減らすことができます。いずれの場合も、観測されたデータから統計的情報を抽出し、その情報から次のデータを予測することによってデータ圧縮を行っている点は共通しています。

つまり、データ圧縮アルゴリズムはデータ予測アルゴリズムと非常に関係が深いことがわかります。効率の良い圧縮アルゴリズムは予測の精度が高いことになるので、同じアルゴリズムを予測インタフェースで使うと効果的だということになります。

PPM法

効率の良いデータ圧縮アルゴリズムとしてPPM法Prediction by Partial Matchingが知られています。PPM法は観測されたデータをもとにして次のデータを予測することにより圧縮を行うアルゴリズムで、たとえば「abracadabra」のあとにどういう文字が来るかを見積もるとき、次のような情報を利用します。

  • ⁠a」は5回、⁠b」は2回、⁠c」は1回出現している
  • ⁠a」の次が「b」である例は2つあり、⁠c」⁠d」であった例が1つずつある
  • ⁠ra」の次が「c」であった例が1つあり、それ以外の文字が出た例は存在しない
  • ⁠bra」の次が「c」であった例が1つあり、それ以外の例は存在しない

から判断すると次の文字は「a」である可能性が高そうで、から判断すると「b」である可能性が高そうで、から判断すると「c」である可能性が高そうです。もちろんそれ以外の文字が来る可能性もゼロではありません。

の情報だけを見ると、⁠a」のあとに「b」が来る確率は「c」「d」が来る確率の2倍と見積もることができます。⁠b」⁠c」⁠d」以外の文字が出現する可能性もあるため、表1のように文字の出現確率を予測することができます。の情報だけを見ると、⁠a」のあとには「c」が来る確率が最も高いと判断されるため、表2のように文字の出現確率を予測することができます。

表1の情報のみをもとにした出現確率
文字出現確率
b2/5
c1/5
d1/5
その他1/5 * 1/(256-3)
表2 ③④の情報をもとにした出現確率
文字出現確率
c1/2
その他1/2 * 1/(256-1)

PPM法では、このような予測値を重みをもって足し合わせることで総合的に出現確率を予測します。

統計情報がない場合はあらゆる文字に対して同じ長さのコードを割り当てる必要があるでしょうが、上記のような情報がある場合は「b」「c」には短いコードを割り当てるほうが効率が良くなります。PPM法では、上記のような統計情報を用いて次に来る文字の確率を見積もり、それによってコード長を変えることによってデータ圧縮を実現しています。

PPM法によるデータ圧縮は圧縮率が高いことが知られていますが、PPM法が圧縮に有効なのであれば、同じアルゴリズムを予測インタフェースに利用可能だと考えられます。これまでの入力文字列から次の入力文字を見積もることが可能になったり、これまでの計算機操作列から次の操作を予測することも可能になります。PPM法を用いた予測入力手法も提案されています[3]⁠。

予測を利用したじゃんけんシステム

PPM法のような予測手法は予測インタフェースの実装に有効であるだけでなく、じゃんけんのような対戦ゲームにおいて、相手が出した手の履歴から次の手を予測できる可能性があります。

PPM法を圧縮に利用する場合は次の文字の出現確率を細かく見積もる必要がありますが、じゃんけん勝負の場合は次にどの手が一番出やすいかを予測するだけでよいので、前述のような計算は必要ないと思われます。グー、チョキ、パーをそれぞれG、C、Pとすると、たとえばこれまでの履歴で「GCP」が10回、⁠GCG」が7回、⁠GCC」が4回観測されていた場合は、⁠GC」のあとは「P」が出やすいと判断することができるので、それに勝つためには「C」を出せばよいと判断できるでしょう。

このような考え方に基づいて、じゃんけん勝負システムを作ってみました図3次ページリスト1⁠。

図3 じゃんけん勝負システム
画像
計算機の手は計算済みだが、背景色を黒くしてユーザには見えないようになっている
画像
画像
ユーザが「パー」を押した。計算機は「グー」を出していたのでユーザの勝ち
画像
画像
ユーザが何度か「パー」を押すと、計算機は「チョキ」を出すようになる
画像
画像
その後は計算機は迷わず「チョキ」を出し続ける

単純なアルゴリズムですが、人間のクセをすぐに学習してしまうので、長く勝負していると人間に勝ち目はほとんどありません。

リスト1 じゃんけん勝負システム
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;
      charset=utf-8">
<title>じゃんけん勝負!</title>
</head>

<ul>
  <li>
    <div style="float:left;">計算機の次の手: </div>
    <div id="computer" style="width:100px;color:
         black;float:left;"></div>
    <br clear='all'>
  <li>あなたの手: 
    <input type='button' onclick='bet("g")' value="グー">
    <input type='button' onclick='bet("c")' value="チョキ">
    <input type='button' onclick='bet("p")' value="パー">
  <li>戦績: <span id="total">0勝 0敗 0分け</span>
</ul>
<blockquote>
  <table id='score'>
    <tr><th>計算機の手</th><th>あなたの手</th>
        <th>勝敗</th></tr>
  </table>
</blockquote>

<script type="text/javascript">
var level = 5;
var accum = [];
var C = [];
var U = [];
var win = 0, lose = 0, draw = 0;
var name = {'g':'グー', 'c':'チョキ', 'p':'パー'};

function add(c){ // ユーザの手を登録
  U.push(c);
  for(i=1;i<=level;i++){
    s = U.slice(U.length-i,U.length).join('');
    accum[s] = (accum[s] ? accum[s]+1 : 1);
  }
}

function show(){ // 勝敗を判断して戦績を表示
  c = C[C.length-1];
  u = U[U.length-1];
  if(c == u){
    r = '△'; draw++;
  }
  else if(c == 'g' && u == 'c' ||
          c == 'c' && u == 'p' ||
          c == 'p' && u == 'g'){
    r = '×'; lose++;
  }
  else {
    r = '◯'; win++;
  }
  document.getElementById('total').innerHTML =
    win + '勝 ' + lose + '敗 ' + draw + '分け';
  s = document.getElementById('score');
  e = document.createElement('tr');
  f = document.createElement('td');
  f.innerHTML = name[c];
  e.appendChild(f);
  f = document.createElement('td');
  f.innerHTML = name[u];
  e.appendChild(f);
  f = document.createElement('td');
  f.innerHTML = r;
  e.appendChild(f);
  s.appendChild(e);
}

function bet(v){ // ユーザが勝負
  document.getElementById('computer').style.
      backgroundColor = 'white';
  add(v);
  show();
  predict();
  setTimeout('nextround()',1000);
}

function predict(){ // 計算機の次の手を計算
  res = [];
  n = 0;
  for(var i=1;i<=level;i++){
    s = U.slice(U.length+i-level, U.length).join('');
    for(c in name){
      r = s + c;
      if(accum[r]){
        if(accum[r] > n){
          n = accum[r];
          res = [c];
        }else if(accum[r] == n){
          res.push(c);
        }
      }
    }
    if(res.length > 0) break;
  }
  c = res[Math.floor(Math.random() * res.length)];
  C.push(c == 'p' ? 'c' : c == 'g' ? 'p' : 'g');
}

function nextround(){ // 次の手を隠して表示
  var k = document.getElementById('computer');
  k.style.backgroundColor = 'black';
  k.innerHTML = name[C[C.length-1]];
}

function init(){
  for(i=0;i<level;i++){
    add(['g','c','p'][Math.floor(Math.random() * 3)]);
  }
  predict();
  nextround();
}

init();
</script>
</body>
</html>

まとめ

予測インタフェースの研究の歴史は古いのですが、入力補助以外にはまだあまり活用されていないようです。予測を行うためには各種の知識やデータが必要ですが、インターネット上の情報共有により、予測インタフェースに利用できるデータが近年格段に増えてきたと言えるでしょう。既存のデータを活用する方法はまだまだたくさんありそうです。

おすすめ記事

記事・ニュース一覧