くどうれいん『うたうおばけ』

歌人くどうれいんさんのエッセイ集。ISBNがついていない『わたしを空腹にしないほうがいい』をやっと手に入れて読んでとても良かったので、今作も見つけた瞬間購入を決めた。

 

食べ物がテーマの前作と違って周りの人にフォーカスした作品が多かったように思う。最近短歌が気になっていて、特に自分+/-10歳くらいの世代の短歌を読みあさっている。初谷むい、九螺さらら、千種創一とか。自分の中の感覚に近いけど自分では思いつかないような感性を見つけるのがとても良い。くどうさんのエッセイにも似たものを感じる。

 

特に自分が好きだったのはお婆ちゃんの話だ。おれもこんなお婆ちゃん欲しい。あんまり試し読みせずにエイヤッと買って読んで欲しいが、出版社のnote.comからこの話は読めるということを後で知った。(note.comの連載は読んだことがなかった)

 

https://note.com/kankanbou_e/n/nca5906988281?magazine_key=m332e3bb4947d

 

くどうさんの短歌を残念ながらあまり読んだ事がないので、今度はそちらも読んでみたい。

Kaggleの"Intro to SQL"をやってみた

自分用メモ。ドットインストールの動画をさっと眺めたぐらいでSQLを触ったことがなかったが、勉強がてらやってみた。とりあえず無料のものでいい&自分の環境でやるのはめんどくさいので、Kaggleのチュートリアルを使うことにした。

 

Learn Intro to SQL Tutorials | Kaggle

 

SQLとBigQuery

SQLにはいくつか種類があることは理解しているが、MySQLとPostgreSQLの違いが何かとか、まったくわかっていない。細かい違いはあるがたぶんここに出てくるような公文で大きな違いはないっぽい。KaggleのSQLはGoogle BigQueryを使っているらしい。

 

SELECT, FROM, WHERE

SELECTで引出したい項目を、FROMで対象となるテーブルを、WHEREで条件を指定する。

SELECT * 

FROM table

WHERE country=US

でcountryの項目がUSであるsub tableが生成される。

 

GROUP BY, HAVING, COUNT()

COUNT()は数を数える。たとえばCOUNT(ID)とあるとIDの数が何種類あるか数える。ID0-99までの顧客リストがあるとCOUNT(ID)は(IDが重複していない限り)顧客数100を返す。SUM()などと同様にこういう複数の値から一つ値を返す関数なのでaggregate functionという。

GROUP BYはCOUNT()の結果を種別に返す。たとえば先ほどの顧客リストにregionという項目があって関東、関西などとある場合、COUNT(ID) とGROUP BY regionによって

関東 25

関西 19

東北 13

...

四国 1

などというような地域別のID数(顧客数)を表示できる。

HAVINGは条件式である。GROUP BY region HAVING COUNT(ID)>1で顧客数が2以上の地域別顧客リストが返る。なのでさきほどの例で言えばリストから四国(IDが1なので)が消える。

 

COUNT(1)で行の数を数えられる。

 

 

ORDER BY

順番を決められる。DESCで降順。なのでORDER BY COUNT(1) DESCで個数順

 

AS WITH

ASはaliasだが、WITH...ASと合わせることで一時的なtable(Common Table Expression, CTE)を作ることができ、可読性をあげることができる。

query_with_CTE = """ 
                 WITH Timetable AS 
                 (
                     SELECT DATE(timestamp) AS trans_date
                     FROM `bigquery-public-data.bitcoin.transactions`
                 )
                 SELECT COUNT(1) AS transactions,
                        trans_date
                 FROM Timetable
                 GROUP BY trans_date
                 ORDER BY trans_date
                 """

のような感じ。例えばたくさんのトランザクションのデータから、顧客ごとに合計額を算出して、それから全顧客に対して平均をとるような処理などに使える。

 

Joining data

pandasのmergeのような感じ。複数のtableをid等を目印に統合する。left join, full joinなどの種類がある。

 

実際全部やるのに5時間くらいだったと思う。Advanced編をやったり、100本ノックをしてみたい。

