読者です 読者をやめる 読者になる 読者になる

【グラフ理論とネットワーク理論】Network and Flow #3

Introduction

Here is the article I wrote last time class.

keita-matsushita.hatenablog.com

Network and Flow

f:id:atiek1121:20170425092743p:plain

Network is defined as below.

Network : Graph G(V, E) in which branch capacity Ci(> 0) is defined.
f(vi, vj) : Branch flow value from vi to vj.
 (0 <= f(vi, vj) <= c(vi, vj) : c is a capacity)

And Flow is defined as below

Flow : f = {f(vi, vj)}
vs : Source, vt: Sink, F = Flow value
・Flow conservation equation

Outgoing flow - Incoming flow = {F for vs | -F for vt | 0 for else}

Undirected network (無向ネットワーク)

The feature of undirected network is below.

0 <= f(vi, vj) + f(vj, vi) <= c(vi, vj)

Maximum Flow Minimum Cut Theorem (最大フロー最小カットの定理)

f:id:atiek1121:20170425095923p:plain

・(X, ~X) : Cut which divides Vs and Vt at X
・Cut capacity c(X, ~X) = Σ(Vi, Vj) (X, ~X)
・Minimum cut (Xo, ~Xo) c(Xo, ~Xo) = min(c(X, ~X))

Maximum Flow Minimum Cut Theorem is defined as below

[ Maximum Flow Minimum Cut Theorem ]
Maximum flow from vs to vt is equal to Minimum cut capacity which divides vs and vt.

f:id:atiek1121:20170425100004p:plain

Maximum Flow Problem

We can calculate only the value of Maximum flow by using “Maximum Flow Minimum Cut Theorem ”. But we can not calculate the route of the Maximum flow.

This problem can solved by only Heuristic algorithm.

Minimum Cost Flow Problem

α(vi, vj) : Cost per unit flow of branch (vi, vj) ・Problem
 Total cost = Σ α(vi, vj) f(vi, vj) → Minimum

f:id:atiek1121:20170425103044p:plain

[ Theorem ]
The necessary and sufficient condition of minimum cost flow is that here are no loops with negative cost.

AtCoder ABC056 C - Go Home

問題

時刻0に直線上の0地点にカンガルーがいる。時刻i - 1から時刻iにかけてカンガルーは現在地点pとするとp - i, p, p + 1のどれかに移動することができる。カンガルーが位置Xに到達する最短時間を求める問題。

C: Go Home - AtCoder Beginner Contest 056 | AtCoder

解法

X = 12に場合を考える。毎時刻、右に進むとき以下のようになる。(p = 位置(t = 時間)と表す)

0(0) →1(1) →3(2) →6(3) →10(4) →15(5)

この時、時刻t = 5の時の現在地はp = 15となりXとの差は3である。上の進み方の内、時刻2から3に変わる時に「動かない」という選択をすると最終地点は3だけマイナスとなりt = 5の時p = 12となりXに到達することができる。これは動きをしていないので最短時間での到達となる。

上記の移動方法をまとめると以下のようになる。

0(0) → 1(1) →3(2) → 3(3)→ 7(4) → 12(5)

全ての時刻で右に進んでいくと、p(position)がXを超えるときが来る。この位置の差をdiff = p - X (p >= X)と置くと、diffはこれまでのどこかの時刻で「動かない」という選択をすればpをXと一致させることができる。これは移動の仕方が、+1, +2, +3, ,,,, + tとなっているからである。

まとめると、時刻tまで全て右に進んだ時の位置はp = (1 + 2 + 3 +, ... + t)となり、(p >= X)となる最小のtが答えとなる。

等差数列の和の公式

今回の移動方法は、全て右に進んだ場合{1, 2, 3, 4, 5, 6, …., t}となる。これは等差数列であり、この数列の項の総和は等差数列の和の公式によってO(1)で求めることができる。

等差数列の和の公式
sum = (項の数 * (初項 + 末項) / 2) = (t * (t + 1)) / 2

