Move Fast

데이터 간 유사도

- 모든 데이터는 벡터로 표현 가능

- 일반적으로 내적을 이용해서 데이터간 유사도를 측정

- 내적을 쓰는 이유: 각도를 이용하는데, 예를 들어 0도면 서로 같고 180도면 서로 다르다. 이를 위해 cosin 각도가 활용되므로 내적을 사용하는 것

- 데이터는 많은 것도 문제가 되나 차원(데이터 테이블의 컬럼)이 높은 것도 분석에 문제가 된다. 차원이 높을 수록 내적에 시간이 많이 걸린다.

고차원 데이터 처리하기

- Locality Sensitive Hashing: 비슷한 데이터를 확률적으로 높게 같은 bucket 에 있게하는 방법으로, 기존의 해쉬기법과 달리 비슷한 데이터끼리는 같거나 가까운 bucket 에 둔다는 점에서 차이가 있다.

- Clustering: 비슷한 데이터끼리 군집화 (서로 다른 클러스터는 서로 다른 데이터라고 볼 수 있다.)

- Dimensionality Reduction: 유사도 측정에 관련 없는 데이터를 제거하는 방법

예시: A와 B를 구매한 고객 X 가 있을 때, 고객 Y 가 A를 구매할 경우 B 를 추천하는 경우 여기서 데이터는 고객 X 로부터 수집된 것이다.

필터링의 필요성

- 웹 상에서는 제품에 대해 거의 제로 비용으로 정보를 제공한다.

- 선택지가 많은 것은 사람에게 복잡함을 주기 때문에 추천 시스템으로 필터를 해줄 필요가 있다.

- Long Tail: 주목받지 못하는 아이템이 그래프 상에서 표현된 모양을 일컫는 용어

가로 축은 등수이고, 세로 축은 인기도일 때 실제 상품이 많아 등수 축은 훨씬 긴 범위를 가지는 반면 인기도 축은 훨씬 짧은 범위를 가진다. 따라서, 상품이 많아 주목받지 못하는 아이템이 주목받는 아이템보다 훨씬 많다. 적분 시 위 그림의 노란색 부분이 더 크다.

추천 유형

- Editorial and hand curated: 전문가의 평가로 추천하는 시스템. (ex: 좋아하는 것의 목록, 필수 아이템 목록)

- Simple aggregates: 대중에게 인기 있는 것을 추천. (ex: 탑 10, 가장 인기있는 것, 최근 업로드한 것)

- Tailored to individual users: 각 개인에게 특화된 추천 - Personalized Recommendation - (ex: 아마존, 넷플릭스, … 등)

공식적인 모델

- Utility function: X가 S를 대상으로 매기는 등급, u: X x S → R

• X = set of Customers
• S = set of Items (추천 대상)
• R = set of ratings (예시: 평점)

- R 는 전체적으로 순서있는 집합이다.

유틸리티 행렬(Utility Matrix)

- 일반적으로 sparse matrix (빈칸이 많음) 라서, 연산을 용이하게 하기 위해 빈 셀에 값을 유추해서 저장해놓는다.

핵심 문제

- 행렬에 대해 알려진 등급(ratings)들을 모은다.

• Explicit Feedback: 명확한 유저의 의견을 반영하는 방식 (예시: 평점) → 실제로 잘 동작X
• Implicit Feedback: 암시적인 의견을 반영하는 방식 (예시: 물건 구매/장바구니 행위 자체)

- 알려진 사람(ones)들로부터 모르는 등급(ratings)들을 유추한다. 주로 모르는 등급들에 관심이 많다. 이미 알려져 있는 것에는 흥미가 없다.

- Utility Matrix U is Sparse → 대부분 사람들은 많은 아이템에 평점을 남기지 않는다.

- Cold Start: 어떤 데이터도 없이 시작하는 것 (ex: 새로 개봉한 영화, 새로 가입한 사용자)

- 추천 시스템에 대한 3가지 접근법

