MF-ALS(Alternating Least Squares, 교대 최소 제곱법)

기본 개념:
ALS는 행렬 분해를 위한 반복적인 최적화 방법입니다. SVD와 비슷하지만, 결측치(missing values)가 많은 추천 시스템에 더 적합해요.

실제 예시로 설명하겠습니다:

        영화1  영화2  영화3  영화4
사용자1   5     ?      3     4
사용자2   ?     2      5     ?
사용자3   4     1      ?     3

(여기서 ?는 평가하지 않은 영화입니다)

ALS의 목표:

• 사용자 행렬(U)과 아이템 행렬(V)을 찾아 R ≈ UV^T가 되도록 함
• 예: 2개의 잠재 요인을 사용한다면

사용자 행렬(U):            아이템 행렬(V):
[0.8  0.3]               [0.7  0.2]
[0.5  0.9]               [0.4  0.8]
[0.2  0.6]               [0.9  0.3]
                         [0.5  0.6]

작동 과정:

1. 초기화:

• 사용자 행렬(U)을 랜덤값으로 시작

2. 반복 과정:
   a) V 고정, U 업데이트:

• 각 사용자별로 평가한 영화들만 사용
• 예: 사용자1의 경우
  • 실제 평점: [5, 3, 4]
  • 최소제곱법으로 최적의 잠재 요인 찾기

b) U 고정, V 업데이트:

• 각 영화별로 평가한 사용자들만 사용
• 예: 영화1의 경우
  • 실제 평점: [5, 4]
  • 최소제곱법으로 최적의 잠재 요인 찾기

실제 계산 예시:
사용자1의 잠재 요인 업데이트:
1. 현재 평가한 영화들의 V 행:

영화1: [0.7  0.2]
영화3: [0.9  0.3]
영화4: [0.5  0.6]

2. 실제 평점: [5, 3, 4]

3. 최소제곱법으로 풀기:

• [x1 x2][0.7 0.9 0.5] ≈ [5][0.2 0.3 0.6] [3][4]

장점:
1. 결측치 처리가 자연스러움
2. 병렬 처리 가능
3. 새로운 사용자/아이템 추가가 쉬움

단점:
1. 하이퍼파라미터(잠재 요인 수 등) 설정 필요
2. 수렴까지 여러 번 반복 필요

실제 적용:

• Netflix Prize 대회에서 성공적으로 사용
• 유튜브 추천 시스템의 초기 버전에서 활용
• 아마존의 상품 추천에도 응용

이해하기 쉽게 비유하면:

• 두 명이 번갈아가면서 퍼즐을 맞추는 것과 같아요
• 한 명이 사용자 특성을, 다른 한 명이 아이템 특성을 담당
• 서로의 결과를 보면서 더 나은 해답을 찾아가는 과정

---

사용 이유

1. 결측치 처리가 자연스러움

실제 평점 데이터:
        어벤져스  타이타닉  매트릭스
Alice     5         ?        3     
Bob       ?         2        5     
Carol     4         1        ?     

• 일반적인 SVD는 결측치(?)가 있으면 계산이 어려움
• ALS는 있는 데이터만 사용해서 최적화
• 넷플릭스처럼 대부분의 영화를 보지 않은 상황에서 유용

2. 병렬 처리가 쉬움

사용자 잠재 요인 업데이트 시:
Alice: [평점: 5, 3] → [잠재요인: 0.8, 0.3] 
Bob: [평점: 2, 5] → [잠재요인: 0.5, 0.9]
Carol: [평점: 4, 1] → [잠재요인: 0.2, 0.6]

• 각 사용자의 계산이 독립적
• 여러 컴퓨터에서 동시에 처리 가능
• 큰 규모의 데이터 처리에 적합

3. 수학적으로 볼록 최적화

• U를 고정하고 V를 최적화할 때
• V를 고정하고 U를 최적화할 때
• 각각은 단순한 최소제곱법 문제가 됨

예: U 고정 시 V 최적화
min Σ(실제 평점 - UV^T)²

4. 새로운 사용자/아이템 추가가 쉬움

새로운 영화 '인셉션' 추가 시:
1. 기존 U는 그대로 유지
2. 인셉션의 V 값만 계산
3. 전체 재계산 불필요

5. 메모리 효율적

• 원본 평점 행렬: 100만 사용자 × 10만 영화
• 잠재 요인(50개 사용): 100만×50 + 10만×50
• 크기가 크게 감소

실제 사례:

• Netflix Prize 대회에서 우수한 성능
• YouTube 초기 추천 시스템
• Spotify 음악 추천
• Amazon 상품 추천

SGD와 비교했을 때 ALS의 장점:

SGD:
- 하이퍼파라미터 조정이 어려움
- 수렴 속도가 불안정할 수 있음

ALS:
- 파라미터 조정이 비교적 쉬움
- 안정적인 수렴
- 병렬화가 자연스러움

이러한 이유로 대규모 추천 시스템에서 ALS는 여전히 중요한 방법으로 사용되고 있습니다.

---

ALS의 convex 특성

SGD와 비교했을 때의 ALS의 convex 특성을 설명해드릴게요.

1. MF 문제의 기본 형태:

min Σ(Rij - Ui·Vj^T)²

이 문제는 U와 V에 대해 동시에 볼 때는 non-convex예요.

2. 하지만 ALS에서는:

a) U 고정하고 V에 대해 최적화:
   min Σ(Rij - (고정된 Ui)·Vj^T)²
   
b) V 고정하고 U에 대해 최적화:
   min Σ(Rij - Ui·(고정된 Vj^T))²

각각의 단계는 convex 문제가 됩니다!

예시로 보면:

R =    [5  ?  3]
       [?  2  5]
       [4  1  ?]

1) U를 고정했다고 하면:
U = [[0.8  0.3],
     [0.5  0.9],
     [0.2  0.6]]

2) V를 찾는 문제는 각 영화별로:
영화1: [0.8]   [v11]   [5]
      [0.5] × [v12] ≈ [4]
      [0.2]

이건 단순한 최소제곱법 문제로 변환되어 명확한 해를 구할 수 있어요.

SGD의 경우:

• U, V를 동시에 업데이트
• non-convex 문제를 그대로 다룸
• 지역 최적해에 더 민감
• 학습률(learning rate) 설정이 까다로움

그래서:
1. ALS는 각 단계가 convex → 안정적인 수렴
2. SGD는 전체가 non-convex → 수렴이 불안정할 수 있음

하지만! ALS도 전체적으로는 여전히 non-convex예요. 단지 각 단계별로 convex한 것뿐입니다.