Learn Advanced SQL Tutorials | Kaggle

 

github.com

AtCoderで緑色になったので振り返りつつ数理科学系大学院生に趣味としてオススメする

はじめに

f:id:ekotto32:20200520092440p:plain

先日のAtCoder Beginner Contest(ABC)168で今年の目標にしていたランク緑色まで到達しました!AtCoder界隈では、色変記事といって、ランクが上がったときに自分が何をしたか振り返り記事を書くようで、多数の良記事があります。私も書こうと思ったのですがせっかくなので振り返りをしつつ、私のもう一つのコミュニティであるポスドク・大学院生に「AtCoder・競技プログラミングは院生の趣味の選択肢として結構アリだと思う」という記事を書きます。

私自身、AtCoderを本格的に始めたのは5ヶ月前でもう既にポスドクをやっていましたが、大学院生時代からやっておけば(サービスをそもそも知らなかったのですが、AtCoder自体は2012年あたりからあるようです)よかったなあと思ったので、この記事を書きました。

 

そもそもAtCoderとは?(競プロ勢は読み飛ばしてください)

AtCoderは競技プログラミングのオンラインコンテスト開催サイト名であり、そのサービス(AtCoder jobsのように就職支援も含まれます!!)を提供している会社の名前です。コンテスト参加は無料です。必要なのはPCと電気代と通信費だけです。PCも高いスペックは必要ないです。

コンテストは(典型的なABCと呼ばれるものだと)100分間の間に問題A-Fの6問出題され、解いた問題に応じて得られる点数の合計およびその速さを競うものです。問題文があって、それにそった入力を受け取り、答えを出力するプログラムを書いて、提出すると、20ケースほどのテスト入力にたいして正しく出力されているかチェックされ、全てのテストに正しい答えを出した場合問題クリアとなります。同じ点数を取ったユーザー間では最後の問題を解いた時間+間違えたプログラム提出数に応じたペナルティ時間で順位がつけられます。

atcoder.jp

規程時間終了後、順位に応じて「パフォーマンス」という数値が計算され、今までのコンテストのパフォーマンスに応じて「レーティング」という数字が決まります。レーティングに応じて複数の色(段位みたいなもの)に分かれていて、下から灰色、茶色、緑色、水色、青色、黄色、橙色、赤色...となっています。ランクに応じてどんなスキルが身に付くのか、詳細については、下のAtCoder社長さんのブログが良いと思いますので、ご参考ください。

chokudai.hatenablog.com

AtCoderは日本のサイトなのですが、同様の海外サイトで著名なものにCodeforces、Topcoderなどがあげられます。他のサイトのコンテストに出ていないので詳細な言及は避けますが、問題文が英語である、開催時刻が日本時間の夜中になる可能性がある、コンテストのルールや開催頻度が異なるなどの違いがあるようです。ちなみにAtCoderの人気はうなぎのぼりのようで、最近のコンテストには海外からの参加者も含め、10000人以上が参加しているとのことです。

良い成績を残すには、もちろんプログラミング能力(アルゴリズムや計算にかかる時間を考える、バグらずにコードを書く)も問われますが、所謂一般的な数学の知識(高校数学~大学基礎科目くらい?)も問われる場合があります。例えば前回は時計の針(分針、時針)の間の距離を求める際に、三角関数の知識を用いる問題がありました。もちろん高校で習う知識なので大半の参加者(中学生とか若い参加者もいらっしゃいます)は最低でも三角関数を「知っている」状態ではありますが、「いつも使っているのでパッと解法が浮かんでくる」とスピードの面で有利です。数理科学系の大学院生だと、こういったところにアドバンテージがあるかと思います!

atcoder.jp

もちろん、数理的な能力・プログラミング能力だけではなくて、解法を思いつく発想力や、典型例を応用する能力、また、よりメタな能力として新しいことを学ぶ力が鍛えられるかと思います。競技という側面はありますが、自分との戦いという面が強く、コミュニティの中でいろいろと解説を出してくれている競技者の方がたくさんいらっしゃいますし、ランクが上がった場合(Twitter等で報告すれば)皆に祝福されます。コツコツとやっていってランクが上がったときの楽しさはあつ森を超えます(当社比)!!