• Content-based: 아이템 내용을 기반으로 추천
• Collaborative: 여러 대상을 이용해서 필터링
• Latent factor based: 확실하지 않으나 존재하는 기준이나 카테고리 또는 요소를 이용(잠재 변수 기반)

- 유추하는 방식을 평가 = 추천 방식의 성능과 성공을 평가

컨텐츠 기반 추천 시스템(Content-based Recommendations)

- 주 아이디어: 고객 X에 의해 높게 등급이 매겨진 이전 아이템들과 유사한 아이템을 고객 X에게 추천

• 예시1: 이전 영화에 나온 배우, 디렉터가 출연한 영화 또는 장르가 유사한 영화 추천
• 예시2: 웹사이트, 블로그, 뉴스에서 유사한 컨텐츠를 가진 다른 사이트 추천

- Plan of Action

- 아이템 프로필(Item Profiles): 각 아이템에 대해 프로필을 생성

profile  = set (vector) of features

• 예시1: 영화 - author, title, actor, director, …
• 예시2: 텍스트 - 문서에서 중요한 단어들의 집합

- 예시 2에서 중요한 특징(feature)을 선택하는 방법

• 보통 텍스트마이닝에서는 TF-IDF 를 사용 (단어 빈도 수 / 단어가 나온 문서 빈도 수)
• TF-IDF = Term frequency / Doc Frequency
• Term -> Feature
• Document -> Item

• f : 문서 j에서 단어 i가 사용된 횟수, max f : 문서 j에서 가장 많이 사용된 단어의 사용 횟수
• TFij = f / max f : 문서 j에서 단어 i의 빈도 수
• ni : 단어 i를 사용한 문서의 개수, N : 전체 문서의 개수
• IDFi = log(N/ni) : 단어 i를 사용한 문서의 빈도 수
• Doc Profile = TF-IDF 가 가장 높은 단어들의 집합

- 사용자 프로필(User Profile)

• 등급을 준 아이템 프로필들의 평균에 가중치한 것
• 분산(Variation): 아이템들의 평균 등급의 차이에 의한 가중치

- 예측 귀납(Prediction heuristic): 사용자 프로필 x 와 아이템 프로필 i 가 주어졌을 때, u(x, i) = cos(x, i) 이다. 여기서 cosin 은 방향이 중요함을 의미한다. 얼마나 좋아하는지가 아닌 좋아하는 그 자체(방향성)에 의미를 둔다.

- 장점

1. 다른 사용자에 대한 데이터를 필요로 하지 않는다. (No cold-start or sparsity problems)

2. 독특한 취향을 가진 사용자에게 추천할 수 있다. (일반적이지 못한 사용자들)

3. 새롭거나 인기가 없는 아이템을 추천할 수 있다. (No first-rater problem)

4. 설명을 제공할 수 있다. (추천된 아이템의 내용적인 특징을 리스팅하는 것)

- 단점

1. 유사도에 필요한 특징(feature)을 선택하기 힘들다. (이미지, 영화, 음악 등)

2. 새로운 유저에게 추천하는 것이 힘들다. (사용자 프로필을 만드는 법에서 막힘)

3. 너무 특화된 것들만 추천할 수 있다. (Overspecialization) 예를 들어, 사용자의 컨텐츠 프로필 외의 아이템을 추천하지 않거나, 다양한 흥미를 가진 사람들이 있을 수 있는데 하나만 추천하는 경우가 해당된다. 다른 사용자의 질적 판단을 이용하지 않는다.

협업 필터링(Collaborative Filtering)

[User-user collaborative filtering]

- 사용자를 고려하는 방식으로, 취향이 비슷한 집단에서 누군가 선호한 아이템을 아직 접하지 않았다면 고객에게 그 아이템을 추천

- N = 고객 x의 등급 부여 방식(ratings)과 유사한 방식(ratings)을 가진 다른 사용자의 집합

- 집단 N 에서 사용자들의 등급 부여 방식을 기반으로, 고객 x가 매긴 등급을 측정(유추)

- 유사한 사용자를 찾는 법 (데이터간 유사도 측정 방식)

