松尾研究室の「第3期 Data Science Online Course」を修了した

東京大学 松尾豊研究室の「第3期 Data Science Online Course」を修了した。
online course general | 東京大学グローバル消費インテリジェンス寄付講座
「グローバル消費インテリジェンス寄付講座」、Global Consumer Intelligenceを略してGCI講座と書かれることもある。……名称が結構色々ある。

いま改めてサイトを見たら

第3期は終了しました。
第3期以降、社会人向けオンラインコース開催の予定はありません。

って書いてありますね。今知ったけど、ラストチャンスだったのか。抽選で落ちた人もいたので(機械学習仲間の中では当選確率半分くらいだった)ラッキーだった。

コースの概要

Chapter 1~6はPythonの各種ライブラリ(Numpy・Pandas・Matplotlib)を使ったデータ処理の話。
Chapter 7~9がデータベース編となり、SQLとNoSQLを勉強した。
Chapter 10~13が機械学習の基本的な内容である。
1週間で1つの章を進める形式である。毎週課題が出されるので、次の週までに提出する必要がある。(未提出が多いと、講座を修了したと認められない。)
これに加えて、最終課題がある。分析するべきデータセットが渡されるので、自分なりに分析してWordもしくはPowerPointのレポートに結果をまとめて提出する。
最近(2019年3月)この講座の内容をまとめた本が出たので、詳しい内容については本を参照。

修了式の内容

4月3日に東京大学本郷キャンパスで修了式が開催された。

f:id:soratokimitonoaidani:20190519142754j:plain

ビュッフェ形式で食事が提供された(デザートの写真だけ撮ったので上げておく)。

f:id:soratokimitonoaidani:20190519142501j:plain

途中で優秀レポート発表の時間があった。選ばれた十数人が、最終課題の自分の解答を発表した。

松尾豊先生は式の最後に登場して、講評を述べた。

「ここにいる人はとても素晴らしい。 今の世の中ではAI、人工知能という単語が喧伝されている。しかし、実際に手を動かして勉強している人はとても少ないのが大きな問題である。 いまこの場にいる人たちは、その少ない勉強している人である。これからも学習を続けていってほしい」 というようなことを言っていた(大意)。

つい昨日の記事でも同様の発言をしている。「手を動かして勉強している人」がほとんどいない現状に、松尾先生は諦めの境地に達しているようだ……。

3カ月や半年でもきちんと勉強すれば、ディープラーニングを経営にも活用できるようになる。だから技術を研究している我々からすると、「早く勉強してほしい」という話に尽きる。これまでこうしたことを日本企業の経営者に何年も言い続けてきたが、何も起こらない。
(中略)
もはや、勉強もせず自ら動こうとしない企業の経営者に何を言ってもしょうがない。それよりも、やる気のある若い世代にチャンスを与えて、新しいことをやってちゃんともうけて会社を大きくしていけばいいのではないかと思う。やる気のある若い人にチャンスを与えたほうがましだ。
日本の社長にお手あげ:日経ビジネス電子版

今回の「第3期 Data Science Online Course」は、データサイエンスを一通り学習できた貴重な機会だった。 あれこれ目移りしてしまうタイプなので、講座に参加すると決まったペースで学習を進めることが出来て良かった。

pandasのSettingWithCopyWarningを理解する (3/3)

この記事は、 SettingwithCopyWarning: How to Fix This Warning in Pandas – Dataquest の日本語訳です。3回にわたって掲載していて、この記事は3回目です。

1回目の記事はこちら: linus-mk.hatenablog.com

2回目の記事はこちら: linus-mk.hatenablog.com

f:id:soratokimitonoaidani:20190518160502p:plain

連鎖代入を詳しく調べる

以前の例を再利用しよう。data内で、bidderの値が'parakeet2004'である各行のbidderrate列を更新しようとしていたのであった。

data[data.bidder == 'parakeet2004']['bidderrate'] = 100
/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/ipykernel/__main__.py:1: SettingWithCopyWarning: A value is trying to be set on a copy of a slice from a DataFrame.Try using .loc[row_indexer,col_indexer] = value insteadSee the caveats in the documentation: http://pandas.pydata.org/pandas-docs/stable/indexing.html#indexing-view-versus-copy if __name__ == '__main__':

このSettingWithCopyWarningによってpandasが本当に伝えていることは、コードの動作があいまいだということである。しかし、なぜあいまいなのかを理解し、また警告の文言を理解するためには、いくつかの概念について説明したほうがよいだろう。

私たちは以前、ビューとコピーについて簡単に述べた(訳注:1回目の記事を参照)。DataFrameサブセットにアクセスするための可能な方法は2つある。メモリ内の元のデータへの参照を作成する(ビュー)か、サブセットを新しい小さなDataFrameにコピーする(コピー)ことである。 ビューは元のデータの特定の部分を見る方法だが、一方でコピーはそのデータの複製物であり、メモリ内の新しい場所にある。前の図で示したように、ビューを変更すると元の変数は変更されるが、コピーを変更しても元の変数は変更されない。

理由は後述するが、pandasでの 'get'操作の出力は保証されていない。pandasのデータ構造にインデックス操作を行うと、ビューまたはコピーのいずれも返される可能性がある。つまり、DataFrameに対するget操作は、新たなDataFrameを返すが、その中身は以下のどちらかだ。

  • 元のオブジェクトからのデータのコピー。
  • 元のオブジェクトのデータに対する参照(コピーを作成しない)。

