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.

2017-11-15

Yahoo!の人工知能（AI）技術「アネックスエムエル」(AnnexML)

論文メモ

下記記事で報じられたヤフーの人工知能（AI）技術「アネックスエムエル」(AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-label Classification)に関する補足。

r.nikkei.com

カタカナで「アネックスエムエル」と表記しているため、本日朝時点でほとんどヒットしなかった。

f:id:upura:20171115094636p:plain

概要

ラベルの種類数が膨大な場合（10^4 - 10^6）のマルチラベル分類問題に対し、高速かつ精度良く予測を行う分類器

おわりに

取り急ぎ自分用まとめ。~~暇な時に見る。~~

2017-11-12

第5回将棋電王トーナメント決勝トーナメントのYorkie辞退騒動の経緯まとめ

その他

認識違いの点などあれば、コメントなどでご指摘ください。詳細は、タイムシフトで確認を。

live.nicovideo.jp

－－－

経緯

決勝トーナメントの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に辞退させようとしたのでは」という憶測が出ています。この憶測は憶測の域を出ませんが、凄く筋が通っているように見えます。

所感

個人的には、二つの問題を明確に切り分けて議論すべきだと思います。前者については、ルールの解釈問題で難しいですが、個人的には予選と同様に引き分けの処理をすべきだったと思います。そして後者については、運営が実際の大会予選開始前に、「独自性」の確認タイミングを設けなかったのが最大の問題かと思います。またそもそも論ですが、こういった強いソフトを目指す大会に「独自性」を求める規定が必要なのかも疑問です。強さだけが正義なのではないかなと。何が「独自性」かという定義も難しいですしね……。

今回浮かび上がった問題を受けてルールや運営方針を見直し、今後より良い大会として存続していってほしいと思っています。

2017-11-10

【論文メモ】同義語を考慮した日本語の単語分散表現の学習

自然言語処理論文メモ

論文名

田口雄哉, 田森秀明, 人見雄太, 西鳥羽二郎, 菊田洸: 同義語を考慮した日本語の単語分散表現の学習, 情報処理学会研究報告, 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).

2017-11-10

【遊戯王デュエルリンクス】修正されたスキル「バランス」で50回戦った初期手札の分布　スクリーンショットからPythonで自動集計

python デュエルリンクス

11月6日のアップデートで、スキル「バランス」に一定のランダム性が付与されたそうです。どの程度のランダム性が付与されたかを調べるため、初期手札の分布を集計しました。

使用デッキ

f:id:upura:20171110075543p:plain
モンスター10枚・魔法5枚・罠5枚デッキで、スキルは「バランス」です。

集計方法

デュエルを始めた際の初期手札の画面でスクリーンショットを撮影し、下記のPython スクリプトで自動集計しました。
upura.hatenablog.com

集計結果

f:id:upura:20171110080504p:plain
※ 0: モンスター, 1: 魔法, 2: 罠

修正前の効果だと、確定でモンスター2枚・魔法1枚・罠1枚になっていました。今回の調査で従来通りの配分になったのは36回（72％）で、以下のようなランダム性がありました。

モンスター2枚・魔法2枚……5回
モンスター3枚・魔法1枚……3回
モンスター3枚・罠1枚……3回
モンスター1枚・魔法2枚・罠1枚……3回

例えば、罠カードをデッキに5枚入れて「バランス」で初期手札に1枚入れようとするデッキの場合、今回の調査結果によると16％の可能性で失敗すると推定されます。

Github

github.com

2017-11-09

【Python＆遊戯王デュエルリンクス】スクリーンショットから初期手札の「バランス」を自動取得するスクリプト

python デュエルリンクス

11月6日のアップデートで、スキル「バランス」に一定のランダム性が付与されたそうです。どの程度のランダム性が付与されたかを調べるため現在、モンスター10枚・魔法5枚・罠5枚デッキで「バランス」を使ってデュエルを始めた際の初期手札のスクリーンショットをひたすら取り続けています。