• rx = 고객 x의 아이템별 등급(ratings)을 원소로 갖는 벡터

• 자카르드 유사도 측정법(Jaccard similarity measure): 교집합 크기 / 합집합 크기
  • 문제: 특정 등급을 무시할 수 있다.

• 코사인 유사도 측정법(Cosine similarity measure): cos(rx, ry) = rx*ry / (|rx|*|ry|)
  • 두 유저의 rating vector 를 내적한 결과를 벡터의 길이의 곱들로 나눔. 단, 여기서 평가되지 않은 경우는 0점을 주어 계산
  • 문제: 누락된 등급을 음수로 표현할 수 있다.

• 피어슨 상관 계수 (Pearson correlation coefficient)
  • Sxy = 고객 x와 y 모두에 의해 등급이 매겨진 아이템들 (추가 이론은 위키피디아 참고)

- 유사도 측정 항목(Similarity Metric)

• 직관적으로 봤을 때 원하는 것: sim(A,B) > sim(A,C)
• 자카르드 유사도: ⅕ < ½ 
  • A와 B의 합집합 크기(총 컬럼 개수 5개, HP1, HP2, HP3, TW, SW1)는 5, 교집합 크기는 1
  • A와 C의 합집합 크기(총 컬럼 개수 4개, HP1, TW, SW1, SW2)는 4, 교집합 크기는 2
• 코사인 유사도: 0.386 > 0.322 → 빈 칸(0)을 처리하지 못해서 A와 C의 반대 성향을 잡지못함
• 해결책: 빈 등급을 음수값으로 맞춰놓고, 행의 평균을 빼고 코사인 유사도를 측정하면 피어슨 상관 계수와 동일한 결과를 낸다.
  • 0.092 > -0.559

A행의 평균은 10/3 이다.

- 등급 예측(Rating Predictions) → 유사도 측정 항목을 어떻게 활용하는가?

• rx = 고객 x의 등급들의 벡터
• N = 아이템 i를 등급매겼던 고객 x와 대부분 유사한 k명의 고객들의 집합
• rxi = 고객 x가 아이템 i에 매긴 등급 = 특정 집단(N)이 아이템 i에 준 점수들의 평균

[Item-Item collaborative filtering]

- 아이템은 고객(user)들의 등급으로 표현된다. 벡터의 각 원소가 각 유저가 매긴 등급(rating)

- 알고리즘

1. 아이템 i와 유사한 다른 아이템들을 찾는다.

2. 유사한 아이템에 대한 등급을 기반으로 아이템 i에 대한 등급을 평가한다.

3. 동일한 유사도 측정 항목과 user-user 모델에서와 같이 예측 함수를 사용할 수 있다.

- rxj = 고객 x가 평가한 아이템 j의 등급

- Sij = 아이템 i와 j의 유사도

- N(i;x) = 아이템 i와 유사한 고객 x에 의해 평가된 아이템들의 집합 (음수인 유사도는 제외)

위의 식으로 아이템 i의 등급을 예측 (다른 고객의 정보가 필요없음)

고객 5가 등급을 매긴 영화들 중 1번 영화와 유사한 영화들을 탐색한 다음,

등급이 없는 영화에 대해 점수를 몇 점 줄 것인지 예측, 왼쪽 sim(1, m)는 1번 영화와 m번째 영화와의 유사도

- CF: Common Practice

• 아이템 i와 j의 유사도 Sij 를 정의
• k개의 가장 가까운 이웃 선택
• N(i; x) = 고객 x에 의해 등급이 매겨진 아이템 i와 가장 유사한 아이템들
• 가중치된 평균으로 등급 rxi를 측정

• b: bias로, 유저별 개인차 또는 아이템별 개인차를 의미한다.
• u: 전체 등급의 평균

[비교 분석: Item-Item vs User-User]

- 실제로, item-item이 user-user보다 협업 필터링이 더 잘 동작하는 것으로 관찰되어왔다.

- 그 이유는 사용자가 아이템보다 개인차가 더 크기 때문이다.

[협업 필터링 장단점]

