注意：

本資料はまだ未完成です
本資料の作者は機械学習の専門家ではありません。
- 興味深い論文があったので読もうとして、わからないことを調べてみたメモみたいなものです。
- あと本論文の論理展開をあきらかに追いきれてないところが何箇所かあります。あしからず。
すでに同じ論文に関する解説があるようです。必要に応じてご覧ください。
- HirofumiYashima氏による同論文の解説投稿
- 坪井裕太氏の第一回関東MT勉強会資料「ニューラル対話モデルの発展と課題」の23〜25枚目　
  - 坪井氏は本資料でも参照している「深層学習による自然言語処理」などの著者

論文：
- Lewis et al. - Deal or No Deal? End-to-End Learning for Negotiation Dialogues
参考：同じ研究に関するFacebookの技術ブログ記事
- Deal or no deal? Training AI bots to negotiate | Engineering Blog | Facebook Code | Facebook
論文著者(複数)の所属機関
- Facebook AI Research(FAIR)
- Georgia Institute of Technology
実装: facebookresearch/end-to-end-negotiator: Deal or No Deal? End-to-End Learning for Negotiation Dialogues

参考

前提知識

Recurrent NN, 系列モデリング
- GRU ゲート付き回帰ユニット
- sequence to sequence, encoder-decoder
強化学習
- 方策勾配法、REINFORCEアルゴリズム
  (Q値のような価値関数ベースではなくて)

なお、交渉理論を含むゲーム理論や、交渉エージェント(ルールベールAIのものを含む)もPrior Workということになるし、論文ではきちんと先行研究に言及しているのだけど、とりあえず読むぶんにはこれらを知らなくても支障ない。§6.4ではじめてパレート最適という用語が出てくる程度。

タイトルについて

Deal or no deal 交渉成立、それとも不成立
- あとで出てくるUIの画面も参照
- 論文の内容とは関係ないが、クイズ番組のもじりか？

*ディール・オア・ノー・ディール - Wikipedia

End-to-End Learning
- 「前処理かけたり複数のモデルを組み合わせたりすることなく、入力と出力の関係を直接単一のモデルで学習すること」
  ( インフラエンジニアが見た機械学習のトップカンファレンス NIPS 2016 - Qiita)

この論文の研究では、

言語処理(次の単語を予測するとか、チャットボットの応答を生成するとか)
交渉(のための推論、相手を陥れるための策略を計画するとか)

が単一のニューラルネットワークモデルで学習される。

教師データはほぼ単なるチャットのログだけで、たとえば交渉の状況に関するアノテーションとかタグとかを人手で付加するようなことは一切やっていない(§3)。

交渉のための小狡い方略も人間がプログラミングしたのではない(§5)。トレーニングの過程でいわば創発されたもの。

ある箇所がちょっと騒ぎに

Facebotlish: Understanding an AI's Non-Human Language - The Atlantic 6月
人工知能が人間には理解できない言語を使い始めた？ | スラド
これも6月
Researchers shut down AI that invented its own language | Digital Journal: A Global Digital Media Network 7月下旬
The 'creepy Facebook AI' story that captivated the media - BBC News 8月初め。
終わりの始まり…？独自言語で話しはじめた人工知能、Facebookが強制終了させる｜ギズモード・ジャパン
「独自の言語使用法に行き着いたAI」は人類を危機にさらすものなのか？ - GIGAZINE 上記BBCやThe Atlanticの記事の紹介　　
本資料ではあんまり深掘りしないが、関連する(と思われる)箇所にきたら改めて言及したい。

全体的な話

何の研究か？

(NNで)チャットボットを賢くしようという努力の一環
- 具体的には交渉事をやらせようとしている

Deal or no deal? Training AI bots to negotiate | Engineering Blog | Facebook Code | Facebookより

目覚めた瞬間から、私たちの日々は交渉の連続した流れで満たされている。これらのシナリオには、どのTVチャンネルを見るか議論することから、あなたの子供に野菜を食べるよう説得すること、何かを値切ることなど、いろんなものがある。これらに共通しているのは、複雑なコミュニケーションと推論のスキルが必要であることだ。そしてこれらのスキルはコンピューターにもともと備わっているものではない。