個人的には学んだことが直接役に立たなくてもいいかなと思っていますが(趣味なので)、実際には「あー大学院生時代にこれ知っておけば〇〇のコードもっと速くなったかもなあ」といった件も存在しました。一個人の考えですが、研究は思い通りに進まないものなので、大学院生時代には「研究と違ってやったらある程度進捗があって気分転換になるもの」を趣味とするのはより良い大学院生活を送る一つの方法だと思います。競プロは(もし、自分に合っているなあ、と思うのであれば)ストレスをそこまで貯めずにかつ「趣味だけど、ある程度実用性もある」くらいのポジションでいてくれるので悪くない選択かと思います。

もちろん、同じ数理科学系の大学院生の中にも多種多様な人がいて、素養があって楽に上に行ける人もそうでない人もいるのは重々承知しています。個人に必要な努力の質や量は目標にも応じて変化します。無理のない範囲でやってみる、くらいのスタンスがお勧めです。

と、いうわけで勧誘はこのくらいにして自分の開始当時の様子や緑色に上がるまでやったことをつらつらと書いていきます。 

 

自己紹介(AtCoderはじめる前はどんなだったか)

AtCoderを始める前の自分を思い返してみると、

研究で必要だったので、独学でC++をやっていた(授業等で、体系的に学んだ経験がないので、知識がちぐはぐ)

物理をやっていたので、高校-大学基礎くらいの数学は馴染みがある。最大公約数・最大公倍数がなんたるかはわかっているし、三角関数もわかる。整数問題も(わかるというと語弊があるのですが)苦手ではない。Nが素数であるか判定するのにはSqrt(N)に比例した時間でわかる、というのがわかる。「グラフ」というのが界隈では図を意味するのではなく、辺と頂点によるアレだと認識している。(AtCoderは整数やグラフに関連した問題が多い。最初から知っている必要はないけど苦手意識がない方が楽しくできる。)

標準入出力はできる。四則演算+商の余りを求められる。if, for文は書ける。配列というものを知っている。STL(C++についてる標準ライブラリ)はvector(可変長配列)ぐらいしかしらない。文字列の編集はあまり知らない、substr()は知っている程度。文字から数値、数値から文字への変換もググらないと思い出せない。

計算量という概念は知っている。ランダウの記法(O(n)とか)も物理で似たような議論があるので知っている。実際に計算量を気をつけてプログラミングした経験は指折り数える程度。

(余談ですが計算量という概念について、以下の記事が面白かったです。実務でも大事な時がある。)

qiita.com

再帰という概念は知っているけど、実装したことはない。累積和、幅優先探索(bfs)、深さ優先探索(dfs)、動的計画法(DP)についても言葉を知らなかった。貪欲法という言葉は知らなかったけど、こういった素直なアルゴリズムは自分で時間をかければなんとなく実装できるくらいの感じ。しゃくとり法、いもす法、ダイクストラ法などは今でもあんまりできない。Unifon Find木やセグメント木もできない。

タッチタイピングがあまりできない。速くないし、ミスも多い!(NとMを打ち間違えていることに気づかず、ペナルティでパフォーマンスを約10%損したことがあります)(でも、典型的なコードを先に作っておいて、コピペして最小限を手打ちにすることである程度カバーできます。)

個人の傾向として、簡単な問題を人より速く解くのは得意。難しい問題をじっくり考えるのが苦手。

といった感じだったと思います。いくつかの専門用語が出てきてこれからAtCoderをはじめようかと気になっている方はギョッとするかもしれませんが、5ヶ月前の私もDPとかセグ木とか聞いたこともありませんでした。焦らず少しずつ学んでいければ良いので、あまり過剰に身構える必要はないかと思います。

 

AtCoderを始めた頃~茶色まで