- 장점: 어떤 종류의 아이템이든지 잘 동작한다. 특징을 선택할 필요가 없다. (No feature selection, only rating vector)

- 단점:

1. Cold Start: 시스템에서 맞출만한 충분한 고객들이 필요하다.

2. Sparsity: 사용자 또는 등급 행렬 (user/ratings matrix)는 대부분 비어있다. 동일한 아이템을 등급을 매긴 고객을 찾기가 힘들다.

3. First rater: 이전에 등급이 매겨지지 않은 아이템을 추천할 수 없다. (새로운 아이템이나 독특한 아이템들)

4. Popularity bias: 인기 있는 아이템만 추천하는 경향이 있다. 독특한 취향을 가진 누군가에게 추천할 수 없다.

- 하이브리드 방법: 둘 이상의 다른 추천을 구현하거나 예측을 결합하는 방법으로, 보통 선형 모델을 사용한다.

예시: 컨텐츠 기반에 협업 필터링을 추가한 방법: 새로운 고객이나 아이템에 대해서(cold start) 프로필을 활용하고 그 외는 협업 필터링을 이용하는 방식 

Remarks & Practical Tips

- 평가(Evaluation): 알려진 등급들을 가지고 예측한 것을 비교한다. (Dataset, Testset 분리)

Root-mean-square error (RMSE)

Precision at top 10 - 퍼센트로 상위 10개만 뽑기

Rank Correlation - 랭크의 유사도 (시스템과 고객의 완전한 랭킹 사이의 스피어맨 상관 관계)

- 또 다른 접근법: 0/1 모델

• Coverage: 얼마나 추천가능한가, 예측할 수 있는 시스템에서 아이템과 사용자의 수
• Precision: 예측의 정확도
• Receiver operating characteristic (ROC): false positive 와 false negative 사이의 Tradeoff 곡선 → 의학영역에서 많이 사용

- 오류 측정 항목(Error metrics)

• 문제: 정확도에 대한 초점이 강할수록 요점을 놓칠 때가 있다.
  • Prediction Diversity: 예측 다양성
  • Prediction Context: 예측 상황
  • Order of predictions: 예측 순서

- 실제로, 높은 등급을 예측하기 위해 주의해야만 한다. RMSE 는 높은 등급에 대해서는 잘 동작하나 아닌 것들에 대해서는 안좋게 동작하는 방법에 불리할 수 있다.

- 복잡도/속도(Complexity/Speed): k명의 가장 유사한 고객들을 찾는 것은 비용이 비싸다. 런타임 상에 수행하기에는 미리 계산해야 함.

- 해결책: 고차원에서 가장 가까운 이웃을 탐색하는 방법 (LSH), 클러스터링, 차원 축소

- 팁

• 변덕스러운 알고리즘이 잘 동작하려는 노력때문에 데이터 크기를 줄이려고는 하지 말 것
• 큰 데이터에 대해서는 단순한 방법이 최고다.
• 데이터를 더 추가하는 것 → 더 많은 데이터가 더 나은 알고리즘을 이기기도 한다. (추천 성능 측면에서만)

잠재 요인 모델(Latent Factor Models)

- Latent Factor: 중요한데 존재하지 않는 카테고리(잠재 변수)

• 예시: 넷플릭스 - 100 만개의 등급(ratings), 2000 ~ 2005 년간의 데이터, 평가 기준 = RMSE

- 로컬 & 전역 효과 모델링 (Modeling local & global effects)

• 전역 효과 예시: 평균 영화 등급이 3.7이고, 식스센스의 평점이 평균 보다 0.5 점 높을 때, Joe는 평균 보다 0.2점을 더 낮게 평가한다면, 식스센스는 4점(=3.7+0.5-0.2)일 것이다. 
• 로컬 효과 예시: local neighborhood (CF/NN) 에서는 Joe 는 영화 Signs 과 비슷한 걸 좋아하지 않는다. → 최종적으로 Joe 는 평점을 3.8점 줄 것이다. (두 영화가 유사하기 때문에 이전의 안좋은 평가를 반영하여 다음 영화의 점수를 예측)