ソースコード

AtCoder ABC057 D - Maximum Average Sets

問題

D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder

N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、その最大の平均値となるように品物を選択する通り数を出力する問題。

解法

まずは、全列挙できるか考え見る。

全列挙による解法

品物を選択する方法を全列挙し、平均値を計算するという方法を考えてみる。全列挙の通り数は、N個の中からi(A <= i <= B)個選択する場合の数の総和となる。N個の中からi個選択する場合の数は、NCi (nCk: combination)と表す事ができる。よってΣ(A <= k <= B) nCkとなり、最大で計算量はO(2N)なる。この場合、N = 50の時に間に合わない。よって別の解法を考える。

ソート済みの配列からA個取る解法

この問題のポイントは平均値を出すということだ。価値の配列を昇順のソートすると、先頭から後方にかけて値は小さくなる。この時、先頭からA個取った場合が平均値が最大となる。これは平均の計算方法が分母に選択した要素数を当てるからである。

次に、平均値が最大となるような品物のとり方の場合の数を考えてみる。具体的に、以下のような場合を考える。

N = 4, A = 2, B = 3
values = {20, 10, 10, 10}

上記の例では、先頭からA個、つまり2個取った場合、選択した品物の価値は{20, 10}となる。これらの値で平均値を計算したものが最大の平均値となる。しかし、A番目である10という数字はA番目以外にも存在する。つまり、平均値を計算するので、A番目以外の10を選択しても最大の平均値となる。今回はA番目と同じ数はvaluesの中に合計で3つ存在する。また、先頭からA番目までの範囲で10は1つ存在するので、平均値が最大となるには選択する品物の中に10は1つ含める必要がある。10の合計数は3つなので、平均値が最大となる選びからは、3C1通り存在することが分る。

今度は以下の例を見てみる

N = 5, A = 2, B = 3
values = {1, 1, 1, 1, 1}

この例の場合では、先頭の数字とA番目の数字が一致している。つまり、選択する全ての数字が同じ数字の場合を考える。A番目の数をVaと置いた時にvaluesの中でVaと一致する数の個数をCountVaとすると、CountVa個の中からi個選択する場合の数CountVa C iの総和(A <= i <= min(CountVa, B))となる。これは、平均値の性質で全て同じ数字であれば、選択する数を増やしても平均値は変わらないからだ。

パスカルの三角形によって組合せを求める

nCkなどのコンビネーションはパスカルの三角形によって求める事ができる。パスカルの三角形は動的計画法を使うことで計算量O(N2)で作る事ができる。

詳しくは以下を参照。

パスカルの三角形を用いてコンビネーション(組み合わせ)のクラスを実装する - マツシタケイタの技術ブログ(勉強中)

全体の計算量

後者の解法の計算量を考える。

  • 配列をソートする → O(NlogN)
  • A番目の数と同じ数字を探す → O(N)
  • パスカルの三角形を作る → O(N2)

よって全体の計算量はO(N2)となる。Nの最大は50なので間に合う。

ソースコード

AtCoder ABC057 C - Digits in Multiplication

問題

C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder

整数N(1 <= N <= 1010)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値する関数と定義されている。

解法

約数を全列挙する方法を考えてみる。整数iを1 ~ Nの範囲でforループさせ、Nがiで割り切れる時、A = i, B = N / iとなりA, Bを求める事ができる。F(A, B)は計算量1で求める事ができるので、全列挙した場合の計算量はO(N)となる。今回の問題ではNは最大で1010なので間に合わない。そこで計算量を減らす工夫を考える。

N = A * B = B * A という性質に注目する

N = A * B = B * Aという性質に着目することで計算量を大幅に減らす事ができる。N = 20の時を考えてみると、A = 4, B = 5の時とA = 5, B = 4の時のF(A, B)は同じ値を返す。つまり、Nの約数A, Bに関してA > Bとなる範囲は計算しなくて良いことが分る。

