A Regression Modeling View of Neighborhood Methods
이전 포스트에서 말했었던 중요한 관점은 바로 user-based method와 item-based method 둘 다 predict ratings하는데 있어서 linear functions로 보는 것 이었습니다.
이 챕터에서는 Neighborhood Methods를 Regression model로서 생각해보겠습니다.
위의 식은 앞의 user-based neighborhood methods의 prediction function입니다. (Eq 2.4)
이 식은 other ratings의 weighted linear combination으로 볼 수 있습니다. 그래서 linear regression 형태와 유사함을 알 수 있습니다. 하지만 linear regression의 경우와 달리 neighborhood based approach에서는 linear function의 coefficients가 heuristic한 방법으로 정해집니다.
item-based의 경우에도 비슷합니다.
user-based model의 경우에는 predicted rating을 동일한 column(item을 기준으로 user간의 유사도를 구함)의 ratings에 대한 linear combination으로 표현한 반면에 item-based의 경우에는 row를 기준으로 합니다.
이러한 view를 기반으로 neighborhood-based models를 heuristic variants of linear regression models라고 할 수 있습니다.
위에서 Linear Regression에서의 view로서의 Neighborhood-based methods를 봤는데, 그럼 최적화 문제에 있어서 어떤 공식이 잘 돌아갈지에 대해 궁금증이 생깁니다. 이에 대해서는 추후에 다시 다루니 넘어가겠습니다.
User-Based Nearest Neighbor Regression
User-based nearest neightbor regression에 대해 알아보겠습니다. 이에 대한 formulation은 위와 같은데, User-based prediction의 공식(Eq2.20)에서 Similarity에 대한 부분을 weight로 변경했습니다.
neighborhood-based models에서는 \(P_u(j)\)를 item j에 대해 rating한 k명의 neighborhoods의 set으로 지정했습니다. 이 때 neighborhoods의 수는 정확하게 k명이 됩니다.
하지만 user-based nearest neighbor regression에서는 \(P_u(j)\)에 대해 우선 k closest peers를 지정하고 이 중에서 item j 에 대해 rating한 peer만 고려합니다. 그래서 이 때의 \(P_u(j)\)의 size는 significantly less than k 입니다.
Optimization problem의 형태로 식을 지정하면 위와 같습니다.
원서에서는 이에 대해 least square 형태로 지정했습니다.
objective function \(J_u\)에 대해서는 different target users의 경우도 한번에 고려할 수 있기 때문에, 위의 식은 disjoint 되어 있는 상태입니다.
합쳐진 objective function은 아래와 같습니다.
물론 smaller optimization problems(disjoint)으로, 더 효율적이고 전체에 대해서 변화없는 결과를 도출 할 수 있습니다. 하지만 다른 기법들과 조합하여 사용하려면 합쳐진 objective function을 사용해야합니다.
만약 standalone basis로 사용하게 된다면 decompose된 form을 사용합니다.
Sparsity and Bias Issues
Regression approach에서 \(P_u(j)\)의 수는 동일한 user u와 다양한 item j에 대해 굉장히 다를 수 있습니다.
(ratings matrices가 굉장히 sparse하기 때문.) 이러한 이유로 적은 수의 peer user를 가지고 있는 item에 대해서 편향이 크게 일어날 수 있습니다.
이를 완화시키기 위해서는 특정 target user u의 특정 item j에 대한 Peer group의 크기를 고려해주면 됩니다.
이에 대한 방법들은 아래와 같습니다.
Eq 2.25에서 Constant factors를 optimization process에서 학습 가능한 bias variable로 바꿔줬습니다.
여기에서는 두 variables가 곱해지기 때문에 더 이상 linear 라고는 볼 수 없지만 여전히 least square를 사용하기 쉽습니다.
Eq 2.26에서는 user bias 뿐만 아니라 item bias까지 추가했습니다.
Item-Based Nearest Neighbor Regression
Item-Based Nearest Neighbor Regression에서는 앞 포스트의 Eq2.21에서 정규화 된 AdjustedCosine(j,t) 계수를 unknown parameter \(w^item_{jt}\)로 변경 했습니다.
위의 user-based nearest neighbor regression과 같이 traditional neighborhood의 \(Q_t(u)\)와 size가 다릅니다.
traditional neighborhood의 경우에는 \(Q_t(u)\)의 size가 정확히 k개 이지만 user-based nearest neighbor regression의 경우에는 k개 보다 작습니다.
직관적으로 unknown coefficient w^item_{jt}\)는 item j의 similarity에 대한 것이기 때문에 item t의 rating (prediction)에 있어서 영향을 끼칩니다. 그래서 이를 user-based neareset neighbor regression때와 같이 least square의 형태로 표현 할 수 있습니다.
Least square 형식으로 위와같이 objective function을 정의 할 수 있습니다.
하지만 이 형태는 disjoint된 형태이고 아래와 같이 consolidated formulation으로 나타낼 수 있습니다.
다른 technique과의 combine 할 때는 consolicated formulation form이어야 합니다.
Sparsity and Bias Issues에서 봤듯이 여기에서도 bias variables와 normalization factors를 적용 할 수 있습니다.
그리고 이 때 ratings는 entire matrix의 global mean에 대해 centered 되어있다고 가정합니다.
이러한 least-squares optimization model은 계산되고, gradient descent approach로 optimization parameters에 대해 해결 할 수 있습니다.
그리고 user and item based 경우 둘 다 regularization을 적용 할 수 있습니다.
Combining User-Based and Item-Based Methods
similar users 뿐만 아니라 similar items도 고려해줘서 이에 대한 관계를 기반으로 rating을 predict 할 수 있습니다.
이전의 경우와 동일하게 ratings matrix는 global mean에 대해 centered 되어있다고 가정합니다.
이 경우 또한 gradient descent approach가 적용 될 수 있습니다.
Joint Interpolation with Similarity Weighting
원서의 Reference [72]에서는 joint neighborhood-based model을 사용합니다.
이에 대한 Basic idea는 target user u에 대한 각각의 rating predict를 target user u에 대한 observed ratings를 다른 items와 비교하는 것 입니다.
위의 식에서 set S는 item j가 아닌 비슷한 item s의 set 입니다. 그래서 위의 식에서 AdustedCosine(j,s)를 사용하여 similar를 고려해줬습니다.
이 경우에도 물론 Regularization을 고려하여 overfitting을 줄이는 것이 가능합니다.
이를 통해 similar items의 target user's ratings를 더 similar하게 만들 수 있습니다.
이 방법은 user와 item similarity 모두 적용이 가능한데, 다른 방법으로 적용 가능합니다.
item-item similarity을 objective function에 multiplicative factors로서 사용합니다. 이는 similar items에 대한 observed ratings와 더 similar하게 예측할 수 있게 합니다.
user-user similarity에서는 regression coefficients를 target user u의 peer group \(P_j(u)\)로 제한하여 ratings를 predict하는데 사용하게 합니다.
Sparse Linear Models (SLIM)
Item-based nearest neighbor regression에서의 item-item regression은 sparse linear models(SLIM)로 여겨집니다. 이런 모델들은 regularization methods를 이용해서 sparsity를 이겨낼 수 있습니다.
이 경우 non negative rating values로 돌아가는데, matrix는 mean centered라고 가정하지 않습니다.
그리고 dislike가 없는 환경에 대해 design 되었기 때문에 implicit 한 경우에 어울립니다. 또한 unary 처럼 missing values를 0으로 여깁니다.
하지만 optimization model에서의 결과는 매우 높은 양수로 예측 될 수 있습니다. 그래서 특정한 값을 rating하기보다는 rank를 정해야 합니다.
이 식에서는 Item-based nearest neighbor regression과 다르게 target item t의 neighborhoods로 국한시키지 않습니다. 그리고 overfitting을 막기 위해 target item을 제외시킵니다. (\(w^item_{tt}=0\))
모든 items에 대해서 target일 경우를 고려하기 때문에 \(Diagonal(W^{item})=0\)이 됩니다.
그리고 target item t( \(\forall t \in {1 ... n}\) )와 나머지 모든 item j간의 관계에 대한 weight matrix를 \(W^{item}\) (n by n matrix)라 했을때 모든 rating prediction은 위의 첫번째 식이 됩니다. (output = m by n matrix)
여기에서의 main goal은 몇몇 regularization terms를 동반한 Frobenius norm \(||R-RW^{item}||\)을 최소화 시키는 것입니다.
이는 W의 다른 columns에 대해 분해될 수 있습니다. 즉 독립적으로 각 optimization problem을 solve 할 수 있음을 의미합니다.
Eq 2.33에서 \(\hat r_{ut}\)로 각각 user에 대해 예측했듯이..
columns에 대해 분해된 식은 아래와 같습니다.
여기에서 more interpretable sum-of-parts regression을 만들기 위해, weight vectors가 non-negative라고 제한합니다.
위의 식에서는 regularization으로 elastic net regularization이 사용되었습니다.
optimization problem은 Coordinate descent method로 해결 가능합니다.
SLIM에는 여러 특징들이 있습니다.
- feature selection에서 learning approach를 적용함.
- SLIM은 implicit feedback data를 위해 디자인 되었음.
- SLIM의 regression coefficient는 non-negative로 제한됨. 이는 더 직관적이고 설명을 쉽게 해줌.
- SLIM은 ranking을 사용함.
- SLIM은 varing number of specified ratings에 대해 heuristic adjustment factor를 적용하지 않음. (Eq 2.29 참고)
Graph Models for Neighborhood-Based Methods
이 부분은 graph 방식에 대해 overview하는 느낌입니다.
neighborhood-based methods에서 sparsity는 유사도 계산에 있어서 주된 문제 입니다.
graph를 사용하면 다양한 users and/or items 간의 관계에 대한 structural representation을 provide 할 수 있고, 이에는 다양한 graph의 형태가 존재합니다.
User-Item Graphs
user-item graph에서는 neighborhoods를 정의하는데 구조적인 measures를 사용 할 수 있습니다. 그리고 edge의 구조적 transitivity를 사용 할 수 있어서 sparse ratings matrices에 대해 더 효과적입니다.
user-item graph는 \(G=(N_u\cup N_i, A)\)로 구성되며, \(N_u\)는 users의 노드에 대한 set이고, \(N_i\)는 items의 노드에 대한 set이며, \(A\)는 두 노드 사이를 잇는 edges로 이루어진 set입니다.
여기에서 graph는 undirect하고 bipartite한 edge로 구성 되어 있으며 A에서의 edge의 수는 utility matrix에서 observed entries 수와 같습니다. 이에 대해서는 Fig2.3에 나와 있습니다.
graph에서의 주된 장점은 neighborhoods의 construction을 nodes간의 indirect connectivity를 통해 정의 될 수 있기 때문에, 두 user가 많은 동일한 items를 rate할 필요가 없다는 것 입니다.
graph representation에서는 neighborhoods를 지정하는 여러 방법들이 존재합니다.
Defining Neighborhoods with Random Walks
user의 neighborhood는 random walk에서 자주 마주친 users의 set으로 이루어 집니다.
여기에서 random walk를 통해 자주 마주치는 건 Chapter 10에 자세히 나와 있습니다.
이 방법은 item-based CF에 유용합니다.
earson Correlation의 경우에는 직접적으로 연결된 경우만 고려햇는데, sparse user-item graphs에서는 connectivity가 많은 nodes에서 존재하지 않기 때문에 sparsity에 대해 문제가 생겼었습니다. random walk가 sparse matrices에 대해 효과적인 이유는 바로 어떤 node에서 다른 노드로 가는 walk를 어떤 단계에서도 적용 가능하기 때문입니다. (indirect)
따라서 user-item graph에서 큰 부분이 연결되어 있는 한 의미있게 neighborhoods를 define하는게 가능합니다.
Defining Neighborhoods with the Katz Measure
위의 random walks 방법은 probablistic measure이었는데, weighted number of walks를 통해 유사성을 정하는 방법도 존재합니다.
이때 각 walk의 weight는 (0,1)의 범위를 갖는 discount factor 입니다. walks가 많을수록 discount 하도록..
만약 두 users가 walk-based connectivity를 기반으로 동일한 neighborhood에 속해있다면, 두 users는 user-item graph에서 연결되려고 하는 경향이 있을 것 입니다.
이제 그러한 성향을 the number of walks(discounted factor)를 통해 측정 됩니다.
Definition Katz Measure
Katz measure는 위와 같은 식으로 측정 됩니다. i와 j는 특정 nodes를 가리키고, t는 walks의 length를 의미합니다. n은 length 가 t인 walks의 수 입니다.
이 식에서는 walks가 길수록 de-emphasize 하게 됩니다.
위의 식에서 A는 그래프의 인접행렬이고 K는 Katz Coefficient에 대한 m x m 행렬입니다.
Katz Coefficient 행렬은 위와 같습니다.
