俵言

しがない社会人が書く、勉強とかゆるふわプロコンのこと

【jupyterで学ぶ】 ゼロから作るDeep Learning - 第2回:3章(その1)パーセプトロンとニューラルネットワークの違い

はじめに

第1回を上げてから四日ぐらいで早くも第2回を上げられるのを嬉しく思います。まあ単に3章を分割することに決めたから早く上げれたってだけなのですが..

やっぱり「ある程度まとまった量で上げたい」とか考えるとズルズルとずれていって結局闇に飲まれていくと思うんですよね(下書きで残っている記事たちを見つつ..)。なので、章を一気にとかじゃなくてある程度切りのいい所で記事を書く形にしようと思います。そのほうが勉強の速度も上がるしね!

そんな感じで今回も「ゼロから作るDeep Learning」を勉強していきます。

3章 ニューラルネットワーク

2章にはパーセプトロンのことが載っていましたが、3章はニューラルネットワークのお話です。
個人的には「パーセプトロンの方が単純らしい」ぐらいの印象を持ってたんですが、よくよく考えると両者がどう違うのかは知りませんでした。(広義にはパーセプトロンニューラルネットワークに含まれそうですが。)この章ではその話が出てきます。

3章は「まとめ」を合わせて7節あるのですが、大体以下のような流れです。

というわけで、今回はその1の活性化関数のお話です。大げさに言えば「遂に明らかになる、パーセプトロンニューラルネットワークの違い!」って感じでしょうか。
因みに前回の終わりで言っていた様に、3章ではNN(※めんどくさいので以降略記します)の学習方法の話が出てきません。3章でNNの動作の仕方を学んだ後、4章で学習方法を学ぶとのことです。では本題に入りましょう。

続きを読む

【jupyterで学ぶ】 ゼロから作るDeep Learning - 第1回:パーセプトロン

はじめに

このブログ、一応勉強するためと銘打っているものの、すっかりたまに競プロの話を書くだけの場になってしまいました。 かつては本を読むモチベーションにしようとしてたんですけどねえ..(ただし一日坊主)

これはアカンということで、久々に本を勉強しながらブログ書くことにしました。また自然消滅するって?いや、今度こそはやり遂げてみせる..!

と、いうわけで題材はコイツです。実は一月ほど前に買ったのに積んだままなんでいい加減勉強したい。

今まで深層学習に興味があって「勉強したい!」と思って本を買ったりもしたんですが、その前のニューラルネット自体の知識がイマイチで二の足踏んでました。
「伝播していくとかイメージはわかるけど、実際にどう動くんかとか学習とかするんかよくわからん!」って状態がずっと続いていた感じ。そんなときに出たこの本は、僕の好きなpythonで本当に初歩の初歩から実装して学んでいくということで、絶対いい勉強になるってことで読むことにしました。
理論的に深いところまでは行かないらしいですが、そこは有名な青色のアレとか濃青色のコレでいずれカバーするということで..

これに加えて、最近はまり出した jupyter notebook をもっと使って習熟するのも目的です。まあタイトルには入れてるけど記事に出てくるかは微妙かも..。伝わりにくいですが可視化の練習をjupyter notebook上でやりつつ勉強しています。

目次は以下の通り。

見ての通り、実はdeep learningが出てくるのは一番最後の章です。ただそこに至るまでを順を追ってやっていくので、ニューラルネットワークを勉強するのにはちょうど良いですよね!

2章 パーセプトロン

「あれ?1章は?」pythonの話書いてるだけなのでパス。pythonの基本の基本に加えて、Numpy(数値計算ライブラリ)やmatplotlib(可視化ライブラリ)が紹介されてました。windowspython入れるなら本にも書かれているAnacondaがめっちゃ楽ですね。

さて、2章はパーセプトロンの話。ぶっちゃけ本当に初歩的なところなので飛ばしても良いところです。概要を言うと、以下のような流れ。

  1. パーセプトロンで単純な論理回路を作る
  2. パーセプトロンの限界
  3. 多層にすることでの表現力アップ
