13 Wed

TIL

[AI 스쿨 1기] 6주차 DAY 3

출처 : https://github.com/sujiny-tech/k-digital-training-AI-dev/blob/main/Machine-Learning-basics/Linear%20Models%20for%20Classification.md

선형 분류(Linear Classification)

• 분류 목표 : 입력벡터 x를 K개의 가능한 클래스 중 하나의 클래스로 할당

• 분류를 위한 결정이론

  • 확률적 모델(probabilistic model)

    • 생성모델(generative model)

      클래스의 사후확률 (using 베이즈 정리) 또는 직접 모델링

    • 식별모델(discriminative model)

      직접 모델링

  • 판별함수(discriminant model)

    확률 계산 없이 입력 x를 클래스로 할당하는 판별함수 구하기(찾기)

판별함수 (Discriminant model)

• 선형함수에 관한 판별함수에 대해 생각하자.

• 두개의 클래스에 대한 선형판별함수

  

  : wight vector

  : bias

  이면 클래스 1로 판별, <0이면 클래스 2로 판별

• 결정 경계(decision boundary)

  • y(x)=0을 만족하는 x의 집합 (x가 D차원의 입력벡터일 때, D-1차원의 hyperplane)

  • 결정 경계면 위

    

    → 즉, 는 결정경계면에 수직

  • 원점에서 결정 경계면까지의 거리

    • 벡터 x⊥ : 원점에서 결정 경계면에 대한 사영(projection)일 때 (아래 그림 참고)

      

      

      

      

      

      이면, 결정 경계면은 원점으로부터 w가 향하는 방향으로 멀어져있음.

      이면, 결정 경계면은 원점으로부터 w가 반대 방향으로 멀어져있음.

      즉, 는 결정 경계면 위치 결정❗

    • x⊥ : 임의의 한점 x의 결정 경계면에 대한 사영일 때

      y(x)는 x와 결정 경계면 사이의 부호화된 거리에 비례

      

      정리하면,

      

      이면, x는 결정 경계면 기준으로 w가 향하는 방향에 있음

      이면, x는 결정 경계면 기준으로 -w가 향하는 방향에 있음.

      의 절댓값이 클수록 더 멀리 떨어져있음.

      

    • (수식 단순화) 가짜입력 dummy input 이용

      • 

      • 

      • 

• 다수의 클래스에 대한 판별함수

  • 클래스 에 대해 표현하면 다음과 같음.

    

    일 때, 를 만족하면, x를 클래스 로 판별

분류를 위한 최소제곱법 (Least squares for classification)

• 사실 분류를 위해 최소제곱법 쓰는건 별로 좋지 x❗

• 클래스를 판별하는 판별식은 다음과 같음

  

  행렬 에 대해 나타내면,

  

  의 k번째 열 :

• 제곱합 에러 함수(sum-of-squared error function)

  • 학습 데이터 , , n번째항이 인 행렬 T, n번째 행이 인 행렬 이 주어졌을 때, 제곱합 에러함수는 다음과 같음.

  

  유도 과정은 다음과 같음.

  

  

  

  에 대해 미분하고 식 전개하면,

  ( : pseudo-inverse 행렬)

• 따라서 판별함수는 다음과 같음.

  

• 분류를 위한 최소제곱법의 문제점✨

  • outlier에 민감

  • 목표값의 확률분포에 대한 잘못된 가정에 기초❗

퍼셉트론 알고리즘 (The perceptron algorithm)

• 기저함수를 넣어 일반화된 식으로 표현하면 다음과 같음.

  

  여기서 이며, f는 활성함수(activation function)로 계단형 함수임

  

• 에러 함수

  

  : 잘못 분류된 데이터들의 집합

• Stochastic gradient descent의 적용하면,

  

• 위 업데이트가 실행될 때 잘못 분류된 샘플에 미치는 영향

  

⭐ 최소제곱법과 퍼셉트론 모두 output 출력하지만, 확률을 계산하진 않음❗

확률적 생성 모델 (Probabilistic Generative Models)

• 모델링 한 다음 → 클래스의 사후확률 을 구함❗ (using 베이즈 정리)

• 이전 판별함수에서는 에러함수를 최소화하는 최적의 파라미터를 찾는 것이 목적이지만, 확률적 모델은 데이터 분포를 모델링하면서 분류 문제를 결과적으로 풀게됨❗

• 2-class를 가정하고, x가 클래스 1(C1)에 속할 확률

  (a에 관한 logistic sigmoid function)

  

  • logistic sigmoid function

    

    

    sigmoid 함수-위키백과 참고

    • 성질

      • 대칭 :

      • 역(inverse) :

• 일반 선형 모델(generalized linear model) - 클래스가 k>2인 경우 (일반화)❗

  • (a에 관한 softmax function)

  • 

⭐ 2-class : logistic sigmoid function를 이용, k-class : softmax function를 이용❗

• 연속적 입력 (continuous inputs)

  • 가 가우시안 분포를 따르고, 모든 클래스에 대해 공분산이 동일하다고 가정하자.

  • 가정 하에 어떤 클래스가 주어졌다면, 해당 데이터를 output하는 확률은 다음과 같음.

    

  • 2-class에 대해서,

    

    이때, w벡터와 w0는 다음과 같음.

    

    a에 대한 전개

  • k-class에 대해서는 다음과 같이 확장 가능.

    • 

    • 

• 최대우도해 (Maximum likelihood solution)

  • 2-class의 경우

    • 데이터와 파라미터들

      • 실제 데이터 에 대해 이면 클래스 1로 분류하고, 은 클래스 2로 분류.

      • 라 할때, 구하고자하는 파라미터는 ❗

    • 우도함수

      • 각 클래스에 대해 다음과 같이 표현할수 있음

        

        p({\bf x}_n, C_2) = p(C_2)p({\bf x}_n|C_2) = (1-\pi) N({\bf x}_n;\mu_2, \Sigma)

        따라서,

        

      π 구하기μ 구하기∑ 구하기