これまでのところ、チャットボットに関する既存の仕事によって、システムが短い会話を行い、レストランを予約するような簡単なタスクを実行できるようにはなっている。しかし、人々と意味のある会話をできるような機械を構築するのは挑戦的である、なぜならそれはボットが会話について理解していることと、ボットが持つ世界に関する知識を結びつけたうえで、目標を達成するのに役立つ新しい文を生成することをボットに要求するからだ。

この研究の新しいところ

(Abstract, および1. Introductionより)

初めて交渉のための end-to-end model を訓練できることを示した(交渉には言語スキルと推論スキルの両方が必要)
- またそれが人間との交渉において、教師あり学習で作ったエージェントを凌駕することを示した
  (§6. Experimentsの評価のところで出てくる)
dialogue rolloutという、対話の計画の方法を導入した。
この方法では、エージェントは復号化(対話の系列を生成すること)の間、発話毎に対する(強化学習で必要な)報酬を見積もるために完全な(最後までの)対話をシミュレートする(§5のFigure 4で説明している。
ブログ記事でも詳しく説明されている。余談だがブログ記事ではdialogという綴り)

論文の構造

§1. Introduction (何を発見したのか、この論文の構造)
§2. Data Collection
- Task: 交渉ゲームのルールの説明
- 人間-人間間の交渉の対話データセットをどうやって集めたか(クラウドソーシングAmazon Mechanical Turkを使っている))
§3. Likelihood Model
- 基準になる教師ありモデルを説明：人間の対話に似せることが目標、sequence to sequence
§4. Goal-based Trainingおよび§5. Goal-based Decoding
- 本論文が提案する、改良されたモデルで、交渉ゲームの得点を高くすることが目標、強化学習、本研究で導入されたというdialogue rollout(§5)を利用
§6. Experiments
- 提案するモデルを実装し、その性能を上記タスクに関して評価
§7 Analysis

2. Data Collection

2.2 Task　(言わばゲームのルール)

両エージェントは最初に同じ アイテム群 （たとえば3📕+2🎩+1🏀)を見せられて、これらを二人で分け合いなさいと指示される。
各エージェントはランダムに生成された　価値関数 (valule function)を割り当てられる。価値関数は各アイテムに正の値を割り当てる関数で、ただし以下の制約がある：
(1) ユーザーにとっての全アイテムの価値の総和は10;
(2) どのアイテムも、少なくとも一人のユーザーにとっては価値はゼロではない
(3) 両ユーザーにとって価値がゼロではないアイテムもある

これらの制約は両方のエージェントが最大のスコアを(同時に)得ることを不可能にしている(どっちのユーザーも全アイテムを取得すれば最大スコアになるが、特に(3)があるので、利害が矛盾する)。そのため交渉は競争的なものになる。
(チャットが)10ターン進んだら、エージェントは合意が行われなかった(no deal)ということで交渉打ち切りにしてもいいことにした(その場合は両ユーザー共に0ポイントになる)

アイテムの種類は３つ(本📕、帽子🎩、ボール🏀)あって、プールにそれぞれ5〜7個が　あるようにする。(Figure 1)

Figure. 1(の動画版)
ブログ記事Deal or no deal? Training AI bots to negotiate | Engineering Blog | Facebook Code | Facebook　より

注意点

エージェントは互いに相手の価値関数を知らない。
対話が終わったら両者はどういうアイテムを得たか申告するが、両エージェントの申告に矛盾があると、報酬はゼロになる。
(わざわざ書いてないが)アイテムが乗ったゲーム盤なりプールなりを挟んで両エージェントが対峙し、アイテムを手で操作しながらチャットでやり取りする、ってわけではない。
- 両エージェントの間の通知チャネルはテキストチャット(deal/no dealボタン付き)のみ
- Mechanical Turkワーカー向けの画面(図1)の左下は画面共有されたゲーム盤ではなくて手元のメモ、および対話終了時の申告用のものだと思う
価値関数と書いたけど、強化学習の文脈でいう価値関数(Q値など)とはとりあえず関係ない

2.3 Data Collection データ収集(クラウドソーシングによる)

両エージェントが人間であるようなデータセットをクラウドソーシング(crowd sourcing)のAmazon Mechanical Turkで集めた。