どちらが起こるのかは分からないし、それぞれの場合の振る舞いは全く異なるので、警告を無視することは危険な行為である。

ビュー、コピー、そしてこのあいまいさをより明確に説明するために、単純なDataFrameを作成してインデックスを付けてみよう。

df1 = pd.DataFrame(np.arange(6).reshape((3,2)), columns=list('AB'))
df1
- a b
0 0 1
1 2 3
2 4 5

そして、 df1のサブセットをdf2に代入しよう。

df2 = df1.loc[:1]
df2
- a b
0 0 1
1 2 3

これまで学んできたことを考えると、df2はdf1のビューかもしれないし、またはdf1のサブセットのコピーかもしれない、ということが分かる。

問題を理解する前に、連鎖インデックスをもう一度見てみる必要がある。'parakeet2004'を使った例を詳しく説明すると、2つのインデックス操作を連鎖させたのであった。

data[data.bidder == 'parakeet2004']
__intermediate__['bidderrate'] = 100

ここで__intermediate__は最初の呼び出しの出力を表し(訳注:実際に__intermediate__というメソッドや変数があるわけではない)、私たちからは完全に隠れている。思い出してほしいのだが、属性アクセスを使用した場合も問題のある同じ結果になってしまった:

data[data.bidder == 'parakeet2004'].bidderrate = 100

同じことが他の形式の連鎖呼び出しにも当てはまる。それは、この中間オブジェクトを生成しているからである。

内部的には、連鎖インデックスとは、単一の操作を実行するために__getitem__または__setitem__を複数回呼び出すことを意味する。これらは特別なPythonメソッドであり、これらのメソッドを実装するクラスのインスタンスに対して角括弧を使用することで呼び出される。これは、シンタックスシュガー(糖衣構文)と呼ばれるものの例である。この例でPythonインタプリタが実行する内容を見てみよう。

# Our code
data[data.bidder == 'parakeet2004']['bidderrate'] = 100

# Code executed
data.__getitem__(data.__getitem__('bidder') == 'parakeet2004').__setitem__('bidderrate', 100)

すでにお気づきかもしれないが、SettingWithCopyWarningは、この連鎖された__setitem__呼び出しの結果として生成される。あなたは自分でこれを試すことも可能だ――上記の2行は全く同じように機能する。理解する上で注意してほしいのだが、2番目の__getitem__呼び出し(bidderの列を呼ぶ箇所)は入れ子になっており、ここでの連鎖の問題の一部ではない。

一般に、既に述べたように、pandasはget操作がデータのビューとコピーのどちらを返すのかを保証していない。この例でビューが返された場合、連鎖代入の2番目の式では、元のオブジェクトに対して__setitem__を呼び出すだろう。しかし、コピーが返された場合、代わりに変更されるのはコピーである。元のオブジェクトは変更されない。

A value is trying to be set on a copy of a slice from a DataFrame. (DataFrameからのスライスのコピーに値が設定されようとしている)」という文言によって警告が言わんとしているのは、まさにこのことである。このコピーはどこからも参照されていないので、それは最終的にガベージコレクションの対象となる。SettingWithCopyWarningは以下のことを伝えている:最初の__getitem__呼び出しでビューとコピーのどちらが返されたのかを、pandasは判断できない、したがって、代入によって元のオブジェクトが変更されたかどうかは不明である。 pandasがこの警告を発生させる理由について考えるもう一つの方法は、「私たちは元のオブジェクトを変更しているのか?」という質問の答えが不明だからである。

そして私たちは元のオブジェクトを変更したい。この警告が提案する解決策は、これら2つの別々の連鎖操作を、locを使用して単一の代入操作に変換することである。これにより、コードから連鎖インデックスが削除され、警告が表示されなくなる。修正後のコードとそれを展開したものは、このようになる。

# Our code
data.loc[data.bidder == 'parakeet2004', 'bidderrate'] = 100
# Code executed
data.loc.__setitem__((data.__getitem__('bidder') == 'parakeet2004', 'bidderrate'), 100)

DataFrameのlocプロパティは、元のDataFrameであることが保証されているが、より多くのインデックス機能を備えている。

偽陰性

(訳注:ここでの「偽陰性」は「実際には問題が起きているのに、警告が発生しないこと」を指す)

locを使用しても問題が解決するわけではない。locを用いたget操作の場合、依然としてビューとコピーのどちらが返る可能性もあるからだ。やや複雑な例を見てみよう。

data.loc[data.bidder == 'parakeet2004', ('bidderrate', 'bid')]
- bidderrate bid
6 100 3.00
7 100 10.00
8 100 24.99

今回は、1列ではなく2列を取り出した。 全てのbidの値を設定してみよう。

data.loc[data.bidder == 'parakeet2004', ('bidderrate', 'bid')]['bid'] = 5.0
data.loc[data.bidder == 'parakeet2004', ('bidderrate', 'bid')]
- bidderrate bid
6 100 3.00
7 100 10.00
8 100 24.99

変更もされていないし、警告も発生していない!スライスのコピーに値を設定したが、pandasによって検出されなかった。これは偽陰性である(訳注:実際には問題が発生しているのに警告が発生しない状況)。locを使ったからといって、連鎖代入を使ってよいわけではない。この特定のバグに関する古い未解決のissueGitHubに存在する。

これを行う正しい方法は次のようになる。