데이터가 이산일 때 (Discrete features)

• 각 특성 이 0 또는 1, 하나의 값만 가질 수 있는 경우

  • 클래스가 주어졌을 때 특성들이 조건부 독립(conditional independence)이라는 가정을 할 경우 문제는 단순화됨! → naive Bayes 가정

    

    이때, 이며, 위 식을 k-class의 에 대입하면 다음과 같음.

    

    

    함수가 함수에 대해 선형인 것을 확인할 수 있음.

[Statistics 110]

Present Part [3 / 34]

3강- Birthday Problem과 확률의 특성 (Birthday Problem, Properties of Probability)

생일 문제 : 생일이 같은 두 명의 사람을 찾기

• 가정

  • 2월 29일은 제외한다

  • 365일이 모두 동일한 확률을 가진다

    • 실제로는 그렇지 않다. 예를 들어 9월에 출생이 많다.

    • 독립 : 한 사람의 생일이 다른 사람의 생일에 영향을 미치지 않는다.

최소한 몇명의 사람이 있어야 50%의 확률을 만족할까?

• 365개의 상자에 공을 최소한 하나씩 집어넣는 경우와 동일

• 사람이 366명일 경우는 확률이 1이다.

  • 이를 비둘기집 원리라고 한다

• 대부분의 사람들은 직관적으로 150~180명을 이야기하며 보통 100을 넘는다.

• 실제로는 23명이 있을 때 50.7%의 확률을 가진다

모두의 생일이 같지 않을 확률

• 이를 1에서 빼면 적어도 두 명이 생일이 같을 확률을 구하는 것과 같다

• P(no match) = $\frac {365 \cdot 364 \cdot \ \ \cdots \ \ \cdot (365 - k + 1)} {365^k}$ : 365개의 날짜 중 1명이 한 날짜를 차지하면 다른 1명은 남은 364개의 날짜 중 한 날짜를 차지하는 방법

• P(match)

  • 50.7% if k = 23

  • 97.0% if k = 50

  • 99.999% if k = 100

k에 대한 직관

• ${k \choose 2} = {k(k-1) \over 2}$

• ${23 \choose 2} = {23 \cdot 22 \over 2} = 253$

  • 23은 작은 수지만, 23명이 만들 수 있는 쌍의 수는 253개이며 충분히 적어도 한쌍이 생일이 같은지 비교할 수로는 작은 수는 아니다

• 생일이 같거나 하루 차이 날 확률

  • about 50% if k = 14

확률 정리

• 기본 정리

  • P($\varnothing$) = 0, P(S) = 1 and it also means $0 \le P(A) \le 1$

  • $P (\cup^\infty_{n=1}) = \sum^\infty_{n=1}P(A_n) \ \ \ \ if \ \ A_n \ \ is \ \ disjoint\ \ with \ \ A_m(m \not= n)$

• 속성

  • $P(A^c) = 1 - P(A)$

    • Proof

      • $1= P(S) = P(A \bigcup A^c) = P(A) + P(A^c) \ \ since A \bigcap A^c = \varnothing$

  • If $A \subseteq B$, then $P(A) \leq P(B)$

    • Proof

      • $B = A \bigcup (B \bigcap A^c)$, disjoint

      • $P(B) = P(A) \bigcup P(B \bigcap A^c)$

  • $P(A \bigcup B) = P(A) + P(B) - P(A \bigcap B)$

    • Proof

      • $P(A \bigcup B) = P(A \bigcup (B \bigcap A^c)) = P(A) + P(B \bigcap A^c) ?= P(A) + P(B) - P(A \bigcap B)$

      • $P(B) = P(A \bigcap B) + P(A^c \bigcap B)$ => True

      • since, $P(A \bigcap B), P(A^c \bigcap B)$are disjoint, union is B

    • 포함배제의 원리, inclusion-exclusion

  • $P(A_1 \bigcup A_2 \bigcup \cdots \bigcup A_n) = \sum_{i=1} ^n P(A_i) - \sum_{i \lt j} P(A_i \bigcap A_j) + \sum_{i \lt j \lt k} P(A_i \bigcap A_j \bigcap A_k) - \cdots + (-1)^{n+1}P(A_i \bigcap \cdots \bigcap A_n)$

몽모르트 문제 : 드 몽모르트가 만든 문제

• 도박에서 처음 나온 문제

• 1부터 n까지 적혀있고 각 수마다 한 장만 존재하는 카드 뭉치가 존재

• 카드를 셔플 후, 카드 뭉치에 있는 카드의 순서와 카드의 값이 일치하는 경우 승리

• 포함배제의 원리를 이용하여 푸는 것이 가장 쉽다

• $P(A_j) = {1 \over n}$, j카드가 j-th에 있을 확률, 이 때 j에 대한 식이 아니다

• $P(A_1 \bigcap A_2) = { (n-2)! \over n!} = {1 \over n(n-1)}$, n개의 카드 중 1과 2가 각각 첫번째와 두번째에 있어야 함

• $P(A_1 \bigcap \cdots \bigcap A_K) = { (n-k)! \over n!}$

• $P(A_1 \bigcup \cdots \bigcup A_K) = n \cdot {1 \over n} - {n(n-1) \over 2! }{1 \over n(n-1)} + { n(n-1)(n-2) \over 3! }{1 \over (n(n-1)(n-2)} - \cdots \\ = 1 - {1 \over 2!} + \cdots + (-1)^n {1 \over n!} = 1 - {1 \over e}$

• 테일러 급수와 비슷한 모양