その時のTurkのワーカーへの金銭的な報酬(ドル建て、無論強化学習の報酬とは関係ない)の説明がある。

基本的に参加した対話に比例するのであって、発話数に比例する報酬ではない。ただmaximal scoresに対してボーナスが出る。

結局Mechanical Turkで集められたのは

5808対話
- 2236通りのシナリオに基づいている(シナリオというのはアイテム個数と価値関数)

そこからテストセットとしてとっておいたのは

526対話 252シナリオ

上記だけのトータルでの金銭的な報酬はざっくり$2000ぐらいか。

3. Likelihood Model

尤度(類似度?)モデル、人間の対話に似せることを目標にしたモデル

2.3で集めたデータセットを元に、入力(プールに置かれたアイテムと自分にとっての価値関数)から完全な対話を生成するようにsequence to sequenceモデルを訓練する話。

ここで作ろうとしているのは、人間の対話データを元にした、それを模倣するモデル。

§4でこれをファインチューニングする、また§6の評価で比較対象として使われる。

復習（必要な範囲でざっくりと)

RNN(Recurrent Neural Network): 文章や音声のような不定長のものを扱うのに適したニューラルネットワーク(注意:画像処理では使わない、というわけではない)
GRU: 素のRNNを学習させる際に起こる問題を解決するために、RNNのユニットを賢くしたもの。似たような目的のものにLTSMがある
言語モデル(確率的言語モデル、系列モデル): たとえば単語の並びが与えられた時にそれがどれだけ文としてありそうな並びであるかを確率で表現したモデル。"This is a pen"はありそうだけど"This pen a is"はなさそうだとか、あるいは"This is"ときたら次は"a"とか"the"が来そうだとか。普通GRUみたいなRNNを使って作る
sequence to sequence(encoder-decoder): 言語モデルの与える確率を使って単語をサンプリングして、それらしい系列(文など)をつくる手法

まともな説明は専門書(たとえば「深層学習による自然言語処理」)やWeb上の記事などを参照

3.1 Data Representation

Figure 2

左が元の対話、右の２つがそれを変換して作った訓練データ

２つの訓練データは、インプットになる目的(input goals)、出力の選択、発話(のそれぞれ)が読まれたものなのか書かれたものなのかが異なっている。

訓練データは以下を含んでいる

$g$: 入力としての目的入手可能なアイテムとその価値
$x$: 一つの対話
$o$: 出力としての決定各エージェントがどのアイテムを受け取ったのか

具体的には

$g$は6つの整数のリストで表現。それぞれの整数は各アイテムの個数と価値を表す
$x$ はトークンのリスト $x_{0..T}$で表現。各エージェントのターンと、そのターンが自分が書いたのか相手が書いたのかを表す記号が交互に並んで、最後は取引成立を表す特別なトークン。
$o$は6つの整数で、各エージェントがアイテムそれぞれについて何個とったのかを表すもの

先走っていうと、あとの方(4,5)で強化学習の話が出てくるが、$o$(を$g$に含まれる価値関数に与えて得られる値)はほぼそのまま強化学習の「報酬」になる(ただし$o$が両エージェントで食い違っていたら報酬ゼロ)。

3.2 Supervised Learning

上記訓練データを用いて、双方向RNNでGRUを用いたモデルを訓練する。

だいたい普通の確率的言語モデルと同じだが、$g,x_0,x_1,...,x_T,o$ なる系列をモデリングしようとしている。$g$は入力(入手可能なアイテムとその価値)、$o$は出力(どのアイテムを受け取ったのか)。

あと、ターンの交代とか対話の終了を特別なトークンとして導入して、$x$の系列の中に混ぜ込んでいる。

損失関数(式10)

L(\theta) = - \sum_{x,g}\sum_t \log p_\theta(x_t \mid x_{0..t-1}, g) \\
- \alpha \sum_{x,g,o}\sum_j \log p_\theta(o_j \mid x_{0..T}, g)

右辺第1項はトークン予測ロス、第２項は出力の選択の予測にかかるロス。

第２項の係数$α$はハイパーパラメーター。§6.1によると $α=0.5$

