Basics of Neural Network

• Keyword: Computational-Learning

• Related Papers
  Computational Learning Theory
  Deep Learning and the Information Bottleneck Principle

Deep Learning Fundamentals

What is Deep Learning?

• Optimization algorithm for complex function ==complex== function
  • 우리가 알아내고자 하는 함수이며, 이가 실제 현실에서 매우 복잡하게 생길 수 있기에 DL의 존재 가치가 있음.
• Deep? → MLP(Multi Layer Perceptron) :
  • 특징을 추출하는 층이 다층 구조라. (보통 3층 이상의 구조를 깊다고 표현)
• predict(forward pass), back-propagation(backward pass)의 과정을 반복 수행.
  • 이 과정에서 Loss 값을 이용해서 함수를 fitting하는 거지.
• 최종 목적은 우리가 알아내고자 하는 함수를 근사하는 것.

그렇다면 왜 이걸 사용하는 걸까? 어떠한 강점이 있나?

• 1. Solid performance(탁월하다)
     e.g. Image classification task - MNIST
     

  Acc of various models
  

• 2. Good adaptable(이식성이 좋다)
  • 전통적 방식은 특징을 추출하고 이를 분류하는 과정으로 진행되었지만, DL의 경우, 특징 추출이 ML 대비 크게 중요하지 않다. 그 과정조차 신경망이 알아서 학습할 거다.
• 3. Highly customizable in design
  • 건드릴 수 있는 부분이 많다.

Why Deep Learning Model is Good?

DL is good for generalization

• 우리의 최종적인 목표는 모델이 패턴을 잘 학습해서, 학습시키지 않은 것들에 대해 올바른 예측을 수행하는 것이다.

==즉, 일반화가 되지 않는 모델들은 정확도가 아무리 높아봐야 의미가 없다.==

Questions

• What makes learning generalize well?
• Can traditional theories explain generalizations?
• What is difference between a model that learns well and a model does not?

Traditional Computation Learning Theory

모델의 complexity가 증가할수록 Train Error Rate은 줄어들 수 있지만, Test Error Rate은 높아지는 경향이 있다.(Trade-Off)

• 모델의 복잡도가 올라가면, 더 복잡한(고차원) 함수로 피팅한다는 말이고, 복잡한 함수일수록 모든 데이터 포인트 하나하나 맞출 수 있다.(High Variance) → 훈련 오류율이 낮은 이유
• 반면, 이렇게 지나치게 고차원 함수로 피팅한다면, 모델은 ==훈련 데이터만 잘 설명할 수 있고, 그 주변은 설명할 수 없다. → 즉, 일반성을 잃는다.== → 테스트 오류율이 높은 이유.

💡

bias-variance trade-off가 과연 deep learning의 오류율도 잘 설명할 수 있을까?

Rademacher Complexity

• 모델의 일반화 성능을 표현하기 위한 하나의 지표
• DL 이전의 traditional 한 방법론들에서 주로 이야기되었음.
• 주어진 ==함수 집합(function class)이 random noise에 얼마나 잘 fitting될 수 있는지== 나타내는 지표
  • 즉, ‘아무 의미 없는’ 패턴도 얼마나 잘 학습할 수 있는지.

${\mathfrak{R}}_s(\mathcal{F})={\mathbb{E}}_{\sigma }[{\sup }_{f\in \mathcal{F}}\frac{1}{m}{\sum }_{i=1}^m{\sigma }_{i}f(x_i)]$

• 여기서 $\mathcal{F}$는 model function space

• $f$는 trained model

• ${\sigma }_i$는 independent 이고 uniform하게 1 또는 -1 의 값을 가지는 Rademacher random variable
  즉, $P({\sigma }_i=1)=P({\sigma }_i=-1)=1/2$

• ${\mathbb{E}}_{\sigma }[\cdot ]$는 모든 가능한 $\sigma =({\sigma }_1,\dots ,{\sigma }_n)$ 시퀀스에 대한 expected value를 의미.

• ${\sup }_{f\in \mathcal{F}}\frac{1}{n}{\sum }_{i=1}^n{\sigma }_{i}f(x_i)$는 함수 집합 $\mathcal{F}$ 내에서, random하게 1 또는 -1이 부여된 데이터 포인트 $x_i$에 대해 가장 강한 correlation를 보이는 함수 $f$를 찾는 것

• Concept:

  • model complexity 혹은 ==expressive power==를 측정한다.
    • R-complexity가 높다는 건 더 복잡한 함수를 fitting할 수 있어 noise까지도 학습 가능함을 말한다.
  • generalization performance
    • generalized error의 ==upper bound==를 추정할 수 있게 해줌.

Vapnik-Chervonenkis Dimension inequality

${ϵ}_{TestError}\le {ϵ}_{TrainError}+\sqrt{\frac{h\text{log}(n)+\text{log}(1/\delta )}{n}}$
이걸 식 변형해보면,

${ϵ}_{TestError}-{ϵ}_{TrainError}\le \sqrt{\frac{h\text{log}(n)+\text{log}(1/\delta )}{n}}$

에러 간 upper bound를 추정할 수 있음.

• VC-dimension:
  binary classification problem에 대한 hypothesis class의 capacity를 측정하는 지표.

  • 위 식에서 $h\text{log}(n)$
  • 어떤 가설 $\mathcal{H}$ 가 ==‘흩뜨릴(shatter)’== 수 있는 max data point 수.
    • $\mathcal{H}$: 학습시키고자 하는 모델.(NN, LM 등)
    • shattering: 주어진 m 데이터 포인트 중 $\mathcal{H}$ 에 속하는 함수를 사용하여 그 m개의 포인트에 가능한 모든 $2^m$가지의 이진 라벨링(binary labeling)을 정확하게 구현할 수 있다면, 우리는 이 m개의 포인트를 $\mathcal{H}$가 ‘흩뜨릴 수 있다’고 말한다.
  • VC 차원이 높다는 것은 가설 집합이 더 복잡하고 유연하다는 의미. 즉, 더 다양한 패턴을 학습할 수 있으며, 이는 훈련 데이터에 대한 피팅(fitting) 능력이 뛰어나다는 것을 의미하기도 합니다. 그러나 동시에, 너무 높은 VC 차원은 과적합(overfitting)의 위험을 증가시킴.
  • 마찬가지로 전통적 방법에서 중요하게 다루어졌음.

• reliability: $\text{log}(1/\sigma )$

• Capacity = VC-dimension + reliability

그렇다면 DL도 이러한 속성을 보일까?

Learning with Random Label

• (a)에서는 실제 데이터셋의 label을 조작한 거다.
  • true: 원본 dataset 그대로 학습시킨거고,
  • random은 label끼리 섞은거지
  • pixel을 조작한 건 random noise를 뿌린거고
  • 결과는 보는대로 random label이 loss

Information Bottleneck Principle

Basic Model Short Summary