昨年の夏くらいに何も知らずにAGC(AtCoder Grand Contest、難しい方のコンテスト)に出て、一回挫折しかけましたが、年末からコツコツABCをやり始めました。Ratedコンテストに出た回数はそこから数えると緑色になるまで18回です。最初のコンテストは37分3完+4ペナ(×5分)=57分で、茶色のパフォーマンスだったようです(この回のC問題は比較的素直な問題で、運がよかったです)。

手元で環境構築はしていなくて、AtCoderコンテストサイトのコードテストページに打ち込んでやっています。キルリングとか補完が使えないので、本当は手元で環境を整えてやる方が良いと思います...ただ、プログラミング始めた頃に私が嫌だったのが環境構築なので、そういった意味では本当に初心者でも気にせずに始めることができるのが良いところです。

その後7-8回かけて茶色まで行きました。AtCoderは参加コンテスト数が少ないうちはレーティングが低めに出る補正がかけられているので、最初のうちはあまりレーティングは気にせずに個々のコンテストの結果(=パフォーマンス)を気にしていました。また、どうしてもコンテスト形式の慣れは必要です。もちろんプログラミングの中身も大事ですし、自分の実力を伸ばすことがまず大事ですが、落ち着いた回答を心がけたりミスをしない仕組みづくりをするなど、総合力でコンテストで良い結果を出すようにしていました。といっても最初は全然ダメで、例えば(もう二度とやらないと誓っていますが)開始20分後から参加して(同じ問題を解いた場合速さで決まるので)順位が大きく下がってレートを下げてしまったこともありますし、コードテスト(後述)をしないまま提出してしょうもないミスをしたことも多々あります。

コンテストを解く際に気をつけていたこととして、コードの内毎回書く部分は予めどこかにストックしておいて、コピペしていました。極力タイプミスをなくすためです。また、典型的な〇〇というアルゴリズムを使えば良いとわかったが実装したことがない際に他人のコードをコピーして問題に合うように修正したりしていました。コードの中身を一行づつ理解できていれば問題ないかと思います。AtCoderの一つの問題に対して書くコードは(我々のようなレベルの問題では)そんなに長くないので、新しい概念でもその場で動くプログラムを組む状態まで持っていくことは可能だと思います。

めんどくさいんでA問題とかスルーしたくなりますが、コーナーケース(業界用語で入力な極端な場合という意味だと思います)で間違った答えを出したり、先述のしょうもないミスをしたりするので、コードテスト(問題に含まれている入力例に対して出力例を正しく返答できるかチェック)しておくのは大事だと思います。戦略として「AB問題早とき!Cはどうせ解けない!」といったことを行う場合にはもしかしたら数秒を争うのでコードテストの時間を端折りたくなりますし、わたしもそうだったのでわかります。ただ、ペナルティが5分なのでそこが大きすぎることを考えると、きちんとテストして提出する方が良いと思っています。

コンテストが終わった後の復習として解説pdfを読むのはオススメです。もちろん時間をかけて解説動画をみた方がきっと良いのですが、そこは解説を読んでもわからなかったら、という形か、あるいは数日後にググって他の方の記事を読んでみるというのも良いかとも思います。基本的にB問題まで解けたらC問題、C問題まで解けたらD問題だけ復習しました。自分がギリギリ解けなかった問題だけ復習して、それ以上の問題は(コンテスト中にCが解けなくて時間をかけてDを考えたけどやっぱダメだった、みたいな場合にC,D両方解説読んだことはありますが)基本的には時間を割く必要はあんまりないかと思います。

いわゆる精進と界隈で言われますが。そういった過去のA問題全埋めやB問題全埋めは行ませんでした。全部解いていたら時間の割りに(それなりにわかっている問題も多いので)得るものは少ないかなと思っていました。ただこれも工夫次第で、多様な問題に触れることを念頭に、各問題をチラッと見て、実装したことないような解法があれば練習がてらやってみる、というのをやっても良かったかなと反省しています。

茶色になるころには、文字列の操作について昔より詳しくなりましたし、mapやvectorなどのC++のSTLを簡単な場合ならスッと実装できるようになりました。「昔の研究の〇〇の場面でこれ知ってたらもっと楽に□□できたかも」と思ったりしたので、茶色になるだけでも(研究で簡単なプログラミングをする場合は)ちょっと役に立つ場合があるかもしれません。

 