- 협업 필터링(CF): 나온지 꽤 되었고 가장 인기있는 협업 필터링 방법

1. Item-Item 방법으로, 유사한 영화들의 등급으로부터 모르는 등급을 도출

2. 아이템 i와 j의 유사도 Sij 를 정의

3. k개의 가장 가까운 이웃을 선택, 그리고 등급을 계산

• N(i; x) = 고객 x에 의해 등급이 매겨졌던 아이템 i와 가장 유사한 아이템 집합
• rxj = 아이템 j에 대해 고객 x가 매긴 등급

그러나 실제로 bias 를 추가하여 아래와 같이 계산

Problems/Issues 2번은 고객 간의 공통성을 놓치고 있다는 의미

해결책은 RMSE 를 최대한 낮춰주는 경우의 가중치 Wij가 가장 좋다.

- Interpolation Weight Wij

• 가중치된 평균보다 가중치된 합을 사용 (아이템 i와 그것의 이웃 j 사이의 관계)

• 표기법
  • N(i; x) = 영화 i와 유사한 고객 x에 의해 등급이 매겨진 영화들의 집합
  • Wij = interpolation weight
  • 가중치 모델은 고객 x에 의존적이지 않으며, 영화 쌍(pairs) 사이에서 상호작용하는 것
  • 오류 측정 항목: 학습 데이터에서 SSE를 최소화하는 가중치 찾기

• 가중치 설정
  • Wij 는 영화 i를 평가했던 모든 다른 고객과 고객 x를 기반으로 학습되거나 측정된다.

- 최적화를 통한 추천

• 목표는 좋은 추천 기능을 하는 것 → RMSE 사용 → 낮을 수록 더 나은 추천
• 고객이 보지 못한 아이템에 대해 추천을 하는 것 → 실제로는 어려움
• 알려진 등급(user, item)에 대해 잘 작동하도록 시스템을 구축하는 것 → 모르는 등급을 잘 예측할 수 있다.
  • 목표 함수(objective function) 정의 → 최적화 문제를 해결
  • 학습 데이터에서 SSE를 최소화하는 가중치 찾기, 가중치를 벡터로 생각하자

• 함수 최소화하는 단순한 방법
  • 어떤 점 y 에서 시작 → 미분 계산
  • 그래프에서 움직이는 방향은 미분의 반대 방향

    

  • 미분 값이 0인, 최저점 도달(converged)할 때까지 반복
  • 기울기가 작을 수록 움직이는 간격이 작아야 한다. 안그러면 값이 그래프를 벗어날 수 있음

object function 을 가중치 Wij 로 미분해서 미분값이 0이 되는 가중치를 탐색

그러나 실제 w를 찾기는 어려우므로 이전 W와의 차이가 0인 새로운 W를 탐색

- 가중치는 유사도를 사용하지 않음. 둘은 다르다. 유사도는 명시적으로 이웃 아이템들 사이에 내부 관계에 대해 설명하는 것

- Latent Factor Models → Singular Value Decomposition

• SVD: 다시 곱해도 원래대로 (노란 부분을 원복) 잘 나오도록 벡터를 분해하는 것
• 가정: 노란 부분을 잘 원복하면 흰색도 원복이 된다.
• factor는 많을수록 정확하게 맞출 수 있으나, overfitting 이 발생할 수 있다. 이는 예측 실패율을 높인다.
• 위의 경우 등급 행렬(rating matrix R)을 Q*Pt 의 곱으로 근사할 수 있다.
• Factor들의 곱으로 등급매기기(Ratings)
  • 아이템 i에 대해 고객 x의 등급이 없으면 어떻게 측정하는가?

Q의 2번째 행과 Pt의 5번째 열을 내적

엔트리가 없을 때는 SVD는 정의되지 않는다. 행렬 P, Q를 찾기 위한 구체적인 방법을 사용해야 한다.

(그냥 SVD는 동작X) → 엔트리가 있는 값들(not missing data)만 가지고 오류의 최솟값을 찾는다.