待ち行列モデルを用いてセブンイレブンのコンサルティングをしてみた
2015年に大学の授業で、待ち行列モデルを用いてセブンイレブンのコンサルティングをした際の資料が出てきたので、出せる部分のみ編集して共有します。
問題設定
大学の最寄り駅近くにあるセブンイレブンを利便性の都合上よく使うのですが、当時の店員のオペレーションに不満を感じていました。それは二つレジがあるにもかかわらず原則一つのレジしか稼働しておらず、5人程度の列ができないと二つ目のサポートが入らない点です。
今回は「平均来店人数」と「平均レジ処理速度」を定義することで行列の数を再現する「待ち行列モデル」を用いて、①このセブンイレブンでどの程度の待ち時間が生じているか②仮に3人並んだ段階で2人体制になったら待ち時間がどの程度削減されるかーーを調べてみました。
実験
①このセブンイレブンでどの程度の待ち時間が生じているか
最初に実地調査をもとに、「平均来店人数」を1分間に1人、「平均レジ処理速度」を店員1人当たり40秒に1人と定義しました。そして共に指数分布に従うと仮定し、モンテカルロシミュレーションを実行します（理論の詳細は割愛します）。「エクセルのシート関数で処理しましょう」みたいな授業だったので、基本はExcelのシート関数で処理しつつ、難しかった部分はVBAで補っています。
この時の系内人数分布と待ち時間分布は下記のようになりました（グラフはRのggolot2で作成しました）。
系内人数分布
待ち時間分布
ここで、過去のアンケート結果を引用し、コンビニにおける「許容待ち時間」を3分と設定しました。この場合に、シミュレーション結果からは、許容待ち時間の3分を超える層が9.01%もいると判明しました。
②仮に3人並んだ段階で2人体制になったら待ち時間がどの程度削減されるか
ここでは「平均来店人数」と「平均レジ処理速度」の設定は変えず、3人並んだ段階で2人体制になるようにモデルを変更しました。
この時の系内人数分布と待ち時間分布は下記のようになりました。
系内人数分布
待ち時間分布
①の場合と比較すると下記のようになります。
系内人数分布
待ち時間分布
【論文メモ】Learning Document Embeddings With CNNs
論文名
Learning Document Embeddings With CNNs
[1711.04168] Learning Document Embeddings With CNNs
概要
教師なし文書埋め込みのためのCNNを用いたモデルの提案。既存アプローチは、複雑な推論を必要とするか、または並列化が困難なRNNを使用。CNNを用いることで、完全な並列化を実現し、より深いモデルを学習させられる。
『画像認識』（機械学習プロフェッショナルシリーズ）第5章まとめ
某所にて、『画像認識』（機械学習プロフェッショナルシリーズ）の勉強会（輪読形式）があり、第5章「分類」を担当しました。参考書の内容に加え、『パターン認識と機械学習 上』の内容も盛り込み、包括的に「分類」を扱いました。
下記の記事にまとめた部分など、参考書に具体例が記載されていない部分については、自らPythonで具体例の実装もしています。
【論文メモ】AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-label Classification
論文名
Yukihiro Tagami: AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-label Classification, KDD’17, pp.455-464, August 13–17, 2017, Halifax, NS, Canada.
どんなもの？
ラベルの種類数が膨大な場合（10^4 - 10^6）のマルチラベル分類問題に対し、高速かつ精度良く予測を行う分類器を提案
先行研究と比べてどこがすごい？
Sparse Local Embeddings for Extreme Classification (SLEEC) [4] の3つの問題点を解決
- SLEEC only uses feature vectors and does not access label information
- SLEEC’s optimization process for learning regressors is slightly complicated because of sparsity-induced and rank-constraint regularization terms.
- Much faster prediction is preferable for scaling up to solve Web-scale classification problems
技術や手法のキモはどこ？
k-nearest neighbor graph (KNNG)
どうやって有効だと検証した？
Extreme Classification Repository [5]のデータを使い検証。予測時間と精度の両者の向上が確認できた。
(At the same level of accuracy, the prediction time of AnnexML was up to 58 times faster than that of SLEEC)
[5] Kush Bhatia, Himanshu Jain, Yashoteja Prabhu, and Manik Varma. 2016. The Extreme Classification Repository. (2016). Retrieved January 15, 2017 from https://manikvarma.github.io/downloads/XC/XMLRepository.html
議論はある？
More complex nonlinear models, such as kernel machines and deep neural networks に取り組みたい
次に読むべき論文は？
[4] Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma, and Prateek Jain. 2015. Sparse Local Embeddings for Extreme Multi-label Classification. In Proceedings of the 28th International Conference on Neural Information Processing Systems.
【補足/論文・動画など】ヤフー/Yahoo!の人工知能（AI）技術「アネックスエムエル」(AnnexML)
第5回将棋電王トーナメント決勝トーナメントのYorkie辞退騒動の経緯まとめ
認識違いの点などあれば、コメントなどでご指摘ください。詳細は、タイムシフトで確認を。
－－－
経緯
- 決勝トーナメントのYorkie VS shotgun戦「256手ルール」の問題の発生しYorkieが敗北
- 運営が「ソフトの”独自性”の問題でYorkieが5位決定トーナメント以降の大会を辞退する」と発表
- 他ソフトの開発者がYorkieの開発者に対し「Yorkieには十分な”独自性”がある」と辞退撤回を要望
- 議論が紛糾するも最終的にはYorkieの開発者の意向が尊重され、Yorkieは5位決定トーナメント以降の大会を辞退
解説
大きく分けて二つの論点がありました。結論から言うと、Yorkieの開発者は1については納得し、2について十分な独自性がないと判断し、自主的に辞退したとのことです。
- 「256手ルール」の問題
- ソフトの「独自性」の問題
「256手ルール」の問題
第5回将棋電王トーナメントのルール(PDF)には、第22条として以下の規定があります。
予選リーグ、決勝トーナメント共に、256 手を超えて、対局が続く場合、立会人がどちらのソフトの負けとも判定せず、千日手でもないときは、その対局を引き分けとする。
昨日の予選リーグのPonanza VS 平成将棋合戦ぽんぽこ戦では、257手時点でPonanzaが「宣言勝ち」できる状況でしたが、上記の通称「256手ルール」が適用され、立会人の判断の元で引き分けを判定されました。
そして今日の決勝トーナメントでは、Yorkie VS shotgun戦で257手目で詰むという勝負になりました。解説者含め多くの方は昨日通りに「256手ルール」が適用され引き分け→再戦になると思いましたが、今回は（昨日とは別の）立会人の判断の元、Yorkieの負け判定が下されました。
この裁定のブレについては、さまざま議論がありましたが、Yorkieの開発者の方は「事前にルールを把握しており、256手では勝負がつかないと分かった際にも、対戦相手のshotgunの開発者と”どうなるのかなあ”と話していた」というようなコメントをしており、この件については納得しているとのことでした。
ソフトの「独自性」の問題
「256手ルール」とは別の軸で、ソフトの「独自性」の問題があります。第5回将棋電王トーナメントのルール(PDF)の第2章「参加資格」第3条には、以下の規定があります。
参加ソフトは、思考部について、自力で十分な工夫を施したものに限る。
「思考部」は以下のように定義されています。
指し手生成部、および、学習部のうち、使用可能ライブラリと定跡データを除いた部分
ただし、使用可能ライブラリを改造して用いる場合は、その改造した部分も含む
参加申し込み時点のYorkieのPR文書(PDF)では「KKPPT形式の手番ありの4駒関係」が「独自性」として記載されていました。また「その他」の部分には「なるべくconstexpr化して、コンパイラによる高速化に期待する」とも書いてありました。
運営による1の問題発生後の”独自性”確認
なぜこのタイミングだったのかが議論を紛糾させる要因だったと思います。1の問題発生後の5位決定トーナメント開始前に、運営によりYorkieの”独自性”確認が実施されたそうです。その場において、YorkieのPR文書内に記載されていた「KKPPT形式の手番ありの4駒関係」が実装に至っておらず、Yorkieは「探索部：やねうら王＋評価部：elmo」という構造で、十分な独自性がないと判明。運営とYorkieの開発者の話し合いの結果、Yorkieの開発者から5位決定トーナメント以降の大会辞退の申し出があったそうです。
しかし運営からその発表があった直後、平成将棋合戦ぽんぽこの開発者を中心に「探索部を高速化している件（PR文書の「その他」に記載あり）は、十分な”独自性”ではないのか」という意見が出ました。「実際に第3回大会では、Aperyの探索部の高速化が”独自性”として認められた前例もある」と根拠を示しています。
探索部「やねうら王」の開発者のツイート
Yorkieのソースコード、やねうら王にmergeした場合、おそらく3〜5%ぐらい速くなりますね。個人的には十分な独自性だと思いますけども、まあ、辞退に関してはご本人の意思を尊重すべきかと..。(大会終了後、Yorkieのコードをmergeさせていただくことになっています。)
— やねうら王 (@yaneuraou) 2017年11月12日
議論は続きましたが最終的には、Yorkieの開発者が「高速化には一定の独自性があると思うが、定量的な評価はできておらず、参加できる十分な”独自性”があるとは言えない」という姿勢を崩さず、辞退のまま大会が続行されることになりました。
憶測
コメントなどでは「1の問題をうやむやにするため、運営がこのタイミングでYorkieの”独自性”確認を実施し、Yorkieに辞退させようとしたのでは」という憶測が出ています。この憶測は憶測の域を出ませんが、凄く筋が通っているように見えます。
所感
個人的には、二つの問題を明確に切り分けて議論すべきだと思います。前者については、ルールの解釈問題で難しいですが、個人的には予選と同様に引き分けの処理をすべきだったと思います。そして後者については、運営が実際の大会予選開始前に、「独自性」の確認タイミングを設けなかったのが最大の問題かと思います。またそもそも論ですが、こういった強いソフトを目指す大会に「独自性」を求める規定が必要なのかも疑問です。強さだけが正義なのではないかなと。何が「独自性」かという定義も難しいですしね……。
今回浮かび上がった問題を受けてルールや運営方針を見直し、今後より良い大会として存続していってほしいと思っています。
【論文メモ】同義語を考慮した日本語の単語分散表現の学習
論文名
田口雄哉, 田森秀明, 人見雄太, 西鳥羽二郎, 菊田洸: 同義語を考慮した日本語の単語分散表現の学習, 情報処理学会研究報告, Vol.2017-NL-233 No.17, 2017.
どんなもの？
訓練済みの単語分散表現を用い，同義語対を用いた日本語の単語分散表現の fine-tuning を行なう．単語分散表現の評価は，日本語の単語類似度データセットを用いて行った．実験の結果，同義語対を考慮した学習手法を適用することで，既存の単語の分散表現よりも質が改善することを確認した．
先行研究と比べてどこがすごい？
分布仮説にもとづいた学習を行なった場合，同義語や対義語に関わらず，同じ文脈に現れる単語は，似たようなベクトルになってしまうため，単語間の類似度を測る際に影響が出てしまう．その対策として，WordNet などの意味辞書から獲得した同義語対を用いて単語の分散表現を fine-tuning する手法が提案されているが，日本語での効果は報告されていない．
技術や手法のキモはどこ？
Faruqui ら [7] が提案している Retrofitting
Faruqui, M., Dodge, J., Jauhar, S. K., Dyer, C., Hovy, E. and Smith, N. A.: Retrofitting Word Vectors to Semantic Lexicons, Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Association for Computational Linguistics, pp. 1606–1615 (2015).
どうやって有効だと検証した？
データとして，Sakaizawa らが公開している日本語単語類似度データセット [19], [24] で評価を行なう．単語の分散表現は，公開されている日本語の訓練済み単語分散表現に加え，word2vec [13], [14] と Glove[17] を用いて実験を行なう．評価は，人手でアノテーションされた単語の類似度と，単語の分散表現を用いたコサイン類似度を，スピアマンの順位相関係数によって行なう．
議論はある？
副詞においては，自動で構築した同義語対を用いた場合，Skip-gram，Glove，そして fasttextにおいてスピアマンの順位相関係数が悪化している．理由としては，副詞の評価データの24語彙のうち，18 語彙が自動で構築した WordNet の同義語対に存在しているが，その中の 5 つの語彙全てがそれぞれの同義語対になっているため，どの単語もほぼ同じベクトルになってしまったことが原因と考えられる．
今後の課題は，Nikola ら [16] が提案している同義語と同時に対義語も考慮して単語の分散表現の Fine-tuning を行なうといった手法の適用が考えられる．しかし，日本語において，筆者らが知る限り，大規模な対義語対のデータは存在しない．そこで，今後は日本語の単語の分散表現を改善するために対義語データの構築を行なう．
次に読むべき論文は？
Faruqui, M., Dodge, J., Jauhar, S. K., Dyer, C., Hovy, E. and Smith, N. A.: Retrofitting Word Vectors to Semantic Lexicons, Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Association for Computational Linguistics, pp. 1606–1615 (2015).