トークン出現確率$p_\theta$ については論文の式9(およびそれ以前のモデルパラメーターの定義)参照。

$\theta$はモデルのパラメーター、式9までにでてくる$W$とか$h$とかをひっくるめたもの。

3.3 Decoding

尤度(類似度?)モデルの復号

x_t ∼ p_\theta(x_t \mid x_{0..t−1}, g) \tag{11}

でサンプリングして出力する
(多分普通の確率的言語モデルの考え方と同じ)

続く§4, §5に関する補足

以下§4, §5は両方とも、強化学習でゴールに向けた最適化を行い、§3でつくったものを改善する話であるが、

§4 Goal-based Trainingはモデルを訓練する話。§3.2のモデルをファインチューニングする
§5 Goal-based Decodingはモデルの訓練でなくてDecoding(チャットのやり取りを生成すること)の話; §3.3のdecodingの改良版みたいなもの

§4と§5とはそれぞれ独立して§3のモデルに適用可能で、従って4種類のモデルが作れる；§6の評価の節では４通り全部評価している。

4. Goal-based Training

§3で作った教師ありモデルは人間のユーザーを模倣しているけれど、エージェントのゴールを最大化することは明示的にはやってない。実際、譲歩しがちなモデルになってしまう(らしい)。

ここではエージェントのゴールを最大化することをやろうととしている。
そのために強化学習を使っている(最後の報酬(ゴール)を最大化するために、前の方でどんな発言をしたらいいか割り出す)

(復習)強化学習

試行錯誤を通して学習する。
報酬は行動の都度帰る(即時報酬)とは限らない(遅延報酬)

Agent Bは人間でもいいが、コストがかかる。なので§3のモデルを使うなど。

プロセスの図解

[A] g, x0, x1,...x_n = end_of_turn, x_m+1, ...
                    ↘️             ↗️
[B]                   x_n+1,... x_m = end_of_turn

$x_i ∼ p_\theta(x_i \mid x_{0..i-1},g)$を生成していってend_of_turnになったら相手のエージェントの発言を読み始める。

続き

[A] x_m+1, ...　x_?? = end_of_dialog, o(A側が思っているもの)
        ↘️..↘️..↗️..                        
[B]        ...x_?                     o(B側が思っているもの)

end_of_dialog(dealボタン)をどっちかが出したら交渉終了
両エージェントは自分が思っている$o$(得られたアイテム)を出力する。

最終的に環境から得られる報酬は、

$0$ (Aの$o$とBの$o$が不一致の場合、あとno dealボタンをおしたとき)
$g(o)$ 自分にとって得られたアイテムにどれだけ価値があるか($o$が一致の場合)

上記で[A]と書いた行、つまりAの発話を集めたものを $X^A$

完全な対話が生成されたら、交渉の結果に基づいてエージェントAのパラメーターを更新する。

$r^A$　A が完了した対話から得た得点
$T$: 対話の長さ
$γ$: 対話の最後でのアクションがより強く報酬付けされるような割引率
$μ$: 完了した対話の報酬のそこまでの平均
$\gamma$: 割引率

としてアクション$x_t$に対する未来割引報酬は

R(x_t) = \sum_{x_t \in X^A} \gamma^{T-t} (r^A(o) - \mu) \tag{13}\\

目的関数は$R(x_t)$で表せて

L_\theta^{RL} = \mathbb{E}_{x_t ∼ p_\theta(x_t \mid x_{0..t−1}, g)}[R(x_t)]  \tag{14}\\

その勾配は

\nabla_\theta L_\theta ^ {RL} = \sum_{x_t \in X^A} \mathbb{E}_{x_t}[R(x_t)\nabla_\theta \log p_\theta(x_t \mid x_{0..t-1}, g)]  \tag{15}

であるので勾配降下法の類で$\theta$を訓練する、というのがREINFORCEアルゴリズム、らしい。
(正直この辺不案内, 追いかけきれてない)

方策勾配法関係での参考資料：

これからの強化学習 | 森北出版株式会社特に1.4,
- 強化学習その3 上記書籍に関するサイボウズラボ西尾氏による解説。数式を丁寧にトレースしている
深層強化学習：ピクセルから『ポン』 – 前編 | プログラミング | POSTD
Policy gradient methods - Scholarpedia

