Mathlife
Mathlife의 학습 노트
Mathlife
전체 방문자
오늘
어제
  • 분류 전체보기
    • CS
      • 알고리즘
      • 자료구조
      • 운영체제
      • 네트워크
      • 데이터베이스
    • 프로그래밍 언어
      • Java
      • JavaScript
      • C·C++
      • Python
    • Backend
      • Spring
    • Frontend
      • HTML
      • CSS
    • Math
      • Linear Algebra
      • Calculus
    • AI
      • ML
      • DL
      • RL
    • Git

블로그 메뉴

  • 홈
  • 관리
  • 글쓰기
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Mathlife

Mathlife의 학습 노트

AI/ML

Perceptron Convergence Theorem Proof

2022. 4. 22. 15:24

목표 vector $w^\star$, 현재 vector $w$ 라고 하자.

 

Data set {($(\mathbf{x_1}, y_1)$, ... , $(\mathbf{x_d}, y_d)$} 가 주어졌다고 하자.

 

WLOG, $||w^\star|| = 1$, $||\mathbf{x}|| \leq 1$ 이라고 하자.

( 모든 data에 $\mathbf{x_i} \leftarrow \mathbf{x_i} / max(\mathbf{x})$ 해도 같은 hyperplane 얻는다 )

 

WLOG, $w = 0$ 으로 시작한다고 하자.

 

$w^\star$의 정의에 따라 모든 $(\mathbf{x}, y)$에 대해 $y x^T w^\star > 0$이 성립한다.

 

Lemma : $y x^T w^\star \geq \gamma$

$\displaystyle \gamma = \min_{x}{|x^T w^\star|}$ 라고 하자. 

즉, $\gamma$는 목표 hyperplane으로부터의 minimal margin이다.

이 때, $y x^T w^\star = |x^T w^\star| \geq \gamma$ 가 성립한다. $\square$

 

어떤 $(x, y)$에 대해 $y x^T w\leq 0$이 성립하여 update가 이루어졌다고 하자.

 

1. $w_{new}^T w^\star = (w+yx)^T w^\star = w^Tw^\star + yx^Tw^\star \geq w^Tw^\star + \gamma$

 

2. $w_{new}^T w_{new} = (w+yx)^T (w+yx) = w^T w + 2yx^Tw + y^2x^Tx \leq w^Tw + 1$

 

 

 

이제 M번의 update가 이루어졌다고 해보자.

 

$M \gamma \leq w^T w^\star \leq ||w^T|| = \sqrt{w^T w} \leq \sqrt{M}$

 

$\therefore M \leq \frac{1}{\gamma^2}$

 

 

 

Update는 많아야 $\lfloor \frac{1}{\gamma^2} \rfloor$ 번 이루어진다.

'AI > ML' 카테고리의 다른 글

로지스틱 회귀  (0) 2022.05.11
    'AI/ML' 카테고리의 다른 글
    • 로지스틱 회귀
    Mathlife
    Mathlife

    티스토리툴바