続きを読む

AGC001 参加記

気づけば前ブログを書いてから4ヶ月経ち、もう学生ではなくなっていた..

6月末くらいから再び競プロに参加できるようになり、先日記念すべきAGC001に参加しました!

agc001.contest.atcoder.jp

遂にAtCoderも世界展開ということで、第一回に参加できて嬉しく思います。結果だけ見ると二完で悲しい感じですが(--;)

以下は復習できた問題にだけ触れます。

ちなみにeditorialはこちら

A - BBQ Easy

A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder

基本的に「一番大きな串に肉をできるだけ多く刺したいなら、対となる串もできるだけ大きくする」という発想で解きました。まあソートして順番に出力していけばOK。

実装

N = int(raw_input())
L = map(int,raw_input().split())
L.sort(reverse = True)
ans = 0
for i in xrange(N):
    ans += min(L[2*i],L[2*i+1])
print ans

B - Mysterious Light

B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder

一応解けたものの、時間使いすぎて結局二完に終わってしまいました。シミュレーションするのは無理だろうってことで  N=2,3,..,11 ぐらいまで三角形描いて  O(1) 解を考えたのですが(なぜかあると思い込んでた)、結局時間を使っただけという..。

ただ、例を何個も描いて行く過程で光の軌跡の長さの変化がユークリッドの互除法っぽくなってることに気づいてそれで解けました。想定解法が美しすぎて感動しましたね。

実装

N,X = map(int,raw_input().split())
X = min(X,N-X)
ans = 0
N -= X
while X > 0:
    ans += N/X * X *3
    N,X= X,N%X
print ans

C - Shorten Diameter

C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder

コンテスト中最後に考えていて結局解けなかった問題。解説聞くとああーって感じです。これは解きたかったなあ。コンテスト中は木の直径をとりあえず求めて、直径の長さを持つパスの端を削ってまた直径計算して..まで考えて、いやうまくいかんやんどうしようって言ってたら終了しました。

直径が K なら木の中心から各ノードへの距離がK/2になるってのは言われてみれば確かにそうですね。勉強になりました。

実装についてはKが偶数のときは各ノードが中心であると仮定して、中心からの距離が K/2 以下となるノードの数を数えてます。 Kが奇数のときはエッジが張られてる一組のノードをペアとして、このエッジを無視して両ノードからの距離が (K-1)/2 以下となるノードの数を数えました。

実装

from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad):
    cnt = 1
    if dist < rad:
        for nxt in E[h]:
            if nxt == b:
                continue
            cnt += rad_reach(h,nxt,dist+1,E,rad) 
    return cnt
def solve():
    N,K = map(int,raw_input().split())
    pairs = []
    E = [[] for i in xrange(N)]
    for i in xrange(N-1):
        a,b = map(lambda x:int(x)-1,raw_input().split())
        E[a].append(b)
        E[b].append(a)
        pairs.append((a,b))
    ans = N
    rad = K/2
    if K % 2 == 0:
        for c in xrange(N):
            ans = min(ans,N-rad_reach(-1,c,0,E,rad))
    else:
        for c1,c2 in pairs:
            ans = min(ans,N-rad_reach(c2,c1,0,E,rad)-rad_reach(c1,c2,0,E,rad))
    print ans
solve()

再帰で書いたほうがすっきりするんですけど、pythonで出すとギリギリTLEしました(pypyなら通る)。ところがこれを繰り返しで書くとpythonでもギリギリ通りました。前もこんなことあった気がします。

D - Arrays and Palindrome

D: Arrays and Palindrome - AtCoder Grand Contest 001 | AtCoder

コンテスト中読んだもののそもそも問題の意味がわからなくて、解説放送見てやっと理解しました。なんか数列の問題かと思ったら一筆書きの話になっててびっくりした。

まだ完全に解説が理解できてないので解けたら復習記事書こうと思います。

E - BBQ Hard