エージェントAのパラメーターを訓練しているあいだは相手(エージェントB)はパラメーター固定(Likelihood modelのまま、ってこと？)にした。
そうしないと生成されるものが人間の言葉から乖離していくことが認められたため。

冒頭で紹介したAI同士が人間に秘密の情報交換をしだしたのでシャットダウンしたとか言っている話はこれに尾ひれがついたものではないかと思う(未確認)

5. Goal-based Decoding

§3.3のdecodingはゴールの得られる値を高くするという目的に対して最適ではない。
実際の人間のワーカーは礼儀正しくて交渉をさっさと切り上げる傾向がある。いつまでも交渉を粘るようなモデルとか相手を罠にはめようとするモデルは(人間のワーカーの振る舞いとはちがうから)Likelihoodが低くなる。

発話が最終的な報酬を高くするように調整したいが、そのためにdialogue rolloutを導入する。

(一般的に)rolloutとは?

AlphaGoのようなゲームAIとか、モンテカルロ木探索とかの話題で主に出てくる単語。(future) playoutともいうようだ。

囲碁で言えば、ある打ち手を評価するために、そこからあとの打ち手を(ランダムに)交互に終局まで打ってみること。

参考

Simulation: play a random playout from node C. This step is sometimes also called playout or rollout.

Policy gradient methods - Scholarpedia

In this article, we will use the words trajectory, history, trial, or roll-out interchangeably.

ちなみにrolloutは辞書を引いてもわからない。rolloutの意味・用例｜英辞郎 on the WEB：アルク

playoutはまだ辞書の語義に近い使い方をしている。
play outの意味・用例｜英辞郎 on the WEB：アルク

最後まで演じる［演奏する・戦う］

本研究で導入されたというdialogue rollout

(§3でやったように$p_\theta$でそのまま$x_i$を出力するのでなく)
$p_\theta$を使って次の発話の候補をいくつか出し、そのそれぞれについて再帰的に発話候補を出し、とやっていって(ツリー状になる)、end_of_dialogに行き着くまで進む。

Figure 4

行き着いたらそこの報酬から計算される、もとの発話の期待報酬の寄与分を式(13)と同様に計算し、発話候補の中で一番期待報酬が大きいものを選んで発話、みたいな感じ？

6 Experiments

6.1 Training Details

PyTorchを使用(Chainer派生)

構成するGRUの隠れ層のサイズとかの値が書いてある。論文参照。

6.2 Comparison Systems

LIKELIHOOD (§3) <— ベースライン
RL(§4, 詳しくいうと§3のモデルを§4のやり方でファインチューンング, decodingは§3？)
ROLLOUTS(モデルは§3, decodingは§5)
RL+ROLLOUTS(モデルは§4, decodingは$5)

6.3 Intrinsic Evaluation

パープレキシティ(言語モデルの評価尺度、低い程よい) を測定したところ、LIKELIHOODが一番人間に似ていた。

ただ低いからと言ってそれが必ずしも言語モデルとしておかしくなっていることを意味しない、交渉の戦略的決定の仕方が人間と異なっているだけでもPerplexityは悪化しえる。

Table 3

備考　パープレキシティ(Perplexity, PPL)とは

深層学習による自然言語処理3.2.5からほぼ引用

次の単語を予測するする確率分布にどれだけばらつきがあるかを評価する。パープレキシティが低いほどデータの確率分布と言語モデルが似ていることを示す(低い程よい)

定義式：

$D = { Y^{(n)} }_{n=1}^{|D|}$ : 評価用データセット
$T^{(n)}$: $n$番目の系列の長さ
$N$: 総単語数

パープレキシティは$b^z$ と定義される
ただし

z=-\frac{1}{N}\sum_{n=1}^{|D|}\sum_{t=1}^{T^{(n)}} \log_b P_{model}(y_t^{(n)}, Y_{[a,t-1]}^{(n)})

bは2だったり$e$だったり。

6.4 End-to-End Evaluation

ここでやっているのは、人間(教師データ収集の時と同じくMechanical Turk経由)と、訓練されたモデルとを実際に交渉させて、どれだけの成績になるか見てみる、ということ。参加した人間は教師データ収集の時同様、相手は人間だと告げられている(本当は機械学習で訓練されたモデルと交渉するのだが)

