2017年05月21日

 角交換振り飛車に大ポカ一発で沈む

昨日は毎年参加している将棋大会だった。
今年は2回戦敗退だったが、予選は1勝1敗で抽選で勝ち抜け(3人のブロックで3人とも1勝1敗だった)、抽選で決勝1回戦はシードだったので、昨年の1回戦敗退より悪い内容だった。通常3勝かかる所、たった1勝で2回戦まで進出するとは、何とくじ運の良かったことか。

筆者はここ1年くらい将棋の勉強をしておらず、全て忘れてしまっており、先月からたまにネット将棋を指していたが以前のレートでは全く勝てず、今年は予選突破できないと思った。
昔から記憶力が無い方であるが、たった1年休んだくらいで全て忘れてしまい、レートが200も下がるのでは、筆者は将棋に向いてないのだろうとつくづく思う。

2回戦の相手は昨年優勝のIさんだった。筆者が絶好調でもまず勝てない相手であるが、先手の筆者に次の局面のような感触の良い手が出た。

通常は4二の銀が4四に居るので、3四の歩を取っても響かないが、この形だと歩を取った後に3筋の歩を伸ばせる。3四の歩を受けるには△1二角と打つしかないが、形が悪いだろう。
筆者は通常、角交換振り飛車には▲6六歩のようにして角交換を拒否するのだが、1回戦で筆者が100回やっても勝てそうにないY田さんがIさんに対して▲6六歩と角交換を拒否して負けたのを見て、何か別の展開をガラケーの自作アプリに仕込んだ棋譜の中から1つ探して、その通りに指してみたものである。そういうことをすると通常は相手の研究にはまるので、ろくなことにならないのだが、今回は功を奏した。
対して、後手のIさんは△3二飛と指した。

これを見た瞬間、チャンスだと思った。2三の地点が空いている。
その誘惑に駆られた上、一手前に長考したこともあり、じっくり考えようとは思わなかった。
▲3四角に△4五桂と両取りに跳ねられても▲同角で両方受かる、と、それ以上考えずに、10秒も使わずに▲3四角と指したら、△2五桂とされて、一発で撃沈してしまった。

あと5秒考えていればこの手に気付いただろう。有段者が何の意味もなく、△3二飛のような隙を作る手を指すはずがない、と、何故一瞬でも思わなかったのか。
△2五桂の後、▲同歩、△3四飛、▲2四歩とすれば、後手は歩切れで、と金ができて大差にはならなさそうだが、この局面では丁度△1五角があって、受かってしまう。

△3二飛の局面は激指14のPro+3でも評価値が+280であり、少しリードしていたのは間違いない。その後、▲3四角ではなく、▲2九飛 △5四歩 ▲4八金と桂馬に紐を付け、△1二角 ▲6六歩 △6四歩 ▲1六歩のように進めれば、まあまあ指しやすそうである。

ここまでの手順は激指14のPro+以上の手を続けたものであり、評価値は+228である。

まあ、相手が相手なだけに、こう進んでもまず勝てなかっただろうが…


 MacPortsでmaximaをインストールするとエラーになるのを回避

現在、MacPortsを使って