茶色から緑色になるまで

Atcoder Problemsというサイトがあって、茶色になるまえから知っていましたが、茶色になったあたりから活用するようになりました。何日連続でAC(Accepted, 正解すること)したか表示される機能があって、これを目安に一日一問解くようにしていました。解く問題の難易度はその日によってマチマチで、時間があるときには自分がギリギリ解けるくらいの問題や、ググって解法を調べないと解けないくらいの問題を解きましたが、時間がないときには簡単に解法を思いつく問題をとりあえず解いていたりしました。「毎日15分くらいでいいのでコツコツ問題に触れる」というのは実力アップにとても重要だと思います。

https://kenkoooo.com/atcoder/#/table/

私の現状の埋まり具合下記のようになっていて、あんまり精進が足りてないのがわかるかと思います。

f:id:ekotto32:20200524052216p:plain

また、chromeの拡張等をつかっていくつかAtCoderサイトの表示をカスタマイズしました。本来であれば茶色になるまえからやっておけば良かったです。

 

greasyfork.org

greasyfork.org

greasyfork.org

どれも好きですが、上二つはコンテスト中により詳細な情報が目に入るので、もしかしたら使いたくない人もいるかもしれません。

茶色になったころ(少し前だったかも?)、それまでAtCoderを始めるまでの貯金でやっていた自分がもうちょっとできるようになりたいと思って、勉強したのが累積和でした。実際Webで検索すると多くの人の解説記事があります。私はいろんな記事でトライして(自分に合った記事を見つけたというよりは、単純にその記事を読んだときにモチベーションが最も高かっただけかもしれませんが)とある記事である程度実装までできるようになりました。記事を読む→コピペでもいいから実装する→見ずになんとなく実装にトライしてみる→ダメだった場合、実装のどこかで論理を理解していないのでそこをやり直す、といったステップを踏んだように記憶しています。早速勉強したそのあとすぐか、あるいはその次のコンテストで累積和を使う問題が出たような記憶があります。

茶色になってからもう少ししてできるようになったことで一番本質であったと現在思っているのが、全探索です。もともと、情報系やコーディング畑ではないので、どちらかというと長いコードをしっかり書いて探索するよりは発想でうまく計算の楽をすることを念頭に置く、きれいに問題を解きたいタイプでした(「ハンマーを持つと問題が全部釘にみえる」に通ずるところもあります)。しかし、全探索で間に合うのにそうやってしまうのは競技プログラミングの基本からはちょっと外れてしまうのかな、と思うようになり、問題をみるとまず全探索できるか、というのを検討するようになりました。本質的な技術というよりは意識の問題が大きかったと思いますが、最初はこれが本当にできていなくて、AtCoderに慣れてきて茶色になれた頃から少しづつ意識的に問題をみるようになりました。全探索できるかという点においては計算量という概念が必要で、元々計算量についてはなんとなく知識がありましたが、解説記事等一通り眺めて勉強しなおしました。問題をみてしっかりコードを書けば時間内に全探索できるケースだ、ということが判断できるようになったのがレートを上げるためには一番大きかったと思います。

その他のアルゴリズムについて話しておくと、私のやったことの中にDP,DFS,BFSがあります。動的計画法(DP)については、茶色になった後累積和を学び終えたころにQiita等を参考にして簡単な問題について実装してみました。複数の解説記事があがっているので、各々が合う記事をみつけてやってみるのをお勧めします。深さ優先探索(DFS)、幅優先探索(BFS)についても同様です。DPをやってこちらに移るのが理解がより容易になるかと思います。もちろん実装できたり手法自体を理解したりすることも大事ですが、問題をみて「「最短経路」と問題にあるし、BFSかも?」とか「全通り試すにはDFSが使えそうだな」といったように、どういう場合にこの解法に落ち着くのか、といった判断を行えることがまず大事だと思います。