E: BBQ Hard - AtCoder Grand Contest 001 | AtCoder

コンテスト中読んで意味はわかったけどどうしていいかわからず放置しました。問題文読んだ中で解説聞いて一番感動した問題です。なのでこの問題だけ詳しく書こうと思います。

ある二つの串焼きセット i,j を選んだとき、串焼きの刺し方は同じものを含む順列を考えて

\frac{(A_i+B_i+A_j+B_j)!}{(A_i+A_j)!(B_i+B_j)!} (通り)

になる(前準備しとけばO(1)で求められる)ってのはいいんですが、問題はこれを全部の組やると {}_NC_2 組だけ計算することになるということ。これだと計算量が  O(N^2) になるので余裕で死にます。それで諦めたのですが..

解法としては、 {}_{n+m}C_m = \frac{(n+m)!}{n!m!}が座標平面上で (0,0) から  (n,m)まで左と下に進まずに至る経路の数であることを利用してます。解説放送見たとき「天才か!」って思いましたね。

サンプルを例に取ると、串焼きセット 3:(2,1) と串焼きセット  1:(1,1)で作れる串焼きの種類は (0,0)から (2+1,1+1)へ至る経路の数になります。で、解説だと分かりやすいように、 (-2,-1)から (1,1)への経路数と言い換えてます。

この経路をdpを使って求める方法は計算量が O(1)になりませんが、重要なのは複数の組での計算が同時に行えることです。串焼きセット3と1,串焼きセット2と1で作れる串焼きの種類を以下のように一回のdpで一気に求められます。同じものを含む順列が出てくると条件反射で O(1) で求めようとしちゃうので、これは本当にビックリしました!

f:id:Tawara:20160720003248p:plain f:id:Tawara:20160720003712p:plain f:id:Tawara:20160720003745p:plain

で、実際の実装としては全部の組み合わせを計算するために、各串焼きセット(A_i,B_i)について (-A_i,-B_i) に 1 を加算し、dpで計算した後は各(A_i,B_i)で値を回収して和を取ります。サンプルだと(1,1) が二つあるので、 (-1,-1)には2が加算され、 (1,1)で値を二回回収します。

f:id:Tawara:20160720011914p:plain

すると求める値は  22 \times 2 + 35 = 79 となる..あれ?本来の解  10 + 10 + 6 = 26と全然違います。理由は下の表に示したいらない部分(青字と黒字)の値も含まれているからです。

f:id:Tawara:20160720011349p:plain

なので、同じ串焼きセットで串焼きを作った場合の種類数を引いて 2 で割れば、 (79 - (15+6+6)) \div 2 = 26 と答えが出せます。これで今度こそOKです。

余談

ところでいきなりなのですが、以下に示すpythonコードの一部を見てください。(  p = 10^9+7 です)

print ((ans - dup) / 2 + p) % p

違和感を覚えたでしょうか?僕はこれのせいで解法を理解したにもかかわらずめちゃくちゃ時間を無駄にしました。

当たり前なんですけど、modとってるのに割り算しちゃダメですよね..本当に何で気付かなかったんだろう..階乗の逆元は前準備のためにしっかり求めてるのに2はそのまま割るという愚行を犯しました。今度から気を付けます。

実装

pypyでも誤差レベルでギリギリ間に合ったのですが(1998ms)、今のPCにC++導入したのでC++でも解いてみました。※include等は省略

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)
 
#define BASE 2000
#define MAX 4000
#define MOD 1000000007
 
LL F[MAX*2+1],Finv[MAX+1];
LL dp[MAX+2][MAX+2];
int A[200000],B[200000];
 