sudo port install maxima
すると、下のようなエラーになって失敗してしまう。(macOS Sierra 10.12.4で確認)
../../doc/info//errormessages.texi:296: `Warning messages' has no Up field (perhaps incorrect sectioning?).
../../doc/info//errormessages.texi:162: Prev field of node `Operators of arguments must all be the same' not pointed to.
../../doc/info//errormessages.texi:152: This node (Only symbols can be bound) has the bad Next.
../../doc/info//errormessages.texi:152: Next field of node `Only symbols can be bound' not pointed to (perhaps incorrect sectioning?).
../../doc/info//errormessages.texi:204: This node (out of memory) has the bad Prev.
../../doc/info//errormessages.texi:8: `Error messages' has no Up field (perhaps incorrect sectioning?).
makeinfo: Removing output file `/opt/local/var/macports/build/_opt_local_var_macports_sources_rsync.macports.org_macports_release_tarballs_ports_math_maxima/maxima/work/maxima-5.39.0/doc/info/maxima.info' due to errors; use --force to preserve.
make[3]: *** [maxima.info] Error 1

原因は、makeinfoのバージョンが古いからのようだ。
http://maxima-discuss.narkive.com/KeLR9qhb/can-t-install-5-39
に、makeinfoのバージョンが4.xだとこうなることが書かれている。 実際、macOS Sierraで makeinfo --version すると、(GNU texinfo) 4.8と表示される。

そこで、

sudo port install texinfo
(GNU texinfo 6.3のmakeinfoがインストールされる)してから再度
sudo port install maxima
すると、上記のエラーは出なくなった。Activationの段階で
--->  Installing maxima @5.39.0_3+xmaxima
--->  Activating maxima @5.39.0_3+xmaxima
Error: Failed to activate maxima: Image error: /opt/local/bin/maxima already exists and does not belong to a registered port.  Unable to activate port maxima. Use 'port -f activate maxima' to force the activation.
というエラーになるが、メッセージの通り、
sudo port -f activate maxima
とすると、一応wxMaximaと併用しても問題なく動いた。

続きを読む "MacPortsでmaximaをインストールするとエラーになるのを回避"

2017年05月06日

 JediにAutoCompleよりCompanyModeを優先させる

2ヶ月前にCarbon EmacsのPython環境を整備したばかりなのだが、MacのOSを10.7.5から10.12.4にバージョンアップすると、Carbon Emacsがまともに動かなくなってしまった。起動はするのだが、すぐに固まってしまう。しかも、その後distnotedというプロセスが全てのCPUを奪い続けて、Macが激重になる。
この現象はOS X 10.9+Emacs 24.3で起こるらしく、Carbon Emacs(Emacs 22)でも起こったという情報は見つけられなかったが、おそらく同じ問題である。どちらかと言うとOSのバグなのだが、現時点ではEmacsを24.4以降にバージョンアップする以外に解決方法が見当たらない。

その為、長年お世話になったCarbon Emacsを手放し、Emacsの最新版である25.2を使うことにした。

EmacsWikiのPython Programming In EmacsのページにはPythonの開発環境を便利にする方法が色々書かれているが、筆者は高機能なPythonの開発環境を使いたい時はSpyderを使っており、EmacsのPython環境はPython.elでPython3が使えて、もう少し便利な補完が効けば十分なので、Jediだけを追加インストールすることにした。

Emacs 25.2にbuilt-inのPython.elはPython3に対応しているのだが、MacPortsでpython35をインストールして、M-x customize-group -> pythonして"Python Shell Interpreter"をpython3にすると、Warningが出まくり、妙に不安定だった。M-x list-packagesしてpython packageを0.25.2にバージョンアップすると少し改善したが、完全には直らなかった。
さらに、Jediをインストールすると、これまた不安定で、時々補完候補が出る前にEmacsが固まった。(C-gで抜けることはできる)

Emacs 24の最新版である24.5.1ではこの問題は起こらなかったので、当面、EmacsでPythonのコードを書く時は24.5.1を使うことにした。

Jediのインストールは、

(require 'package)
(add-to-list 'package-archives '("melpa" . "https://melpa.org/packages/"))
(package-initialize)
としてpackage.elにMELPAのリポジトリを登録し、M-x list-packagesしてjediをインストールし、Jedi.elのドキュメントに従ってセットアップした。

なお、Emacs25でjediをインストールすると、Emacs24で"Symbol's function is void: cl-struct-define"というエラーになった。これはjediに限らず、よくあることだそうで、Emacsの24と25を併用する場合、package.elで何かをインストールするならEmacs24でする方が良さそうだ。

さて、JediはAutoCompleteとCompanyModeの両方に対応しているが、package.elで"jedi"をインストールするとAutoCompleteが使われる。"company-jedi"をインストールするとCompanyModeが使われるのだが、"jedi"と"company-jedi"の両方をインストールすると、AutoCompleteが優先される。特にAutoCompleteに不満は無く、和製なので贔屓したいが、色々読んでいると、世界的には、日本でも現在は、CompanyModeの方が人気があるようなので、何が良いのかを知るために、これからしばらくはCompanyModeを積極的に使うべく、両方をインストールしてCompanyModeをデフォルトにすることに決めた。

しかし、.emacsや.emacs.d/init.elでCompanyModeを優先する適当な方法がわからなかった。Python modeにしてM-x auto-complete-modeとすればAutoCompleteのON/OFFが切り替わり、OFFだとCompanyModeが使われるのだが、Emacs Lispで(auto-complete-mode)としてもON/OFFが切り替わらず、auto-complete-mode関数にはOFFにする引数も無いのである。auto-complete-mode関数のソースコードを見ると、"(if auto-complete-mode ..."とあるので、

(setq auto-complete-mode nil)
(auto-complete-mode)
とすれば良さそうに思ったが、これでもOFFにならない。
但し、(setq auto-complete-mode nil)すると、即座にAutoCompleteがOFFになる。このことを使って、試行錯誤の末、.emacs等に
(add-hook 'python-mode-hook 'jedi:setup)
よりも前のどこかに
(add-hook 'python-mode-hook
(lambda () (setq auto-complete-mode nil)))
と書けば、Python mode開始時にAutoCompleteがOFFになり、CompanyModeが使われることがわかった。

続きを読む "JediにAutoCompleよりCompanyModeを優先させる"

2017年04月09日

 ROC曲線を理解する

2値の予測(判別、識別、…)に用いる特徴量の良し悪しを評価する1つの方法として、ROC曲線というものがある。
実際は正で予測も正であるデータの数をTP(True Positive)、
実際は負で予測も負であるデータの数をTN(True Negative)、
実際は負で予測は正であるデータの数をFP(False Positive)、
実際は正で予測は負であるデータの数をFN(False Negative)、
と呼ぶ時、
TPR(True Positive Ratio)=TP/(TP+FN)を縦軸、
FPR(False Positive Ratio)=FP/(FP+TN)を横軸、
としたグラフである。

ROC曲線の例
ROC curve sample

ROC曲線は、必ず(0,0)から始まって(1,1)で終わる。
特徴量が全く予測の役に立たない、ランダムな値であれば、TPR=FPRの線になる。
ROC曲線より下の面積、AUR(Area Under ROC curve)(または単にAUC(Area Under the Curve))が大きいほど、特徴量の値の全域に渡って良い特徴量だとされる。 理想的な特徴量だと、ROC曲線はFPR=0とTPR=1の線になる。

ROC曲線は機械学習で識別器の評価によく用いられるらしいので、とりあえず覚えておこうと思ったのだが、筆者はこれの理解にえらく苦労したので、調べたことや考えたことをメモする。
統計学の検定と同様、こういう確率と論理を組み合わせたものは、人によって向き不向きがあるのだと思いたい。

TP,TN,FP,FNの関係を再度整理すると、次のようになる。

予測

TPFN (Type II error)
FP (Type I error)TN
PやNは予測がPositiveかNegativeかであり、TやFはそれが正解かどうかである。
FPは誤検出のことであり、統計学の検定でも使われる「第一種の過誤」(検定では帰無仮説を棄却できないのに棄却する条件に誤ってヒットしてしまうこと)である。
FNは検出不能であり、「第二種の過誤」(検定では帰無仮説が誤りなのに棄却する条件にヒットしないこと)である。

予測の精度に関する尺度としては、Accuracy, Presicision, Recall, F値があり、それぞれ次のように定義される。
Accuracy = (TP+TN) / (TP+TN+FP+FN)
予測の正解率。
Precision = TP / (TP+FP)
Positiveと予測される中の正解率。
Recall = TP / (TP+FN)
実際にPositiveの内、Positiveと予測される割合。検出力、Sensitivity。
F値(F-measure, F1 score) = ((Precision-1 + Recall-1)/2)-1
PrecisionとRecallの調和平均。統計学のF分布に従うF値とは関係ない。
PrecisionとRecallはトレードオフの関係にあるので、それらをバランス良く合成した尺度。

予測の精度はAccuracyで評価するのが簡単だが、実際の正のデータ数と負のデータ数に偏りがあると、データ数が少ない方の正解率が低くても、データ数が多い方の正解率が高ければAccuracyが高くなってしまうので、Accuracyだけでは適切に評価できない。
そのような場合にPrecisionやRecallが用いられるが、これらは一般に特徴量の閾値によってトレードオフの関係があり、セットで評価しないといけないので、単純比較には向かない。そこで用いられるスカラー値が、F値や、ROC曲線のAUCである。
Precision-Recall曲線のAUCも使われることがあるが、Presicionは実際の正のデータの割合に依存するので、正のデータの割合が同じでないと比較には使えない。実際の正のデータの割合が極端に小さい場合など、Precisionが大きな意味を持つ場合にはPrecision-Recall曲線が用いられる。

ROC曲線は、TPR=TP/(TP+FN)とFPR=FP/(FP+TN)のグラフである。TPRを陽性率、FPRを偽陽性率と呼ぶこともある。TPRはRecallと同じである。FPRはfall-out(副産物)と呼ばれることもある。

次の図の3つのROC曲線が、正のデータと負のデータがどのように分布する特徴量に対応するかを考えてみる。
ROC curve sample 2

例えば、次のような分布になる特徴量だと、青いROC曲線になる。
distribution of totally independent feature
横軸は特徴量、縦軸は赤い部分が正のデータの分布、青い部分が負のデータの分布を表している。このグラフでは、正のデータも負のデータも一様分布している。閾値tより右ならPositive、左ならNegativeと予測する時、tを右端から左に動かすと、TPRもFPRも0から1に向かって増大するが、常にTPR=FPRである。正のデータと負のデータの割合はグラフの形状には関係しない。

次のような、正のデータと負のデータが完全に分かれる理想的な特徴量だと、緑のROC曲線になる。
distribution of ideal feature
tを右端から左に動かすと、FPR=0のままTPRが0から1に変化し、青のゾーンに入ると、FPRが0から1に変化する。

次のような分布だと、赤いROC曲線になる。
distribution of which makes ROC curve perfect arc
tを右端から左へ動かすと、FPRよりもTPRの方が早く上昇する。なるべく正のデータと負のデータの分布が分離している良い特徴量ほどFPRが上昇する前にTPRが上昇するので、AUCが大きくなることがわかる。

AUCはどれくらいだと良いか、という基準は一般的なものも色々あるようだが、大体、最低0.7は無いと有効ではないとされるようである。

なお、特徴量の最良の閾値(cut-off)はROC曲線の(0,1)に最も近い点とする、という方法を複数の箇所で目にしたが、明確な理論的根拠がある訳ではなく、必ずしもそれに限定されないようである。そもそも、(0,1)に最も近いというのがユークリッド距離で良いのかどうかがわからない。

続きを読む "ROC曲線を理解する"

2017年03月31日

 pandasでmergeせずにgroupbyで間接参照したい

この前、pandasを使っていて、次のような感じの、関連する2つのテーブル、access_logとchoice_logがある時に、結合したテーブルを作らずにchoice毎のtimestampの最小値を求めたかったのだが、どう書けば良いのかわからなかった。

import pandas as pd
import numpy as np
access_log = pd.DataFrame({'session': [100, 101, 102, 103, 104, 105, 106, 107, 108, 109],
                           'timestamp': [314, 159, 265, 358, 979, 323, 846, 264, 338, 327]})
choice_log = pd.DataFrame({'session': [100, 100, 101, 102, 102, 103, 104, 104, 105, 106, 106, 107, 108, 108, 109],
                           'choice':  ['A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E']})
>>> access_log
   session  timestamp
0      100        314
1      101        159
2      102        265
3      103        358
4      104        979
5      105        323
6      106        846
7      107        264
8      108        338
9      109        327
>>> choice_log
   choice  session
0       A      100
1       B      100
2       C      101
3       D      102
4       E      102
5       A      103
6       B      104
7       C      104
8       D      105
9       E      106
10      A      106
11      B      107
12      C      108
13      D      108
14      E      109
>>> 

結合テーブルを作るなら、次のように書ける。

merged = choice_log.merge(access_log, on='session', how='left')
result = merged.groupby('choice')['timestamp'].min()
>>> result
choice
A    314
B    264
C    159
D    265
E    265
Name: timestamp, dtype: int64
>>> 

実際にあったテーブルは巨大で、他にも列がたくさんあり、単純に結合テーブルを作るとRAMが足りなくなってメモリスワップが多発したので、結合テーブルを作らずにこれと同じことがしたかったのだが、その書き方がわからなかった。
結局access_log.set_index('session').to_dict()のようにして一時的なdictを作って、スワップを多発させながら処理してしまった。
それが心残りだったので、改めてpandasのドキュメントを拾い読みしながら方法を探してみた。

  1. 単純に、別のテーブルを参照する関数をSeries.mapに渡す
    def session_to_timestamp(session_series):
        return session_series.map(lambda x: access_log[access_log.session==x]['timestamp'].iat[0])
    
    result = choice_log.groupby('choice').agg(lambda x: session_to_timestamp(x).min())
    

    Seriesの先頭の要素を取り出す方法には、.iat[0]の他に.iloc[0]や.values[0]などがあり、筆者が試した所values[0]の方が速かったりしたが、pandasのドキュメントに書かれているのはilocとiatなので、ここでは添字が整数なら高速なiatを用いた。

  2. リスト内包表現(list comprehension)で別のテーブルを参照する
    def session_to_timestamp(session_series):
        return [access_log[access_log.session==x]['timestamp'].iat[0] for x in session_series]
    
    result = choice_log.groupby('choice').agg(lambda x: min(session_to_timestamp(x)))
    

    リストにはminメソッドが無いので、session_to_timestamp(x).min()とはできない。

  3. isinを使ったBoolean Indexingで別の表のサブセットを得る
    def session_to_timestamp(session_series):
        return access_log[access_log.session.isin(session_series.values)]['timestamp']
    
    result = choice_log.groupby('choice').agg(lambda x: session_to_timestamp(x).min())
    
  4. 別の表からSeriesを作ってSeries.mapに渡す
    def session_to_timestamp(session_series):
        return session_series.map(access_log.set_index('session').timestamp)
    
    result = choice_log.groupby('choice').agg(lambda x: session_to_timestamp(x).min())
    

    一見シンプルで美しそうだが、set_index()はコピーを返すので、timestampの一時的なdictを作るのと変わらない。しかも、グループ数だけ新たなテーブルを作るので、無駄である。

これらの処理時間を色々測ってみたが、2つのテーブルのサイズやグループの数によって変わり、どう比較すれば良いかわからなかったので、省略する。
大まかな傾向としては、1.と2.の処理時間はchoice_logのサイズに依存し、3.と4.の処理時間はsession_logのサイズに依存するようだった。4.はset_indexした中間テーブルを事前に作っておくと高速化するが、それでも、大抵の場合3.が一番速かった。
いずれの方法も最速になる場合があるようなので、場合毎に色々試してみるしかなさそうである。

肝心のメモリ使用量は、適当な測り方がわからなかった。
そもそも、スワップしながらの処理時間が問題だったので、単純にメモリ使用量では測れないと思う。

他にも、以下のような方向で書き方を考えてみたが、うまくできなかった。

  • groupbyでaggregateでなくtransformしてmin()
    transformする時に別のテーブルを参照することを考えたが、transformするとgroup解除されてしまうので、使えなかった。transformする時にmin()するのなら、min()した値を増殖させるだけ無駄なので、確実にaggregateの方が効率が良い。
  • pandas.DataFrame.lookupを使う
    引数としてindexしか受けられないので、使えなかった。
  • pandas.DataFrame.joinを使う
    pandas.DataFrame.mergeを使うのと変わらなかった。

そもそも、lambda式を使わずに書く方法は無いのだろうか。
teratailとかStack Overflowとかで聞いた方が早いか。

続きを読む "pandasでmergeせずにgroupbyで間接参照したい"