ダイクストラ法や、しゃくとり法など、典型的なアルゴリズムは他にも何個かありますが、私はまだできていません。緑色になるために全てを知っている必要はないですし、同じ緑の人でもきっとできることはそれぞれ違っているかと思います。コンテストにたくさんでそうなものから覚えた方が、自分のレーティングが上がる機会もそれだけ増えるのでアプローチの一つかと思います。あるいは、自分がとっつきやすいものから取り組んでいくのもモチベーションを保つ上で一つの手かもしれません。緑色の次の水色になるには典型的な解法・アルゴリズムのほとんどをある程度こなせる必要があると思っていて、それが緑色から水色にあがることが特に難しいと(個人的に)思っていることの一つです。

 

まとめ&これから

というわけで、AtCoderと自分の今までの取り組みについて簡単に紹介してきました。個人差はありますが、緑色までは自分の得意なことだけ(私で言えば簡単な問題の早解き+少数の典型アルゴリズムの習得)である程度進めると思います。もちろん、大学院生の中にも多種多様な方がいらっしゃるので一概に言えませんが、特に数理系の方で競技プログラミングの面白さに目覚めるかたは一定数いると思います。研究に役立つこともありますがかといって近すぎもせず、私個人としては息抜きとして良い選択肢でありつつ、楽しんで学び続けられたと思っています。あまり目線を高くせずに、まずは茶色や緑色を目指して気軽に無理のない範囲で時間のある週末に参加してみることをお勧めします!

ただ、個人的に趣味としては「楽しい」「負担にならない」などが重要だと思っています。もちろんどんどんレベルが高いところを狙う段階になってくると逆に苦しくなることもあるので、個人の判断で適度にやめるのも良いかと思います。

私個人としては、もちろんうまくいかなかった時の苦しさはなかったといえば嘘になるのですが、目標を達成したときの面白さを感じたので、これからも頑張って次の水色を目指したいと思います。とはいってもここからは一段と厳しいのは重々承知しているので、焦らず半年くらいかけてコツコツとやっていきたいと思います。データ分析コンペであるKaggleに出てみたいという目標もあるので、そちらと折り合いを付けつつ、うまく時間を割り振っていけたらいいなと思います。

思えば今まで二回ほどABCDを素早く解いて水色パフォーマンスを出しましたが、E問題を時間内に解いたことはないので、Dまで落ち着いて素早く解けるようになりつつ、時々Eを解けるようになりたいなと思っています。DP,DFS,BFSといった典型アルゴリズムについて、まだしっかり自分のものにした感覚はないので、関連した問題を解いて精進していきます。

参考文献

学習する上でお世話になったもので、上記以外の物をお礼も込めてリストアップしておきます。

qiita.com

qiita.com

上記二つは最初に読んでみるとイメージがわくかもしれません。

 

qiita.com

この記事は「便利ツール」の欄でお世話になりました。

 

下記はいろいろな解法を調べるときにお世話になっています。

drken1215.hatenablog.com


qiita.com

 

qiita.com

 

最後に色変記事について、すべてが自分にとって正解とは限られませんが、atcoder 〇〇色と検索するとその色になった人等の記事がたくさんヒットすると思います。また、単純に中身関係なく他のプレイヤーの成功をみるとモチベーションアップにもなると思います。

AtCoderで茶色から緑色に上がるには何を勉強すればよいか - テストステ論

AtCoderで緑色になりました - Qiita

 

こういったメタな情報を集めやすくなって皆の実力が上がっていて、とある色になるまでの実力がどんどん上がっていっている?という話もあるようです。事実かどうかはわかりませんが。良いことも悪いことも含んだ話かもしれませんが、何か考えるとっかかりがあることは初心者にとってはありがたいことだと思いますし、私自身他の方の解説記事がなければ緑色に来られなかったでしょう。自分の力で情報を集めて、自分の糧にできる人が伸びて行きやすいのかもしれません。

Python実践データ分析100本ノックのノック35で困ったとき

Python 実践データ分析100本ノックのノック35で

ValueError: Grouper for 'is_deleted' not 1-dimensional