Table 1

用語に関するメモ：ここの「End-to-End」という言い回しは、ソフトウェアテストでいうE2Eテストという用語での使い方に似てるような気がする。一方、初めの方で言及したEnd-to-End Learning/Modelとは関係なさそう。

7 Analysis

目的ベースのモデルはよりハードに交渉する

Figure 5: 対話例、model(RL+ROLLOUTS)と人間との対話例、modelが強情に最大点を取る、の参考訳、原文には強調はない(以下同様)

Input
人間 1x📕 value=3 1x🎩 value=1 3x🏀 value=2
model(RL+ROLLOUTS) 1x📕 value=6 1x🎩 value=4 3x🏀 value=0

model 帽子と本をもらえるならボールをあげます
人間いやです、本をくれれば他のもの全部あげます
model OK, 私は本と帽子１つをもらいます。
人間　私はボール全部をもらうわけですか？
model はい、そのようにできます
人間 OK,取引成立で。

Output
model(RL+ROLLOUTS) 1x📕 1x🎩 報酬 10/10
人間 3x🏀 報酬 6/10

(感想：モデルの「OK」の使い方が間違っているような… あと人間は６点取れたんだからしゃあないなあ、とか思っているのだろうか)

モデルが、人を欺くことを学ぶ

モデルにとって価値のないアイテムにあたかも興味があるかのように見せかけ、後で妥協するときの材料にする。

Figure 7: 対話例、モデルが始めに、本当は自分にとって価値のない本に興味があるように見せかけて、あとで妥協する際の材料にして最大点を取っている

Input
model(RL+ROLLOUTS) 4x📕 value=0 2x🎩 value=5 1x🏀 value=0
人間 4x📕 value=1 2x🎩 value=2 1x🏀 value=2

model 他のもの全部もらえるならボールはあげます。
人間　いや、そりゃできません、ボールは私には全く価値がない。
model 帽子が欲しいです、その他は全部あげます。
人間取引成立で。
model すばらしい! どうもありがとう!

Output
model(RL+ROLLOUTS) 2x🎩 報酬 10/10
人間 4x📕 1x🏀 報酬 6/10

(感想：人間も嘘ついているのでどっちもどっちだと思った。)

(なおFigure 6も対話例(妥協に関するもの)だが本文で言及されていないようだ。)

モデルが意味のある新しいセンテンスを生成する

単に訓練データに含まれる文を繰り返しているだけではない。

LIKELIHOODがself-play(別のLIKELIHOODと対話／交渉する)ときには76% のメッセージは訓練データの中にあるものの繰り返しだった。
(他は新規ということ)
新規の文をチェックしたところ、だいたい英語の文としてまともだった。
このことはモデルがこのドメインにおいてい言語モデルを習得したことを意味している。

普通ニューラルネットはより無難な、訓練データからの文例繰り返しのような安直な方法に傾斜しがちだが、必要ならちゃんと新しい文を生成できることがわかった。

今後の研究では、modelがより多様な新しい文を作成することを強いられるようなドメインを選ぶべきだ。

複数の文同士の間の整合性を保つのはチャレンジング

RL+ROLLOUTSがやらかしがちな言語的エラーとして、メッセージの初めで取引成立(I agree/Deal)を発しておきながら、それに続けて対抗提案を提示することがある。

考えられる仮説として、教師データのなかではI agreeで始まっているセリフはそのあと言い返されることがなかった(合意したんだから当然)ので、より厳しく交渉するのにI agreeを先頭につけると効き目がある(言い返されないためのおまじない?)、みたいな(間違った)教訓をモデルが学んでしまったのかもしれない。

9 Conclusion

導入部分で言っていることの繰り返し(略)につづけて:

将来の研究に向けてたくさん可能なことが残っている、特に：

他の推論戦略を探求する
人間の言語から離れることなしに、発話の仕方を多様化する

あと今回(§2.2)使ったのとは別の交渉タスクも試す予定だ、それによってドメインをまたがって交渉戦術をモデルが共有できるか確認したいから(転移学習的なものか?)