LL pow_mod(LL b,LL e){
    LL ret = 1;
    for (;e>0;e>>=1){
        if(e&1) ret = ret * b % MOD;
        b = b * b % MOD;
    }
    return ret;
}
int main(){
    int N,A_MAX=0,B_MAX=0;
    LL ans = 0,dup;
    F[0] = 1;
    rep(i,MAX*2) F[i+1] = F[i]*(i+1) % MOD;
    Finv[MAX] = pow_mod(F[MAX],MOD-2);
    rep(i,MAX) Finv[MAX-i-1] = Finv[MAX-i]*(MAX-i) % MOD;
    rep(i,MAX+1) rep(j,MAX+1) dp[i][j] = 0;
    scanf("%d",&N);
    rep(i,N){
        scanf("%d %d",A+i,B+i);
        A_MAX = max(A_MAX,A[i]);
        B_MAX = max(B_MAX,B[i]);
        dp[BASE-B[i]][BASE-A[i]] += 1;
    }
    range(i,BASE-B_MAX,BASE+B_MAX+1){
        range(j,BASE-A_MAX,BASE+A_MAX+1){
            dp[i+1][j] = (dp[i+1][j]+dp[i][j])%MOD;
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%MOD;
        }
    }
    rep(i,N){
        dup = F[A[i]*2+B[i]*2]*Finv[A[i]*2]%MOD*Finv[B[i]*2]%MOD;
        ans = (ans + dp[BASE+B[i]][BASE+A[i]] - dup + MOD) % MOD;
    }
    printf("%lld\n",ans*pow_mod(2,MOD-2)%MOD);
    return 0;
}

F - Wide Swap

F: Wide Swap - AtCoder Grand Contest 001 | AtCoder

問題文すら読めていないので何も書けません。時間内に誰も解けなかったそうです。

まとめ

世界向け第一回ということもあってか、どの問題も学びがあるめっちゃいいコンテストでした。こんな問題とけるようになりたいし、思いつくようにもなりたいです。

次回がいつになるかわかんないですけど絶対に参加したい。

SRM684 div2 参加記

ブログ書くのもう三ヶ月ぶりくらいですね。

とりあえずどうにか卒業出来ることが決まり、めっちゃ久々にSRM に参加しました。

せっかくなので久々に参加記も書くことにします。

Easy (250) - Istr

問題概要

アルファベットの文字列  S に対して、文字列に含まれる各アルファベットの数の二乗の総和をその文字列のスコアとする。この文字列から文字を  k 個削除してスコアを最小にせよ。

制約

 1 \le |S| \le 50,  0 \le k \le |S|, 文字列に含まれるのは "a - z" のアルファベットのみ

解法

含まれる数の多いアルファベットから一個ずつ減らしていけばよい。制約が緩いので、一回削除するごとにソートしてました。

実装

class Istr:
    def count(self, s, k):
        cnt = collections.Counter(s)
        l = cnt.values()
        l.sort()
        for i in xrange(k):
            if l[-1] == 0: break
            l[-1] -= 1
            l.sort()
        return sum(i**2 for i in l)

 0 \le k \le |S| だから if 文の判定が実は要らないってあとから気付きました。まあ実害は無いですが。

Med (600) - DivFreed2

問題概要

以下の条件を満たす長さ n の数列 a_n は何通り作れるか。10^9+7で割った余りを答えよ。

  •  1 \le i \le n について  1 \le a_i \le k
  •  1 \le i \le n-1 について  a_i  \le a_{i+1} または  a_i \bmod a_{i+1} \ != 0

制約

 1 \le n \le 10, 1 \le k \le 10^5

解法

a_n を先頭から順番に決めていくとき、 a_{i+1} は直前の  a_i にのみ依存します。もう明らかにDPの匂いがプンプンする。

末尾の値が t であるような問題文の条件を満たす長さ (i+1) の数列の数を dp[i+1][t]とすると、dp[i+1][t]は以下のいずれかを満たす s に対する dp[i][s] の総和になります。

  •  s \le t
  •  s \bmod t \ != 0

問題は各 t に対して s がこれらの条件を満たしているかを全てのsについて確かめると、計算量が  O(n \ k^2)になってTLEすること。この部分で工夫が必要です。