と出て困ったときのメモ。

 

ぐぐるとどうやら"is_deleted"というカラムがpandasのdataframeの中に重複してできているのが原因らしい。

 

customer_clustering = pd.concat([customer_clustering, cust], axis=1)
customer_clustering = customer_clustering.loc[:,~customer_clustering.columns.duplicated()]
customer_clustering.groupby(["cluster","is_deleted"],as_index=False).count()"customer_id","is_deleted","customer_id"

 

のように間に重複を取り除く処理を行えばうまくいく。

AtCoder Beginner Contest 167 D問題 ループ構造を捉える

問題へのリンクはこちら

 https://atcoder.jp/contests/abc167/tasks/abc167_d 

 

街1からスタートして、N個の街をK回移動していく。K回の間に行かない街もありえる。問題はKが最大10^18と大きいので、愚直に計算していくと間に合わない、ということだ。

 

計算量についての一般的な話は下記のけんちょんさんの記事参照。

qiita.com

 

一方、Nは2×10^5と十分小さい。K>Nの場合、鳩の巣原理から、いくつかの街を複数回訪れることがわかる。そして、とある街にいる際に次にいる街は必ず定まることから、最後は閉ループになっていることがわかる。

 

例えば例1を考えてみると、街1→街3→街4→街1→...

とループしている構造に見える。これから、Kをループ内の個数で割ったあまりを考えたら計算量を楽できそうという予想がつく。

 

例えば3N回移動したときはいつも街1にいる。3N+1なら街3、3N+2なら街4だ。

 

f:id:ekotto32:20200510232250p:plain

入力例1の街を辿っていった際の構造。

 

 

この問題は例が優しいので、次に入力例2を見ると、より問題への理解が深まる。

 

次は

(街1→街6→)街2→街5→街3→街2→...となっていて、ループの中に入るまでに二つの街を経由している。一度ループに入ったら出てこないので、ループ前の街をうまく考えてあげて、ループに入った後の移動回数をループ内の町の個数で割った余りに着目してあげれば良さそうだ。

 

f:id:ekotto32:20200510232706p:plain

入力例2の場合のループ構造

 

 

そこで、町の順番を把握するためにwhile文で街1からスタートして、一回行ったことがある街までたどり着くまで街の順番を覚える。ここでは例えば可変長配列vに訪れた街の番号を詰めることを考える。N<2×10^5なのでこの計算は十分早く終わる。

 

ループ前の街の個数をN_out、ループ内の街の個数をN_loopとすると、K-N_outがループの中で移動する回数であることに気をつければ

d=(K-N_out)%(N_loop)でループ内での移動後の位置がわかる。

さっきの町の順番の配列vには、ループ前の街も含めて考えている。そこで、v[N_out+d]とすれば答えの町の場所がわかる。 

講談社サイエンテイフィク「これならわかる深層学習入門」読書ノート

 

瀧雅人著、「これならわかる深層学習入門」の読書ノート。2017年10月20日発行の第1刷を参照している。

 

 

 

https://amzn.to/2ROJK6B

機械学習スタートアップシリーズ これならわかる深層学習入門 (KS情報科学専門書)
 

 

 

自分のためもあるが、他の人が読む前になんとなく構造を理解できるように書くつもりです。間違い等あればコメントでご指摘いただけると幸いです。読書の補助であって、これだけで知識が完結するようにはもちろん書いていません。

 

また、誤植等について、下記のブログ記事を参考にしました。

http://wshinya.hatenablog.com/entry/2017/12/06/164033

 

第1章はじめに

 

簡単な注意と構成が書いてある。

構成は(必要であれば付録)→2→3→4→5→6までで誤差逆伝搬法まで進む。

7章以降は

7章自己符号化器は6章の後に読める

8章畳み込みニューラルネットも6章の後に読める

9章再帰型ニューラルネットも6章の後に読める

10章ボルツマンマシンは2章が終われば読める

11章深層強化学習は8章の後に読める

というふうになっている。

章を昇順に読んでいけば(言いたかっただけ)良いので、とりあえず2章から順に読んでいく。

 

