link / excerpt > CHAPTER 4. A visual proof that neural nets can compute any function by Michael Nielsen

[input:100 node, output:100 nodeでの関数近似をNeural networkに学習させようとしている](http://qiita.com/7of9/items/7394f4326a88500a67b9)。
関連するキーワードとして「function approximation」が挙げられる。

見つけたのが以下。
http://neuralnetworksanddeeplearning.com/chap4.html

以下、自分が興味を持った部分の[抜粋(Excerpt)](http://ejje.weblio.jp/content/%E6%8A%9C%E7%B2%8B)と補足考察。

### universality

> This result holds even if the function has many inputs, f=f(x1,…,xm), and many outputs. 

...

> This result tells us that neural networks have a kind of universality. No matter what function we want to compute, we know that there is a neural network which can do the job.

どんな関数であろうとも、それを再現するNeural networkがある、とのこと。

> What's more, this universality theorem holds even if we restrict our networks to have just a single layer intermediate between the input and the output neurons

hidden layerが単層でもこのuniversalityを持つとのこと。[蒸留](http://qiita.com/HirofumiYashima/items/fc220b66d16b2d2078c4)の結果得られるネットワークでもextremely powerfulとも関連するかもしれない(私見)。

universalityについては、quite technicalな説明はあったとのこと (以下)。 

> For instance, one of the original papers proving the result* did so using the Hahn-Banach theorem, the Riesz Representation theorem, and some Fourier analysis.

色々な過程は関数計算と考えられる（以下)。

> Almost any process you can imagine can be thought of as function computation. Consider the problem of naming a piece of music based on a short sample of the piece. 

...

> Or consider the problem of translating a Chinese text into English. 


...

> Universality means that, in principle, neural networks can do all these things and many more.

...

> This limitation applies also to traditional universality theorems for models such as Boolean circuits.

真理値表の学習なども可能。
[167,926個の学習](http://qiita.com/7of9/items/6fa9552340041ee534d9)もおそらく可能(と自分を奮い立たせる)。

### Two caveats

http://ejje.weblio.jp/content/caveat
> 手続き差し止め通告、警告、注意

...

> two caveats to the informal statement "a neural network can compute any function".

1つ目のcaveatは以下。

> First, this doesn't mean that a network can be used to exactly compute any function. Rather, we can get an approximation that is as good as we want. 

...

> by using enough hidden neurons we can always find a neural network whose output g(x)g(x) satisfies |g(x)−f(x)|<ϵ, for all inputs x. 

希望精度$\epsilon$までの近似はhidden neuronを増やしていくことで達成できる。

2つ目のcaveatは以下。

> The second caveat is that the class of functions which can be approximated in the way described are the continuous functions.

連続関数でないと近似できない。
Step functionのような場合、[Gibbs phenomenon](https://en.wikipedia.org/wiki/Gibbs_phenomenon)のようになるのだろうか。

...

> However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough.  ... In practice, this is not usually an important limitation.

...

> Summing up, a more precise statement of the universality theorem is that neural networks with a single hidden layer can be used to approximate any continuous function to any desired precision.

...

> In the diagram below, click on the weight, ww, and drag the mouse a little ways to the right to increase w.

どういう仕掛けかわからないが、weightとbiasを変更しながらその出力関数を見ることができて面白い。

> You'll see that as the bias increases the graph moves to the left, but its shape doesn't change.

...
>  You'll see that as you decrease the weight, the curve broadens out.

...
> Finally, increase the weight up past w=100. As you do, the curve gets steeper, until eventually it begins to look like a step function. 

...
> It's actually quite a bit easier to work with step functions than general sigmoid functions.

...
> And so it makes things much easier to assume that our hidden neurons are outputting step functions. 

sigmod functionでなくstep functionであると仮定して考察している。

> the position of the step is proportional to b, and inversely proportional to w.
> In fact, the step is at position s=−b/w

step functionの値が変化する部分(パラメータs)について考察している。wとbによる出力関数のグラフからsによる出力関数のグラフを閲覧者が確認できるようにしている。

> Up to now we've been focusing on the output from just the top hidden neuron. Let's take a look at the behavior of the entire network.

hidden layerの1つのneuronの操作から、hidden layerの全部のneuronのs値と、weightの操作による出力変化を見ることができる。

> What's being plotted on the right is the weighted output w1a1+w2a2 from the hidden layer. ... These outputs are denoted with aas because they're often known as the neurons' activations.

...

> Finally, try setting w1 to be 0.8 and w2 to be −0.8. You get a "bump" function

bump function: グラフの途中でstep upして、その後step downするような形。

> We can use our bump-making trick to get two bumps, by gluing two pairs of hidden neurons together into the same network:

hidden neuronsを増やしていくことで、bumpの数も増やしていくことができる。そしてそれは関数の近似に貢献していくという感じ。


> Contrariwise, try clicking on the graph, and dragging up or down to change the height of any of the bump functions. 

グラフ自体を操作することで、h値の変化を見ることもできる。

> What's output from the network is σ(∑jwjaj+b) where bb is the bias on the output neuron. Is there some way we can achieve control over the actual output from the network?

> The solution is to design a neural network whose hidden layer has a weighted output given by σ−1∘f(x), where σ−1 is just the inverse of the σσ function.

σ−1は$\sigma^{-1}$。(リンク元ページではきちんと表示されている。こちらではlatex表記で書きなおす時間省略のため手抜き)。

> How well you're doing is measured by the average deviation between the goal function and the function the network is actually computing.

グラフにてbumpsを操作して、実際のAverage deviation値を見ることができる。

> It's only a coarse approximation, but we could easily do much better, merely by increasing the number of pairs of hidden neurons, allowing more bumps.

hidden neuronsのペア数を増やすことで、精度を高められる。

> We could have used this procedure for any continuous function from [0,1] to [0,1].

~~範囲について[0,1]の制約があるのかは未消化。~~
(sigmoid function前提の話のためのようだ)

### Many input variables

> So let's address the two-input case.

2入力の場合に拡張している。

> The difference is that now the step function is in three dimensions. 

2つのinput neuronsになった場合、2次元(x,y)方向それぞれのstep functionを操作するようなことになると図示されている。

> We can use the step functions we've just constructed to compute a three-dimensional bump function. 

bump functionもx,y軸それぞれになり、tower functionになる（以下）。

> What we've built looks a little like a tower function:

...

> then we could use them to approximate arbitrary functions, just by adding up many towers of different heights, and in different locations:

...

> Let's try gluing two such networks together, in order to compute two different tower functions. 

tower function自体を複数持つことも可能。

> In particular, you can see that by modifying the weights in the final layer you can change the height of the output towers.

...

> What about functions of more than two variables?

...

> **By gluing together many such networks we can get as many towers as we want, and so approximate an arbitrary function of three variables. Exactly the same idea works in mm dimensions. The only change needed is to make the output bias (−m+1/2)h, in order to get the right kind of sandwiching behavior to level the plateau.**

(-m + 1/2)hの制約については未消化。

### Problem

single hidden layerで任意の関数を近似することを提案している。

> to approximate a tower function which is circular in shape

input neuronの数を増やすことで、rectangular in shapeから circular in shapeになるということだろう。

### Extension beyond sigmoid neurons

これまでの議論はsigmoid functionに基づいていた。別の関数を使うとどうかというと

> and ultimately it becomes a very good approximation to a step function. 

...

> What properties does s(z)s(z) need to satisfy in order for this to work? We do need to assume that s(z)s(z) is well-defined as z→−∞ and z→∞. ... We also need to assume that these limits are different from one another. 

### Problems

> Earlier in the book we met another type of neuron known as a rectified linear unit. Explain why such neurons don't satisfy the conditions just given for universality.

ReLUはuniversalityの条件を満たさないとのことらしい。


### Fixing up the step functions

> Up to now, we've been assuming that our neurons can produce step functions exactly. 

...

> a narrow window of failure, 

完全なstep functionではなく、値が急峻に変化する部分にa narrow window of failureがある。

> Now, it's not a terrible failure. By making the weights input to the neurons big enough we can make these windows of failure as small as we like. 

...

>  points in a failure window for one approximation won't be in a failure window for the other.

step functionを複数使ってoverlapさせた場合、1つのfunctionのfailure windowは他のもののfailure windowにならない、などのため影響は小さいと著者は見ているようだ (以下)。

> We could do even better by adding up a large number, MM, of overlapping approximations to the function σ−1∘f(x)/M.


### Conclusion

> So the right question to ask is not whether any particular function is computable, but rather what's a good way to compute the function.

...

> Given this, you might wonder why we would ever be interested in deep networks, i.e., networks with many hidden layers. Can't we simply replace those networks with shallow, single hidden layer networks?

...

> In later chapters, we'll see evidence suggesting that deep networks do a better job than shallow networks at learning such hierarchies of knowledge.