data.loc[data.bidder == 'parakeet2004', 'bid'] = 5.0
data.loc[data.bidder == 'parakeet2004', ('bidderrate', 'bid')]
- bidderrate bid
6 100 5.0
7 100 5.0
8 100 5.0

実際の場面でこんな問題にはまってしまうことなんてあり得るのだろうか、と思うかもしれない。しかし、思っているよりも問題に陥りやすいのが、DataFrameのクエリの結果を変数に代入するときである。次の節で説明する。

隠れた連鎖

先ほどの隠れた連鎖の例をもう一度見てみよう。そこでは、変数winnersを作り、その中の304というラベルの行に対して、bidderの値を設定しようとしていた。

winners = data.loc[data.bid == data.price]
winners.loc[304, 'bidder'] = 'therealname'
/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/pandas/core/indexing.py:517: SettingWithCopyWarning: A value is trying to be set on a copy of a slice from a DataFrame.Try using .loc[row_indexer,col_indexer] = value insteadSee the caveats in the documentation: http://pandas.pydata.org/pandas-docs/stable/indexing.html#indexing-view-versus-copy self.obj[item] = s

locを使用しても、SettingWithCopyWarningが出力される。この問題は非常に分かりづらいかもしれない。なぜなら、警告メッセージが提案していることを、私たちがすでに実行したようにみえるからだ。

しかし、変数winnersについて考えてみよう。本当のところ、これは何なのだろうか? 変数winnersをdata.loc[data.bid == data.price]でインスタンス化したしたことを考慮すると、変数winnersが元のDataFrameのビューとコピーのどちらかなのかは分からないのだ(get操作はビューかコピーのどちらかを返すので)。インスタンス化の行と、警告が出てきた行とを組み合わせると、私たちの間違いがはっきりする。

data.loc[data.bid == data.price].loc[304, 'bidder'] = 'therealname'
/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/pandas/core/indexing.py:517: SettingWithCopyWarning: A value is trying to be set on a copy of a slice from a DataFrame.Try using .loc[row_indexer,col_indexer] = value insteadSee the caveats in the documentation: http://pandas.pydata.org/pandas-docs/stable/indexing.html#indexing-view-versus-copy self.obj[item] = s

この場合も連鎖代入を使っていたのだが、今回は2行に分かれていたというわけだ。これについて考える別の方法は、「このコードは1つのものを修正するか、それとも2つのものか?」という質問をすることである。今回の場合、答えは不明である。もしwinnersがコピーであればwinnersだけが影響を受けるが、winnersがビューであればwinnersとdataの両方が更新された値を表示することになる。この状況は、スクリプトソースコード内で非常に離れている行の間で発生する可能性があり、問題の原因を突き止めるのが非常に困難になるおそれがある。

ここでの警告が意図していることは、私たちが思い違いをするのを防ぐことである すなわち、元のDataFrameをコードは実際には変更しないのに変更すると思うことや、元のDataFrameではなくてコピーを変更しているのだと思ってしまうことである。pandasのGitHubリポジトリ上の古いissueをよく調べると、開発者自身がこの問題を説明しているのを読むことができる。

問題をどのように解決するかは、私たち自身がどうしたいかによって異なる。元のデータのコピーを使って作業したい場合は、pandasにコピーを作成するように強制すれば解決である。

winners = data.loc[data.bid == data.price].copy()
winners.loc[304, 'bidder'] = 'therealname'
print(data.loc[304, 'bidder']) # Original
print(winners.loc[304, 'bidder']) # Copy
nan
therealname

一方で、元のDataFrameを更新する必要がある場合は、元のDataFrameを使用せねばならない。不確定な動作によって他の変数をインスタンス化するのは避けるべきだ。以前のコードは次のようにすればよいだろう。

# Finding the winners
winner_mask = data.bid == data.price
# Taking a peek
data.loc[winner_mask].head()
# Doing analysis
mean_win_time = data.loc[winner_mask, 'bidtime'].mean()
... # 20 lines of code
mode_open_bid = data.loc[winner_mask, 'openbid'].mode()
# Updating the username
data.loc[304, 'bidder'] = 'therealname'

DataFrameのサブセットのサブセットを変更するような、より複雑な状況においては、連鎖インデックスを使用する代わりに、元のDataFrame上でlocを使って作成しているスライスを変更できる。たとえば、上で書いた新しい変数winner_maskを変更したり、winnersのサブセットを選択した新しい変数を作成したりできる。以下のように:

- auctionid bid bidtime bidder bidderrate openbid price bidtime_hours
225 8213387444 152.0 2.919757 uconnbabydoll1975 15 0.99 152.0 70.074168
328 8213935134 207.5 2.983542 toby2492 0 0.10 207.5 71.605008
416 8214430396 199.0 2.990463 volpendesta 4 9.99 199.0 71.771112
531 8215582227 152.5 2.999664 ultimatum_man 2 60.00 152.5 71.991936

この手法は、将来の開発コードのメンテナンスとスケーリングに対してより堅牢である。

歴史

読者の皆さんは疑問に思っているかもしれない。 このSettingWithCopy問題の全部が、簡単にすっかり回避できないのはどうしてだろうか? ここまで長々見てきたような分かりにくい状況を作り出すのをやめて、ビューならビューだけを、コピーならコピーだけを常に返すインデックスメソッドを明示的に規定してやればいいのではないか? この点を理解するためには、pandasの過去を調べる必要がある。