第2章機械学習と深層学習

深層学習は機械学習の一分野。その両方について述べられる。2.3と2.4以外は式が少ない。

 

2.1なぜ深層学習か

なぜ、深層学習が便利なのか?

主に二点挙げられている。

(1)「コンピュータに明示的な指示をする必要がないこと」

(2)「高い汎化性能を持つこと」

(1)は深層学習に限らず他の機械学習でも当てはまる場合があるが、コンピュータのプログラムに逐一「何々という条件が揃ったら、Aという行動をして、そうじゃない場合はBという行動をしなさい」などと書き込む必要がないということ。これによって問題が少し変わった時により柔軟な対応をしてくれる。

(2)は訓練の時にやった以外の問題にも対応できる、ということである。犬か猫か写真を見て判断しなさい、という問題において、訓練で見せた写真を解けることは重要ではなく、訓練以外で見せた写真について犬か猫か判別できることが一般には重要である。こういった他の問題を解ける能力を汎化性能と呼び、深層学習が高い汎化性能を持っていることから注目を浴びている。

 

(なぜ深層学習が一般にこのような高い汎化性能を持つかという理由については、(こういうのが効いているのであろうという予想はあれど、)まだきちんと理解されていない。ということが3.7節の最後の方にも書いてある。間違いがありましたらコメントください。)

 

2.2機械学習とは何か

深層学習を含む機械学習とは何か?ということについて述べられている。

 

簡単にいうととあるタスク(仕事)があり、とあるパフォーマンスの評価指標がある中で、具体例で経験(訓練)を積ませて機械がより高いパフォーマンスの評価指標を出せるようになることが機械学習だと書かれている。

 

この際に汎化が大事、ということがまた出てくる。与えられた具体例以外をうまく解くことが大事である。

 

2.2.1では二つのタスクの例が挙げられている。

(1)クラス分類

(2)回帰

の二つ。後に2.4節の基礎部分で順番は(2)回帰・(1)クラス分類とひっくり返っているけども、紹介される。

 

2.2.2データセット

MNSITなどの有名なデータセット(学習する際に使える一般に公開された具体例)が紹介される。(2020年現在、MNISTは昨今簡単すぎて他のデータセットに取って代わられつつあるらしい。)

 

2.3統計入門

2.3.1標本と推定

標本と推定について説明されている。

2.3.2点推定

推定量についての説明や、推定量が持つべき性質について書かれている。

(1)バイアスが小さい

(2)分散が小さい

(3)一致性

(3)は(1)とほぼ同じことを言っていないか?と思っていたがよくわからなかった。バイアスが定数だと(3)は満たされない。バイアスがN→♾で0に近づくようなものであれば(3)の一致性は満たされる。確かにバイアスが小さい定数でも一致性は満たされない。

 

二つの例と共に推定量についての議論が進んで終わり。

(1)ガウス分布

(2)ベルヌーイ分布

 

2.3.3最尤推定

パラメトリックな場合について推定量を求めるために使える有力な手法として最尤推定方が紹介される。上記二つの例について最尤推定が用いられる。

 

2.4 機械学習の基礎

逐次アップデートします。(2020/04/19)

 

 

Pythonをシェルスクリプトライクに使って他のコードを実行する

Qiitaに書けば良いと思うでしょ。僕もそう思う。

 

参考にさせていただいたサイト。

kyotogeopython.zawawahoge.com

 

subprocessモジュールを使う。osでも良さそうだが、非推奨っぽい?MacOS High Sierra, Pythonのversionは3.6.3。

import subprocess

 

for i in range(1000):

    subprocess.run(['python', 'anotherprogram.py', str(i) ])

 

runの第一引数にリストを渡して、区切ればよい。

bashのaliasでpy=pythonとしている自堕落な私だが、リストの一番目を'py'としても走らないことに注意。

anotherprogram.pyの引数として今はiを渡している。計算スクリプトをパラメータを変えながら何度も走らせたい場合等を想定している。シェルスクリプトで書いてももちろん大丈夫なのだけど。