この問題を解決するために累積和を用います。一つ目の条件を満たすsに対するdp[i][s]の総和については、先にdp[i][s]の累積和を小さい方から取っておけば  O(1)で答えられます。

ポイントとなるのは二つ目の条件の方の求め方です。一つ目の条件を満たさないかつ二つ目の条件を満たすsに対するdp[i][s]の総和は、

( s > t かつ  s \bmod t \ != 0 を満たす sに対する dp[i][s]の総和) =

( s > t を満たす sに対する dp[i][s]の総和) - ( s > t かつ  s \bmod t \ = 0 を満たす sに対する dp[i][s]の総和)

と考えてやることで簡単に求められます。

( s > t を満たす sに対する dp[i][s]の総和)については、一つ目の条件のときと同様に先にdp[i][s]の累積和を大きい方から取っておけば  O(1)で答えられます。

( s > t かつ  s \bmod t \ = 0 を満たす sに対する dp[i][s]の総和)については、要するに t の倍数であるような s に対する dp[i][s]の総和です。tの倍数を順番に確かめるのは  O(\log_t k) で行えるので、t+1 から k まで全部確かめるよりも計算量が格段に減ります。

以上により計算量は大体  O(n k \log k) となるのでTLEを脱せます。ちょっとpythonつらそうだったので C++で出しました。

実装

using namespace std;

#define P 1000000007

long long dp[10][100001],acum_u[100002],acum_l[100002];

class DivFreed2 {
    public:
    int count(int n, int k) {
        int i,j,cnt;
        
        long long comp_sum, ans = 0;
        for (i = 0; i < k+1; i++) dp[0][i] = 1;
        dp[0][0] = 0;
        for (i = 1; i < n; i++) for (j = 0; j < k+1; j++) dp[i][j] = 0;
        for (i = 1; i < n; i++){
            for (j = 0; j < k+1; j++) acum_u[j] = acum_l[j] = dp[i-1][j];
            acum_u[k+1] = acum_l[k+1] = 0;
            for (j = 0; j < k; j++){
                acum_l[j+1] = (acum_l[j+1] + acum_l[j]) % P;
                acum_u[k-j-1] = (acum_u[k-j-1] + acum_u[k-j]) % P;
            }
            for (j = 1; j < k+1; j++){
                comp_sum = 0;
                for (cnt=j*2;cnt < k+1;cnt+=j){
                    comp_sum = (comp_sum + dp[i-1][cnt]) % P;
                }
                dp[i][j] += (acum_l[j]%P + ((acum_u[j+1] - comp_sum) % P + P))%P;
                dp[i][j] %= P;
            }
        }
        for (j = 1; j < k+1; j++) ans = (ans + dp[n-1][j]) % P;
        return ans;
    }
};

accumがacumになってるところに英語力の無さを感じる..

Hard (900) - Autohamil

問題概要

0か1のみからなる文字列を読んで動作するある決定性有限オートマトンを考える。このオートマトンの状態は 0 から n-1 の計 n 個で、状態 iのときに0を読むと状態 z0[i] に、1を読むとz1[i]に遷移する。

このとき、全ての状態にちょうど一回だけなるような文字列が存在するか?

制約

 1 \le n \le 50, |z_0| = |z_1| = n, 0 \le z_{0 i} , z_{1 i} \le n-1

感想

解けなかったので感想だけ。問題概要があまり概要になってませんが、要はこのオートマトンの状態遷移図を有向グラフと見たときに、ハミルトン路が存在するか?という問題。今気付いたんですが、よくみたら問題名もAuto''hamil''でちゃんとハミルトンって主張してました笑

正直全然分からなかったのとMedバグらせて時間無かったのもあって手がつけられませんでした。また挑戦したいと思います。

まとめ

結果はdiv2 50位でレートも50ほど上がったので久々にしては頑張った方だと思いたい。ただしょうもないミスでバグらせるのはいい加減止めたいなあと思います。

レートが1163になり、やっと青くなるチャンスが巡ってきました。次こそはdiv1に上がれるようがんばります!