ビューを返すのかコピーを返すのかを決定するためにpandasが用いているロジックは、pandasの操作の根底にあるNumPyライブラリの使用に由来している。実のところ、ビューはNumPyを介してpandasの言語仕様に入った。実際、NumPyではビューが期待通りに返ってくるので便利である。NumPy配列はsingle-dtypedなので、pandasは最も適切なdtypeを使って、メモリ空間と処理に要する時間を最小にしようとする。その結果、単一のdtypeを含むDataFrameのスライスを、単一のNumPy配列のビューとして返すことができる。この方式のおかげで、操作を処理するのは非常に効率的になった。しかしながら、multi-dtypeスライスをNumPyに同じように効率よく格納することはできない。pandasは、汎用的に使えるインデックス機能を組み合わせて、NumPyコアを最も効果的に使用できるようにした。

結局のところ、pandasのインデックスの設計は便利で汎用的に使えるが、設計方法は根底にあるNumPy配列の機能と厳密には一致してるわけではない。 これらの設計要素と機能要素が長い時間をかけて相互に作用した。その結果出来上がったのが、ビューとコピーのどちらを返せばよいかを決定する一連の複雑な規則である。熟練したpandasエンジニアは、pandasの動作には通常満足している。インデックス操作の挙動を自分の思い通りにするのに苦労しないからである。

get操作はインデックス可能なpandasオブジェクトを返すが、だからといって連鎖インデックスは意図したとおりの方法ではない。しかし、ライブラリを初めて使用する人にとっては残念なことに、連鎖インデックスを使ってしまうのはほとんど避けられない。さらに、ここ数年のpandasのコアデベロッパーの一人であるJeff Rebackが言うには、「言語の観点から連鎖インデックスを直接検出することは不可能である。それを推測せねばならない」。

その結果、この警告は2013年の終わりごろにバージョン0.13.0で導入された。多くの開発者が遭遇した、「連鎖代入が警告やエラーもないのに失敗する事象」に対する解決策として導入された。

