[CS229] [16] Lecture 16 - Independent Component Analysis & RL

1. Independent Component Analysis(ICA)

- ICA에 대해서 알아볼 건데, PCA와 비슷하게, 이는 데이터를 표현할 basis를 찾는 과정이지만, 하지만 object가 다르다.

- motivation으로 "cocktail party effect"를 생각해보자.

-n명의 사람들이 동시에 파티에서 이야기하고 있으며, 방에 있는 마이크로 각 사람들의 목소리가 섞인 신호만 기록한다고 하자.

- 방엔 서로 다른 거리에 있는 n개의 마이크가 있는데,

- 각 마이크는 사람들과의 거리 차이로 인해 각기 다른 사람들의 음성을 혼합한 신호를 받는다.

- 이러한 음성 데이터를 n명의 사람들의 음성을 분리할 수 있을까?

 

- 우선 이 문제를 해결하기 위해 s ㅌ R^n을 만족하는 n개의 independent한 벡터가 있다고 가정하자.

- 여기서 A는 mixing matrix라고 불리는 square matrix이다.

- x는 관찰을 통해 얻은 n개의 혼합된 음성이고, s는 개개인의 음성 데이터를 의미하게 된다.

- 우리의 목표는 이러한 s를 복구하는 것이다.

- 이는 간단하게 A의 inverse matrix구해 s를 구할 수 있다. 여기서 W = A^-1 이라고 정의해보자.(unmixing matrix)

- 이를 통해, j번째 사람의 음성은 다음과 같이 얻어낼 수 있다.

1.1. ICA ambiguities

- 그러면, W을 어느 정도 까지 얻어 낼 수 있을까?

- mixing matrix에 대한 정보가 없다면, x_i만 가지곤 복구하는데 힘들 것이다.

- 예를 들어, P를 n x n permutation matrix라고 가정해보자.(각 행 열이 하나의 1만 가짐)

- 만약 z가 벡터라면, Pz는 z의 좌표를 permutation한 다른 벡터가 될 것이다.

- 즉, x_i만 가지고 W,PW를 구별할 순 없다라는 것이다.

- 이는 곧, ICA에서 signal의 순서가 뒤섞이는 경우를 구분 못한다는 것이다.

- 즉, (A,B,C)나 (B,C,A) 나 (C,A,B)나 같은 데이터로 간주한다는 것이다.

- 하지만, 대부분의 application에선 순서가 바뀌는 것은 큰 문제가 되지 않는다.

 

- 또한, ICA는 signal의 scale을 복구 할 수 없다.

- 예를 들어, mixing matrix가 2배로 커지고, signal이 절반으로 줄어들어도

- 관찰된 데이터 x = As는 동일하다.

- 하지만, 음성 데이터에선 scale은 단지 볼륨만 달라지고, 원래 음성 신호는 그대로 유지된다.

- 음성의 부호(양수/음수)가 바뀌어도 듣는 데는 차이가 없다.

- 그래서, scale이나 부호가 바뀌더라도 applicaiton에선 무시 가능하다.

 

- 이러한 ICA는 signal data가 non-Gaussian일 때만 제대로 작동한다.

- 만약 signal이 Gaussian distribution을 따른다면, 

- distribution의 contour은 평균을 중심으로 회전대칭적이다.

- 즉, 데이터가 어떤 방향으로 회전하더라도 분포가 변하지 않는다는 것이다.

 

- 우리가 관찰하는 데이터 x = As에서, mixing matrix A를 통해 데이터가 혼합된다.

- 이 데이터 x 역시, Gaussian distribution을 따르며, 평균은 0이되고 공분산은 다음과 같아진다.

- mixing matrix A에 임의의 rotation matrix R을 곱해 A' = AR를 만든다고 가정하자.

- 그러면 x' = A's의 공분산을 구해보면,

- 즉, 구분을 할 수 없게 된다는 것이다.

 

- 따라서, ICA는 s_i가 non-Gaussian일때 원래의 independent signal을 복구 할 수 있다.

 

1.2. Densities and Linear Transformations

- ICA을 본격적으로 설명하기 전에, Linear transformation이 확률 밀도 함수에 어떤 영향을 미치는지 간단히 알아보자.