この条件でiの範囲を再定義すると、1 <= i <= sqrt(N) となる。(sqrt(N)はNの平方根)

これによって計算量はO(sqrt(N))となり、この問題を解くことができる。

ソースコード

【グラフ理論とネットワーク理論】Matrix Expression of Graphs and Paths #2

Introduction

Here is the article of the last time class.

keita-matsushita.hatenablog.com


Matrix Expression of Graphs and Paths

f:id:atiek1121:20170418092017p:plain

Graphs can be expressed by matrixes. Below matrixes express above the graph.

Incidence matrix (接続行列)

Cols represents branches and rows represents nodes.

+1 means that the node has outdegree from the node and -1 means that the node has indegree from the node.

Path matrix (経路行列)

Cols represents branches and row represents path.

So in above matrix means that the first path is through a1, a3 and a5.

Adjacency matrix (隣接行列)

Both cols and rows represent nodes. 1 means that there is a branch between the nodes. Adjacency matrix can express the loop of V3 node. So this matrix is very useful.

Adjacency matrix has an important theorem.

[ Theorem ]
The element of Al represents the number of paths with l branches.

In A2 matrix, the matrix has 2 in 0th row and 2nd col. This means that There are two paths from V1 to V3 with two hops. The one path is through a1 and a3. another paths is through a2 and a6. The both paths hops with 2 branches. In A3 matrix case, the number of hops become 3 as well. So, the index of power corresponds with the number of hops.


Search for Shortest Path

The distance in graph can define as below.

Distance: Sum of the length of the branch of a path
Distance graph (距離網): Graph in which distance is defined

Shortest path tree

Below graph G, T is the shortest path tree from V0 to V1, V2, V3, and V4

f:id:atiek1121:20170418095340p:plain

If T covers G, the T is called Maximum shortest path tree.

Search methods of shortest path

We want to know the shortest path in graphs whose branch have distance. The distances are not just 1. Any number can be the distance of the branches. So we can not find the shortest path by just counting the number of branches between the nodes.

There are some methods to find the shortest path

  1. Heuristic method
  2. Dijkstra Algorithm

【Deep Learning お勉強 #3】ニューラルネットワークとは

はじめに

前回の記事はこちら

【Deep Learning お勉強 #2】パーセプトロンを実装してみよう - マツシタケイタの技術ブログ(勉強中)

今回はニューラルネットワークについて触れる。

パーセプトロンからニューラルネットワーク

復習も兼ねてパーセプトロンの特徴は以下の通りだった。

また、これまでのパーセプトロンの話では、重みやバイアスは実現したいものによって手動で値を設定していた。 ANDゲートを表現する場合には、どのように重みとバイアスを設定すれば、2つの入力値をパラメータとして受け取った時にANDゲートと同じ挙動をするかを人間が考え設定する必要があった。

ANDゲートのような単純なものであれば難はないが、より複雑な処理をさせたい時に重みやバイアスのを適切に設定することは難しい。

ニューラルネットワークは重みの設定を自動化できる

ニューラルネットワークはコレを解決することができる。適切な「重み」をデータから自動で学習できるというのが、ニューラルネットワークの重要な性質の1つとなる。

つまりニューラルネットワークを用いれば、ある入力値をデータとして入れた時に、こちらが意図するような値を出力するような関数を自動で生成することができるということ。(だと認識している)

ニューラルネットワークの形態

ニューラルネットワークは以下の3つの層(入力層、中間層、出力層)に分ける事ができる。

f:id:atiek1121:20170417164451p:plain

パーセプトロンと同じような構造になっていることが分る。 それぞれのニューロンで計算された値をまた次のニューロンの入力値として受け取りさらに計算させるような構造だ。

また、ニューラルネットワークを説明する用語として「活性化関数」というものがある。

活性化関数

パーセプトロンの計算方法を思い出してみると以下のように書ける。