（オートで回している隙間時間を使って）その集計を簡略化するべく、スクリーンショットの画像から初期手札のモンスター・魔法・罠の割合を自動取得するプログラムを書きました。
github.com

手法

画像から、手札の1枚ずつの領域を取り出す
それぞれの領域内のRGB値の平均を導出し特徴量とする
全てのデータ（特徴量＋各ラベル）からKmeans法でモンスター・魔法・罠に分類する
集計して棒グラフを出力する

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import os
import cv2
from sklearn.cluster import KMeans
from collections import Counter
import matplotlib.pyplot as plt
import numpy as np

img_dirs = ['img']
CARD_NUM = 4
CLASS_NUM = 3
img_data = []

def convertImgToRGB(img):
    for card in range(CARD_NUM):
        trim_img = img[1180:1200,(80 + 113 * card):(193 + 113 * card)]
        averages = trim_img.mean(0).mean(0)
        img_data.append(averages)

def imgImport():
    for i, d in enumerate(img_dirs):
        files = os.listdir('./'+d)    
        for f in files:
            img = cv2.imread('./' + d + '/' + f)
            convertImgToRGB(img)

def createBarplot(counter):
    labels = []
    cnts = []
    for label, cnt in counter.most_common():
        labels.append(label)
        cnts.append(cnt)
    left = np.array([(i+1) for i in range(len(cnts))])
    height = np.array(cnts)
    plt.bar(left, height, tick_label=labels, align="center")

def converRGBToCollection(img_data):
    pred = KMeans(n_clusters = CLASS_NUM).fit_predict(img_data)
    pred.resize(int(len(pred)/CARD_NUM), CARD_NUM)
    pred = list(pred)
    for i in range(len(pred)):
        pred[i].sort()
        pred[i] = str(pred[i])
    counter = Counter(pred)
    createBarplot(counter)

imgImport()
converRGBToCollection(img_data)

画像処理のイメージ

github.com

Kmeans法の結果

f:id:upura:20171110090559p:plain

from mpl_toolkits.mplot3d import Axes3D
def plotRGBVectors(img_data):
    pred = KMeans(n_clusters = CLASS_NUM).fit_predict(img_data)
    x = []
    y = []
    z = []
    for i in range(len(pred)):
        x.append(img_data[i][0])
        y.append(img_data[i][1])
        z.append(img_data[i][2])
    fig = plt.figure()
    ax = Axes3D(fig)
    ax.set_xlabel("X-axis")
    ax.set_ylabel("Y-axis")
    ax.set_zlabel("Z-axis")
    ax.set_xlim(0, 256)
    ax.set_ylim(0, 256)
    ax.set_zlim(0, 256)
    ax.scatter(x, y, z, "o", c=pred)
    plt.show()

plotRGBVectors(img_data)

スクリーンショット募集

データ量が大事なので、同条件でのスクリーンショットを下記フォルダにアップロードいただけると大変ありがたいです。
https://drive.google.com/drive/folders/1N4kV_Mu0qq--IEJO0EwoLKBk4ygD_r3M?usp=sharing

追記：20171226

論文名

どんなもの？

先行研究と比べてどこがすごい？

技術や手法のキモはどこ？

どうやって有効だと検証した？

議論はある？

次に読むべき論文は？

概要

論文

追記20171115

ソフトウェア/データ

発表の動画

おわりに

経緯

解説

「256手ルール」の問題

ソフトの「独自性」の問題

運営による1の問題発生後の”独自性”確認

探索部「やねうら王」の開発者のツイート

憶測

所感

論文名

どんなもの？

先行研究と比べてどこがすごい？

技術や手法のキモはどこ？

どうやって有効だと検証した？

議論はある？

次に読むべき論文は？

使用デッキ

集計方法

集計結果

手法

画像処理のイメージ

Kmeans法の結果

スクリーンショット募集