# Introduction

Here is the article I wrote last time class.

# Network and Flow

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 (最大フロー最小カットの定理)

・(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.

# 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

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

# 問題

C: Go Home - AtCoder Beginner Contest 056 | AtCoder

# 解法

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

0(0) →１(1) →３(2) →６(3) →１０(4) →１５(5)

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

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

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

#### 等差数列の和の公式

sum = (項の数 * (初項 + 末項) / 2) = (t * (t + 1)) / 2

# 問題

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

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

# 解法

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

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

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

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

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なので間に合う。

# 問題

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

# 解法

#### 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))となり、この問題を解くことができる。

# Introduction

Here is the article of the last time class.

# Matrix Expression of Graphs and Paths

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.

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

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 お勉強 #2】パーセプトロンを実装してみよう - マツシタケイタの技術ブログ(勉強中)

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

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

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

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

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

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

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

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

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

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

# 活性化関数

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

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

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

# 活性化関数は種類がある

#### ステップ関数

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

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

#### シグモイド関数

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

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

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

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

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

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

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

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

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

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

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

# 出力層の設計

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

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

#### ソフトマックス関数

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

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

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

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

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

# 最後に

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

# はじめに

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

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

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

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

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

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

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

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

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

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

# パーセプトロンの限界

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

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

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)となる領域は、直線で分ける事ができる。こういった領域を線形な領域と呼ぶ。

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

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

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

# 最後に

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