このh(x)のような関数と活性化関数と呼ぶ。入力信号の総和がどのような活性化(発火するか)するか決定する役割があるからだ。

つまり、これまで見てきたパーセプトロンの内部では、入力として受け取った値と設定された重み、バイアスを活性化関数によって計算され、その計算結果の値を用いて出力の内容を決定させていたと言える。

活性化関数は種類がある

活性化関数にはいくつか種類がある。代表的なものは以下の3つだ。

ステップ関数

ステップ関数はパーセプトロンで採用されていた活性化関数だ。計算結果がある閾値を超えたらある値を出力する。

実装すると以下のようになる。

また、ステップ関数をグラフにすると階段上になる。

シグモイド関数

シグモイド関数は、ニューラルネットワークでよく用いられる関数の1つである。

実装すると以下のようになる。

シグモイド関数をグラフにすると、ステップ関数を滑らかにしたような曲線を描かれる。

ニューラルネットワークでは非線形関数を用いる

ニューラルネットワークの性質を変えるものはどの活性化関数を選ぶかということだ。 活性化関数は非線形関数で無ければならない。

ニューラルネットワークは活性化関数を何層も重ねて複雑な処理している。もし、活性化関数がh(x) = cx (cは定数)のような線形関数の場合、層を重ねる意味がなくなってしまう。仮にy(x) = cxを3層に重ねてみるとy(x) = c^3xと表現できてしまい、層を重ねる事に意味がなくなってしまう。

層を重ねることの恩恵を受けるために、活性化関数に非線形関数を使う必要がある。

ニューラルネットワークの計算には行列の内積を使う

ここまでで、ニューラルネットワークの内部ではどのような計算が行われているかが分かった。まとめると以下のようになる。

  1. 入力層で受け取った入力データを活性化関数によって計算する
  2. 活性化関数で計算した値を中間層のニューロンの入力値として、受け取り、活性化関数によって再び計算される。(中間層は複数の層になる場合もある)
  3. 中間層によって計算された値を出力層によって出力する。

※出力層の挙動は後述する。

つまり、最終的な出力を得るまでに、かなりの量の計算をする必要がある。入力データの量、ニューラルネットワーク内のニューロンの数が膨大になれば計算時間がすごいことになってしまう。

しかし、行列の内積を用いることで計算量を大幅に減らすことができる。

出力層の設計

出力層の設計の仕方も何パターンかあるようだ。出力層の設計を決定させるためには、どんな問題を解きたいかによる。機械学習の問題は大きく以下の2つに分ける事ができる。

  • 「分類問題」:データがどのクラスに属するかを解く問題
  • 「回帰問題」:入力データから数値の予測を行う問題

どの問題を解くかで、出力層にどの関数を設定するべきか決める事ができる。分類問題を解くためには、よくソフトマックス関数が用いられる

ソフトマックス関数

k番目のニューロンのソフトマックス関数によって出力される値は、出力層の1つ手前の層の全てのニューロンからの計算結果の和を分母として、k番目のニューロンの計算結果を分子として計算される。

この性質は確率分布として表現できる

ソフトマックス関数は確率分布を表現する

ソフトマックス関数によって出力された値は、上記の性質により0.0 ~ 1.0の間の少数値を取る。そして、出力層から得られた全ての出力値の総和は1となる。これは確率の性質と同じである。

つまり、ソフトマックス関数を使うことで確率分布を表現することができる

最後に

ここまでで、ニューラルネットワークの構造や内部での計算方法などを知ることができた。しかし、まだ重みの設定を自動化する話は登場していない。次の章をちら見すると「ニューラルネットの学習」とある。おそらくこの学習によってニューラルネット内のパラメータを設定しているのだろう。

【Deep Learning お勉強 #2】パーセプトロンを実装してみよう

はじめに

この記事はパーセプトロンを実際に簡単な例を使って実装してみようというもの。 パーセプトロン自体の説明は以下の記事を参照。

keita-matsushita.hatenablog.com