- 확률 밀도 함수의 면적의 크기가 1이 되야 하기에, random variable를 linear transformation을 하게 되면,

- 그 확률 밀도 함수의 면적의 크기가 달라지기에 보정을 해주어야 한다.

- s = Wx 라고 할 때,

- p_x(x) = p_s(Wx) 가 아니라, p_x(x) = p_s(Wx)|W| 가 된다.

 

1.3. ICA Algorithms

- 이제 ICA를 유도해보자.

- 우리는 MLE을 통해 진행해나갈것이다.

- 각 signal s는 P_s(s)를 따른다.

- signal s의 joint distribution을 구해보면 다음과 같다.(각 signal은 Independent하다고 가정한다.)

 

- 여기서 1.2에서 다룬 내용으로 식을 변형해주면 다음과 같다.

 

- 여기서 signal s의 density를 정의하기 위해서 CDF을 지정해야 하는데,

- CDF는 0에서 1까지 단조 증가하는 함수여야 한다.

- 그래서 Sigmoid function을 CDF로 지정해보자.

- 따라서, p_s(s) = g'(s)를 만족하게 된다.

- 이를 토대로 MLE를 진

행하면 다음과 같다.

- 해당 log likelihood를 maximization 하기 위해, Gradient Ascent를 이용하면 다음과 같이 update된다.

 

2. Reinforcement Learning

- RL은 간단하게, 모든 Step에서 올바른 답을 말하라고 요구하지 않는 알고리즘이다.

- 우리같은 엔지니어들이 할 일은 모델이 잘 할떄와 못할 때를 알려주는 reward function를 지정해줘야 한다.

- 즉, 모델이 일을 잘 동작할 때마다 높은 reward를 주는 reward function을 작성해야 하고,

- 반대면 낮은 reward를 주는 reward function을 작성해야한다.

- 만일 체스 ai를 만든다고 생각해보자, 이 ai가 만약 50수에서 져서, -1 이라는 reward를 받는다고 생각해보자.

- 근데, ai가 지게 된 요인이 49수일까? 30수때부터 잘못둬서 뒷 일이 전부 꼬일 수 도 있다.

- 즉, 어떤 순간부터 불리하게 작용하였는지를 알아야 적절한 reward를 취해줄 수 있다는 것이다.

- 이를 Credit assignment problem이라고 한다.

 

2.1. MDP(Markov Decision Process)

- Reinforcement Learning은 보통 MDP로 문제를 해결해나간다고 한다.

- 그럼 MDP는 무엇일까?

- MDP는 5개의 tuple로 이루어져 있다.

i) S : set of State (ex, 모든 가능한 체스 위치의 집합, 헬리콥터의 조정 가능한 위치의 집합..)

ii) A : set of actions (ex, 체스 게임에서 할 수 있는 모든 움직임의 집합..)

iii) {P_sa} : state transition probabilities(특정 행동 a와 특정 상태 s를 취할 때,특정 다른 상태의 최적 상태에 도달할 확률)

iv) gamma : discount factor [0,1)

v) R : Reward function

 

- MDP의 동작은 다음과 같이 진행된다.

i) 초기 상태 s_0에서 시작한다.

ii) 상태 s_0에서 a_0 ㅌ A 라는 행동을 선택한다.

iii) 이 행동의 결과로 MDP는 P_(s_0a_0)에 따라 무작위로 다음 상태 s_1로 전이된다.

iv) 이후, 상태 s_1에서 새로운 행동 a_1 ㅌ A를 선택한다. 이를 계속 반복한다.

- 이를 도식화 하면 다음과 같다.

 

- MDP에서 payoff는 다음과 같이 계산된다.(마치 이자와 비슷한 느낌)

- 이러한 discount factor는 결국 payoff가 수렴하도록 만들어주는 역할을 하게 된다.

- RL의 목적은 해당하는 payoff의 Expectation을 Maximization하는 행동을 step에 따라 선택하는 것이다.

- 대부분의 RL에서는 state -> action으로 mapping 시키는 policy를 정의한다. (ex, 날씨가 흐림(s) --> 우산을 챙김(a))

 

- 그 다음 내용부터 Lecture 17로 이어진다.