バージョン0.12より前では、 ixインデクサが最も普及していた(pandasの命名法では、ix, loc, ilocのような「インデクサ」は、その後に角括弧をつけるとオブジェクトをインデックスできる構造にすぎない。 これは配列と同様であるが、しかし動作は特別なものである)。 しかし、2013年半ばのこの頃には、pandasプロジェクトは勢力を伸ばしはじめて、初心者ユーザー向けにすることがますます重要になっていた。このリリース以降、locおよびilocインデクサは、その性質が明示的であり使用方法が解釈しやすいことから、結果的に好まれている。(訳注:ixインデクサは非推奨(deprecated)となった

SettingWithCopyWarningは、導入後も進化を続け、数年間にわたりGitHubの多くのissueで盛んに議論され、さらに更新されている。しかしこの警告はpandasに定着しているため、pandasの専門家になるためには理解することが依然として必要不可欠である。

まとめ

SettingWithCopyWarningの根底にある複雑さは、pandasライブラリの数少ない小さな欠点の1つである。その起源はライブラリに非常に深く組み込まれており、無視してはならない。 Jeff Reback自身の言葉では、「私の知る限り、実際にはこの警告を無視すべきであるという場合はありません。……特定の種類のインデックス操作をして上手くいかないこともあるし、他の種類のインデックス操作で上手くいくこともあるでしょう。危険極まりない行為です。」

幸運なことに、警告に対処するには、連鎖代入を特定して修正するだけで済む。この記事全体の中で、このことだけは覚えていってほしい。


これにて翻訳完了である。

2回目の記事を書き上げた後、3回目の翻訳を仕上げることを半ば忘れていた。ところが、2週間ほど前にこのシリーズに対して言及があったのである。

DataFrameの値を書き換えるときにSettingWithCopyWarningが出る - 日々精進

驚いた。なにせpandasの特定の警告に関する記事なので、いささかマニアックというか、それほど需要は多くないはずだ。この記事に対するリアクションを見たのは初めてであった。
感謝の言葉に気を良くした俺は翻訳を再開したというわけだ(チョロい)。

英語の記事(ドキュメント)の翻訳は楽しいし勉強になるが、なかなか大変なのも事実だ。今後はまたいい記事があったら翻訳していこう。
それでは。

【未解決】Pythonの関数とグローバル変数とローカル変数の話

最近は競技プログラミングに対する熱がだいぶ高まっている。

以前にやって解けなかったこの問題を、少し前に解き直していた。
C - 広告
そうしたら思わぬ挙動にハマったのでメモしておく。

問題のコード

元々書いていたコードは前述の問題を解くためのものだが、この記事に載せるにあたって該当部分だけを抜き出して適宜変更した。したがって、元の問題とは殆ど無関係なものになっている。

def lower_func(v):
    w = match[v]
    if(w < 0):
        match[v] = v+1
        print("lower_func:" , match)
    return True

def higher_func():
    match = [-1] * V
    for v in range(V):
        lower_func(v)
        print("higher_func:", match)
    return 

V = 3
match = [-1] * V

higher_func()
print("global:", match) 

グローバル部分でmatchというリストを定義し、higher_func()を呼ぶ。
higher_func()の中では、matchを同じ値でもう一度初期化しておいてから、lower_func()を呼ぶ。
lower_func()の中で順次値を書き換える。

#出力
lower_func: [1, -1, -1]
higher_func: [-1, -1, -1]
lower_func: [1, 2, -1]
higher_func: [-1, -1, -1]
lower_func: [1, 2, 3]
higher_func: [-1, -1, -1]
global: [1, 2, 3]

……あれれ。
globalとlower_funcの中は書き換わっているのに、higher_funcの中のmatchは書き換わっていない!
どうなってるの。

idを見てみよう

こういう問題(同じ名前の変数がどのオブジェクトを指しているのか分かりにくい問題)の場合、idを見ると分かりやすいだろう。

def lower_func(v):
    w = match[v]
    if(w < 0):
        match[v] = v+1
        print("lower_func:", match)
        print("lower_func:", id(match))
    return True

def higher_func():
    match = [-1] * V
    for v in range(V):
        lower_func(v)
        print("higher_func:", match)
        print("higher_func:", id(match))
    return 

V = 3
match = [-1] * V

higher_func()
print("global:", match)
print("global:", id(match))

# 出力(注意:idは実行するごとに異なる値となる)
lower_func: [1, -1, -1]
lower_func: 33907336
higher_func: [-1, -1, -1]
higher_func: 39538248
(中略)
global: [1, 2, 3]
global: 33907336

複数回呼び出されるので複数回idがprintされるわけだが、全部書いても意味がないので略した。

なるほど、lower_func()とグローバル領域のmatchは同じオブジェクトを指している。つまり、グローバル変数だ。
そして、higher_func()のmatchは関数内のローカル変数だ。
lower_func()はグローバル変数を書き換えているが、higher_func()内で出力しているのは別の変数の値なので、出力された値は変わらない。

一件落着……したようだが、まだ疑問がある。

疑問その1

pythonの公式ドキュメントより引用。

関数内で変数への代入を行うと、その値はすべてこのローカルなシンボルテーブルに記憶されます。一方、変数の参照を行うと、まずローカルなシンボルテーブルが検索され、次にさらに外側の関数のローカルなシンボルテーブルを検索し、その後グローバルなシンボルテーブルを調べ、最後に組み込みの名前テーブルを調べます。
4. その他の制御フローツール — Python 3.7.3 ドキュメント

lower_func()では w = match[v]で、変数の参照を行っている。 「ローカルなシンボルテーブルが検索され、次にさらに外側の関数のローカルなシンボルテーブルを検索し……」とチュートリアルには書いてある。
つまり、最初にlower_func()の中を検索する。そこにmatchという変数は定義されていない。
したがって、次に呼び出し元であるhigher_func()を検索する。そこにmatchという変数は定義されて……いるじゃん。
あれ? チュートリアルのドキュメントの通りなら、lower_func()の中でmatchを参照したらhigher_func()の中のmatchになるんじゃないの?

疑問その2

公式ドキュメントの、先ほどの箇所にはこうも書いてある。「関数内で変数への代入を行うと、その値はすべてこのローカルなシンボルテーブルに記憶されます。」

match[v] = v+1の部分で代入を行っている。そしたらmatchはローカルになるんじゃないの?

従って、関数の中では、グローバルな変数を参照することはできますが、直接値を代入することは (global 文で名前を挙げておかない限り)できません。
4. その他の制御フローツール — Python 3.7.3 ドキュメント

同じことを別の言い方をすると、なんで関数内でグローバル変数に値を代入できているの?
この記事を見ていると、関数内でグローバル変数に値を代入するとエラーが発生するようだけど。
Pythonの変数スコープの話 - Qiita

(多分、疑問1・2とも、変数matchそのものではなくmatchの要素に対して参照・代入を実行しているところがミソな予感がする。が、これ以上は調べてもよくわからないので撤退する)

疑問は措いておいてひとまず解決するなら

global文を使えば、その変数がグローバル領域のものであることを明示できる。
関数を定義した直後にglobal matchと書いて、matchがグローバル変数であることを書けば良い。

def lower_func(v):
    global match #追加
    w = match[v]
    if(w < 0):
        match[v] = v+1
        print("lower_func:", match)
        print("lower_func:", id(match))
    return True

def higher_func():
    global match #追加
    match = [-1] * V
    for v in range(V):
        lower_func(v)
        print("higher_func:", match)
        print("higher_func:", id(match))
    return 

V = 3
match = [-1] * V

higher_func()
print("global:", match)
print("global:", id(match))

# 出力(注意:idは実行するごとに異なる値となる)
lower_func: [1, -1, -1]
lower_func: 39406536
higher_func: [1, -1, -1]
higher_func: 39406536
lower_func: [1, 2, -1]
lower_func: 39406536
higher_func: [1, 2, -1]
higher_func: 39406536
lower_func: [1, 2, 3]
lower_func: 39406536
higher_func: [1, 2, 3]
higher_func: 39406536
global: [1, 2, 3]
global: 39406536

global() / higher_func() / lower_func() のidが全て同一であり、どこから表示しても値が書き換わっていることが分かる。

Python ビットシフトと加減算の演算子の優先順位

気づいてしまえば何ということもない話だったが、解決までに結構時間を食ってしまったので、忘れないようにメモしておく。

Python演算子で、ビットシフト演算子は加算・減算演算子よりも優先順位が低い。

演算子の優先順位の一覧は、公式ドキュメントの以下のセクションにあるので参照のこと。
6. 式 (expression) — Python 3.7.3 ドキュメント


以下、具体例。

下の例で、aを8ビットシフトした数値と、bを4ビットシフトした数値の和を求めたいとする。(この記事を通して、シフト方向は左とする)
手計算では、答えは3 * 256 + 5 * 16 = 768 + 80 = 848 となる。

a = 3
b = 5
x1 = a << 8 + b << 4
print("x1={}".format(x1))

x2 = (a << 8) + (b << 4)
print("x2={}".format(x2))

x3 = a * 2 ** 8 + b * 2 ** 4
print("x3={}".format(x3))


出力:
x1=393216  # 期待と違う!
x2=848
x3=848

x1 がおかしな値になった理由は、加算演算子のほうがビットシフト演算子よりも優先順位が高いせいである。x1の式の計算順序は次のようになる。

  • まず、8 + bが先に計算される。 8+5=13
  • a << 13 << 4の2つの演算子の優先順位は同じなので、左から先に計算される。 3 << 13 = 24576
  • 24576 << 4演算子はただ一つしかないので、それが計算される。24576 << 4 = 393216

2番めで左から先に計算される根拠は、公式ドキュメントの先ほどと同じ箇所にある以下の記述である。
6. 式 (expression) — Python 3.7.3 ドキュメント

同じボックス内の演算子は、左から右へとグループ化されます (例外として、べき乗は右から左にグループ化されます)。

「aを8ビットシフトした数値と、bを4ビットシフトした数値の和」を求めたい場合は、x2のようにカッコを付ける必要がある。

また、x3のように書いてもよい(計算速度については考慮していない)。乗算演算子よりもべき乗演算子のほうが優先度が高い。したがって、a * 2 ** 8は期待通りにべき乗が先に計算される。

初めてのAtCoderコンテスト中600点正解を目前で逃した話

先週末の天下一プログラマーコンテストのこと。

最初の問題を首尾よく片付けた俺は、2問目に取り掛かっていた。 しかし、600点問題を試験時間内に解いたことは無い。500点でも解けない確率の方が多いので、解けないものと半ば諦めつつ問題文を読んだ。

atcoder.jp

ナップサック問題っぽい。 これは「赤の辺の長さがxのもの」だったら単純なナップサック問題で、動的計画法を使えば解ける。 ……あれ?これは「赤の辺の長さが全体の半分以上のもの」の3倍が三角形を作れない場合の数だから、全体から引けば答えが出るのでは?そして「赤の辺の長さが全体の半分以上のもの」は上と同様の動的計画法で求められるのでは? ……もしかしてこの問題、解けるんじゃないか?

上記で基本方針は正しいが、実はこれだけだとダブルカウントが発生して間違いになる。しかし解いている途中で間違いにも気づき、2つ目のDPテーブルを作れば解決できることを導き出した。

サンプル入出力も無事に通って、満を持して提出! TLE。Pythonのような遅い言語にはあり得ることだ。 WAは出ていないので、解法は完璧だと思うが、いかんせん計算に時間がかかりすぎている。 その後デバッグを続けてもTLEを脱出できず、時間切れとなった。

やはりPythonで正答を提出するのは不可能なのだろうか。C++とかじゃないと無理なのだろうか。

みんなの回答を見ようとして、言語の一覧を見ていたところ、PyPyを見つけた。 PyPy。確か、Pythonの一般的な処理系よりも処理が高速だ、と聞いたことがある。

試しに最後の回答をPyPyで再提出してみた俺は、脱力した。

すなわちPyPyで提出していれば600点問題がAC(accepted、正答)だったのだ!

この方法に気づかずコードの修正をしていたせいで、 初めての600点ACを逃してしまった。

ひとまず、解法が合っているはずなのにTLEで落ちる場合は、処理系をPyPyに切り替えてもう一度試してみよう。

それでは。

技術書典6 買ったものまとめ

2019年4月14日(日) 池袋サンシャインで開催された技術書典5に一般参加してきた。
半年前の技術書典5は「うーん、買ってもどうせ読まないんだよなぁ」と思って不参加だった。今回はちょっと気になる本もあったので、半ば何となく参加。
11:15頃に待機列に並び、12:00頃に入場。会場はコミケに買いに行ったときのような凄い混雑で、酷いときは身動きが取れないほどだった。
あれだけの熱気を目にすると「次はサークル側で参加して本を書いてみようかな……?」と思うが、その3秒後には「いや、でも俺が書けるようなことなんてないぞ……」と思ってしまうのであった。


というわけで、買った本。ザッと見てみた内容を書いています(本格的に読むのはこれからです)。boothなどの通販がある場合は併記しています。

f:id:soratokimitonoaidani:20190416232312j:plain コーディング関係の本から行きます。

におうコードの問題集 〜ソフトウェア設計に立ち向かう編〜

シリーズ3冊目。ちなみに1冊目が「〜バリエーションに立ち向かう編〜」、2冊目が「〜セキュリティホールに立ち向かう編〜」である。
俺は普段、大きな製品のごく一部分を変更する作業ばかりしているので、ソフトウェアの設計らしい設計をほどんどやらない。
たまに試験用の内部向けツールを作ると、「は? これクラスの設計に大失敗したな?」という惨事がよく起きる。
そういうのを上手く作れるようになりたいと思って買った。なお、扱っている言語はシリーズで一貫してCrystalである。珍しい。(1500円)

技術書典6で「におうコードの問題集〜ソフトウェア設計に立ち向かう編〜」を頒布します - 圧倒亭グランパのブログ
【PDF】におうコードの問題集 〜ソフトウェア設計に立ち向かう編〜 - Grand Pa-Ma - BOOTH

機械学習の炊いたん。

前回の秒速DEEP LEARNING本が高く評価されているのを見かけることが多かった(例えば 手を動かしながら学べるディープラーニングの優良なチュートリアル - karaage. [からあげ])。
俺は買おうかなと思ったが結局買いそびれてしまった。聞いてみたら、なんと5月に商業の本として編集・出版されるらしい。
秒速DEEP LEARNINGに続くこの本は、5人が分担して書いた本である。機械学習の転職事情の話を目当てに買ったけど、他には学習用環境の話とか強化学習の話とかがある。(1500円)

[新刊] 機械学習の炊いたん。 - tomo-makes - BOOTH

機械学習API作成入門 ―scikit-learnとdjango-rest-frameworkでサクッと開発―

Djangoは全くやったことないけど、立ち読みしてみたらかなり簡潔な内容だったので、これなら俺でもできるんじゃないかと思いつつ購入。(500円)


f:id:soratokimitonoaidani:20190416232316j:plain 続いて、コーディング要素の少ない本。

個人開発がやりたくなる本 ~クリエイター13人の実録エッセイ~

技術書典に行く主目的は多分この本だったなぁ。鮮やかな黄色の表紙がひときわ目を引く。いい色ですね。
競技プログラミングみたいに「向こうから解くべき課題がやってくる」タイプの開発は好きだと思う。一方で、個人開発……アプリ作ったりサービス作ったりするのは殆どしたことがない。俺はそういう性格なのかなぁとも思うが、その手の開発をしてる人を凄いなぁと思うのもまた確かだ。個人開発で何か作ってみたいなぁと思いつつ購入。(1500円)

【電子版】個人開発がやりたくなる本 - クリエイター13人の実録エッセイ - #IndieCoderJP - BOOTH

はじめる技術 つづける技術

パラパラ見た感じだと、何かを始めるとき・続けるときに起こりがちな問題点とその対策をまとめた本かな。
著者や周囲の具体的な事例を織り交ぜながら語っている。(500円)

技術書典6の新刊「はじめる技術 つづける技術」 - 青空な日々
はじめる技術 つづける技術 - fortegp05 - BOOTH

継続的にアウトプットする技術

上とかなり似たようなテーマの本(なおスペースはぜんぜん違う場所だった)。
会場につくまで本の存在を知らなかった。俺が見つけて立ち読みしたときに買う決め手になったのは、参考文献の存在である。巻末には15冊の参考文献が掲載されている。このような題材だと「俺はこう思う」で個人的な主観を書けてしまう中で、なるべく再現性のあることを書こうとしてるのは好感が持てる。(1000円)

継続的にアウトプットする技術――エンジニアのための「続けられる」科学 - yagitch.com - BOOTH

OneStop転職

そりゃ買うよね。

ワンストップ勉強会も買おうかと思ったが、実物を見ると厚みと重量が半端なかったので回避(電子版で購入予定)。

俺「OneStop転職を1冊お願いします」
売り子のお姉さん「ありがとうございます。こちら無料配布の冊子2冊です。」
俺「( ゚д゚)ポカーン ……おまけの方が量が多くないですか?」
お姉さん「気のせいです!」
俺「気のせいですか……?」
今見たけどやっぱりおまけの方が多いですね……一体どういうことなんだ……w
(1500円)

OneStop転職 - alchemists - BOOTH

今思い出したけど、この本はサークル側の方針により電子書籍で発売しない、とどこかで見かけました。物理本で買いましょう。

エンジニアアンチパターン

write-blog-every-weekのslackで一緒の このすみさん に挨拶に行った際に購入。技術書典5で出した既刊本です。
プログラミング・データベース・プロジェクト管理からUI/UXまで、色々な分野で筆者が犯した失敗から教訓を得る本。他の人の失敗から学ぶのだ……!
まえがき・あとがきには「失敗の本質」をきっかけにこの本を書いた旨が書いてある。「失敗の本質」は大変な名著ですね、大好きです。(800円)

エンジニアアンチパターン: 〜失敗に学ぶエンジニアリング〜 Kindle版

技術書典5向け新刊「エンジニアアンチパターン 〜失敗に学ぶエンジニアリング〜」のご紹介と制作秘話 - このすみろぐ


番外編:当日買っていないもの。

pythonチートシート

pandas, matplotlib, データ前処理のチートセット。

Data Analysis Cheat Sheet - data-analysis-cs - BOOTH

songle API

最初に周ってるときに、Songle APIの本を見つけてビックリした。 俺はこの間、Songleで分析した結果のLTをやっていた。メジャーな技術でもないのに、まさかSongleを題材にした本があるとは。

マッシュアップ曲を聞いてビックリしたので、音楽のコードを分析してみた / Examined the Similarity of Two Tunes by Analyzing their Chords - Speaker Deck

一通り目当てのものを買ったあとで買おうと思って、後で立ち寄ったが、そのときにはすでに売り切れていた……


計算してみると、当日会場で支払ったのは10000円弱だということが分かった。一人1万円×参加者1万人として、1億円が動くと思うとすごくないですか。
あとは、せっかく買ってきた本が積ん読にならないように、読んで手を動かしていかねば……
それでは。

Machine Learning Casual Talks #9 イベントレポート #MLCT

2019年3月8日に開催されたこのイベントに参加してきました。
Machine Learning Casual Talks #9 - connpass
ブログ枠で申し込んだのに記事を書かないまま1ヶ月以上経ってしまった……申し訳ないです……
以下、敬称略です。

発表

@satoshihirose 株式会社スマートニュース「Data Engineering at SmartNews

会場に遅く着いたため発表を聞けませんでした。スライドをご覧ください。

@ruka_funaki(舟木類佳) 株式会社LegalForce 「LegalForceにおける契約書言語処理システムの開発について」

ある言語から別の言語を検索する、言語横断の文書検索

  • LegalForceは、リーガルテック(法律×テクノロジー)の会社

    • 契約がまずいと、揉め事が起きたり訴訟が起きたり…
    • 弁護士でも35%ミスをする というアメリカの統計もある
    • 現在はベータ版を各社に使ってもらっていて、4月に正式版をリリースする予定
  • できること

    • 契約書のレビュー:抜け漏れがあったら指摘する
    • 条文検索:過去に結んだ契約から条文を検索する
  • 構成

  • LegalForce Zoo:公開しているAPIの集まり。各APIを動物と関連させているので動物園という名前

    • Article Search
    • Document Parse
      など10以上ある。実際の製品ではこの各APIを組み合わせて作っている。
  • 事例紹介:契約書の構造解析(パース)
    契約書を意味のまとまり(第何条とか)に分割したい

    • 結構いろんなパターンがあって、複雑……
    • 正規表現の多用でなんとかしてたけど、つらい
    • いろいろ考えて、下記のやり方にした
      • 行ごとに分割する
      • 行ごとにラベルをつける(正規表現を使って)
      • まとめる
      • この「まとめる」に、オートマトンによる状態遷移を使った
      • 例えば「条文のタイトルは既に出てきた」のような状態を作り、1行を読み込むごとに状態遷移する

LT

@mogamin (Mogami Takashi)ウルシステムズ: 「Pytorch強化学習プラットフォーム?Horizonのドキュメントを読む」

  • pytorchの強化学習フレームワーク、Horizonが1月末あたりに出てきた
  • GitHubを見てみると、Scalaが7%ほどある!? (Sparkパイプライン部分だと思われる)
  • 他の強化学習プラットフォーム(chainer RL、keras RL)と違ってプロダクションユースケース向けに設計したよ
  • 大規模データに対応しているよ
  • 大きな値の特徴量が出てくると処理が不安定になるので、適切に正規化する

@nishiba(西場正浩) エムスリー: 「Graphの推薦システムへの応用」

  • 医療向けのサービスなので、データ数が少ない
  • 日本の医者は約30万人です。
  • 正解ラベルが少ない…
  • しかし、そのおかげでグラフがメモリに乗るんじゃないの?
  • 医者に向けたメールで、ニュース記事を推薦することが対象
  • cold-start問題(評価用のデータが集まる前の初期段階は推薦ができないという問題。参考)に対処できる
  • LDA(Latent Dirichlet Allocation)トピック分類をして、記事のcold-startに対処した
  • ランキングに基づいた推薦は全ユーザーに同一のものを推薦するが、推薦モデルは(もちろん)ユーザーごとに異なる記事を推薦する。
  • 両者をアンサンブルすると、ベースはランキング推薦になるが、ユーザーごとの情報も使っていい塩梅になるようだ

@tkngue(竹野峻輔) Retty: 「Webサービスにおけるデータサイクルのデザイン」

paper.dropbox.com

  • データのエコシステムのデザインって、どうやってる?
  • 飲食店を紹介するキャッチコピーを自動生成する問題
  • テンプレート型、生成型の手法は難しい…
  • ユーザーの口コミからキャッチコピーを切り出した
  • 機械学習は「どれがよりキャッチコピーらしいか」の判定に専念した。ロジスティック回帰を用いた
  • データの隠れた構造を導き出すのは面白い
    • 今回の場合:口コミ文は、飲食店に対する適切な推薦文になるよね!

ディスカッション

  • 契約書はセンシティブなのでクラウドにアップロードするのは難しいのでは?

    • 弊社に問い合わせする会社の大半は「クラウドだろうな」って予想してからお問い合わせしてくるので、あまり問題は起きていない。
      AWSだからダメだね、と言われたのは聞いたことがないね……
      データのセキュリティには留意している
  • 初期段階で契約書をどうやって集めたのか(cold-start問題)

    • 最初は無いので、貰うしかない
    • 製品パートナーの会社と、「そちらの過去の契約書を使わせてください。代わりに製品を使っていいですよ」という契約を結んだ
  • 精度評価の指標は何を使っているか

    • precisionとrecallが多い
    • 学生にも分かりやすい指標。大学の法学部のインターン生が弊社には大勢いる。
  • B2Bだと 「この文言を特に重要視する」みたいな重み付けがあるのでは?

    • ポリシー設定があり、顧客の側で優先度付けを変更する
  • ネガティブな口コミがキャッチコピーに出て来たりしないの?

    • キャッチコピーに出現しやすい単語、出現しにくい単語を最初に入れているので、結果的にネガティブな口コミは除外できている

関連リンク

私はこの勉強会にブログ枠で参加していましたが、同じブログ枠にいた方が先に記事を書いていたので紹介します。

@kumapoさん
Machine Learning Casual Talks #9 に参加してきた - Qiita

それでは。