論理回路パーセプトロンで表現する

以下のテーブルはANDゲートの真偽値表である。(x1 AND x2) => yとみると、ANDゲートの場合、x1、x2が共に1の場合のみyが1となる。

x1 x2 y
0 0 0
1 0 0
0 1 0
1 1 1

よくif文で使う、両方とも真であれば式全体も真となるあれだ。 ANDゲートの他にもORゲート(どちらかが真であれば式全体も真)などがある。 これらのゲートはパーセプトロンを使って表現することができる。

パーセプトロンの簡単なおさらい

パーセプトロンとは、複数の入力値を受け取り、重みとバイアスを用いて乗算の総和が0を上回る時に発火し、ある値を出力するものだ。

パーセプトロンのモデルを使いANDゲートを表現する

ANDゲートは、二つの入力値(x1, x2)を受け取り、どちらとも1であれば1を出力するものだ。 普通の関数としてANDゲートを表現する場合であれば、引数としてx1, x2を受け取り、if文でそれぞれの引数が1かどうかを判定し、出力するようにしてあげれば良い。しかし、今はパーセプトロンのお話をしているので、パーセプトロンのモデルを当てはめて考える。パーセプトロンの計算方法はb + w1*x1 + w2*x2であった。私たちが操作できるのは、重みとバイアスのみである。 よって、以下のように関数を定義できる。

上の関数で、ANDゲートを満たすように重みとバイアスを設定する必要がある。設定できる値は無限に存在するが、(w1, w2, b) = (0.5, 0.5, -0.7)と設定した時にANDゲートの条件を満たし出力してくれる。

つまり、パーセプトロンによるANDゲートの表現は以下のようになる。

どうように、ORとNAND(ANDの否定)も同じようにパーセプトロンで表現することができる。

パーセプトロンはモデルは一緒、パラメータが異なる

上記の例AND, NAND, ORでは、どれも同じモデルである。異なるのは重みやバイアスの値だけある。

パーセプトロンの限界

パーセプトロンは、パラメータを変えることで様々な演算を表現することができた。しかし、単一のパーセプトロンでは表現できないものも存在する。

その例としてXORがある。XORは2つの入力が異なった時に真を出力するものだ。

x1 x2 y
0 0 0
1 0 1
0 1 1
1 1 0

XORは、重みやバイアスをどのように設定しても表現することができない。これはXORが持つ、非線形という性質によるものである。

線形と非線形

AND, NAND, ORをxy軸平面上に書き起こした時(ANDであれば、x=1, y=1の座標は真、x=0, y=1の座標は偽)に、真(1)となる領域と偽(0)となる領域は、直線で分ける事ができる。こういった領域を線形な領域と呼ぶ。

一方で、XORをxy平面上に書き起こしてみると、真と偽の境界は直線で分けることができない。その代わりに曲線であれば分けることができる。このような領域を非線形な領域と呼ぶ。

つまり、単一のパーセプトロンでは非線形な領域を表現することはできない。

多層パーセプトロンによって非線形な領域を表現する

実は、単一のパーセプトロンでは非線形な領域は表現することはできないが、パーセプトロンを層のように重ねることで非線形な領域でも表現することが可能である。

具体的には以下のような実装となる。

入力として受け取ったx1, x2をそれぞれNANDとORで処理させ、それぞれの処理結果として受け取った出力s1, s2と置き、s1とs2を入力としてANDに処理させる。これによって最終的な出力結果はXORのものとなる。

多層パーセプトロンの可能性

これまでの例で非線形のような複雑な処理もパーセプトロンを組み合わせることで実現することができた。実は、多層パーセプトロンを用いることで、コンピュータを作れるほどの複雑な処理も表現することが可能である。

最後に

これまでは、パーセプトロンについて学んできた。次の章では、ニューラルネットワークという単語が登場するらしい。パーセプトロンニューラルネットワークの基礎となるらしいので、勉強を進めていきたいと思う。