개인화 추천 시스템의 머신러닝을 위한 음수 미포함 행렬 분해와 변수 선택 기법의 비교

Ⅰ. 서 론

개인화 추천을 위한 머신러닝 모델의 베이스라인으로 널리 쓰이는 협업 필터링(Collaborative Filtering)[1]은 행렬 분해 기법에 그 기초를 두고 있다. 이론적으로는 특이값 분해(singular value decomposition)에 기반하고 있지만, 특이값 분해는 병렬화가 어렵고 큰 데이터에서 잘 동작하지 않는 성능적인 문제가 있기 때문에 실제적으로는 행렬을 두 개로 분할하는 음수 미포함 행렬 분해(nonnegative matrix factorization)[2]과 같은 기법을 사용하는 경우가 많다[3], [4].

행렬 분해를 통해 얻어진 사용자(user) 벡터 또는 품목(item) 벡터는 여러 가지 형태로 사용될 수 있는데, 가장 흔하게 사용되는 방식은 근접 이웃(nearest neighbor) 방법을 통해 사용자가 선호한 품목과 가까운 품목을 LSH(locality sensitive hashing)와 같은 방법으로 찾아 추천의 후보군으로 삼는 것이다[5]-[7]. 이 경우에 한 가지 가정이 깔려있는데, 그것은 원래 계획 행렬(design matrix)에서 유사한 벡터가 행렬 분해 후에도 유사하게, 유사하지 않은 벡터는 행렬 분해 후에도 유사하지 않게 유지되리라는 것이다. 유사도의 측정은 보통 코사인 유사도[8]를 통해 이루어진다. 코사인 유사도가 보존되는 것이 바람직한 성질이라고 전제할 때, 음수 비포함 행렬 분해가 이와 같은 성질을 가지는지, 어느 정도까지 유사도를 보존하는지에 대한 검증이 필요함에도, 실제 머신러닝 모델을 만드는 과정에서 이와 같은 가정이 철저히 검증되지 않는 경우가 많다.

또한 음수 비포함 행렬 분해는 알고리즘의 병렬화가 가능하긴 하지만, 그럼에도 불구하고 데이터 크기나 분해할 행렬의 계수(rank)가 커지면 모형 생성에 매우 오랜 시간이 걸린다. 그리고 새로운 데이터가 들어오게 되면 처음부터 다시 훈련을 해서 모형을 생성해야 하는 문제를 가지고 있어서, 끊임없이 새롭게 들어오는 데이터를 빠른 시간 내에 반영해야 하는 서비스 환경에서 적용시에 모형 생성에 필요한 시간만큼 반영이 지연되는 결과를 낳는다.

본 논문에서는 음수 비포함 행렬 분해에 관한 위와 같은 가정들을 실험을 통해 검증하고자 한다. 또한 분산과 엔트로피에 의한 변수 선택이 음수 비포함 행렬 분해보다 좋은 시간 복잡도를 가지면서도, 분해할 행렬의 차원에 따라서는 음수 비포함 행렬 분해보다 코사인 유사도 보존 측면에서 낫다는 것을 보이고자 한다. 이를 통해 머신러닝 모델에서 근접 이웃 방법에 사용될 사용자 또는 품목 벡터를 생성하기 위해 검토 없이 무조건 음수 비포함 행렬 분해를 사용하는 것이 아니라, 상황에 따라 더 나은 방법을 사용하도록 제안하고자 한다.

본 논문은 2장에서 음수 미포함 행렬 분해에 대해 기술하고, 3장에서 변수 선택 기법과 음수 미포함 행렬 분해를 코사인 유사도 보존 측면과 시간 복잡도 측면에서 비교한 후, 4장에서 결론을 맺는다.

Ⅱ. 음수 미포함 행렬 분해

음수 미포함 행렬 분해는 주어진 행렬을 분해된 두 행렬의 모든 원소가 0보다 같거나 크다는 조건을 만족하면서 원래 행렬을 근사하는 두 행렬의 곱으로 분해하는 것으로, 행렬 A ∈ R^{m × n}를 계수 r인 두 행렬 U ∈ R^{m × r}, V ∈ R^{r × n}로 분해한다고 할 때 목적함수는 식 (1)과 같이 표현된다.

개인화 추천을 위한 머신러닝에서 특이값 분해 대신 음수 미포함 행렬 분해가 선호되는 이유 중 첫 번째는 모든 잠재 요인(latent factor)이 양수로 표현되기 때문에 해석이 쉽기 때문이다. 그러나 그보다 더 중요한 이유가 있는데, 음수 미포함 행렬 분해는 특이값 분해에 비해 훨씬 희소한(sparse) 행렬을 만들어내는 경향이 있기 때문이다. 이것은 분해의 해를 찾는 과정에서, 모든 원소가 0보다 같거나 커야 한다는 제약 조건 부근을 탐색하게 되면서 제약 조건에 걸려 많은 원소가 0으로 정해지기 때문이다[9]. 희소한 행렬은 메모리를 덜 차지하면서 서비스 시에 계산할 양도 줄어들기 때문에 실용적으로 큰 장점이라고 할 수 있다.

음수 미포함 행렬 분해는 위와 같은 장점을 가지지만, 대신에 몇 가지 문제를 가지고 있다. 첫 번째로, 다항식 시간에 계산이 가능한 특이값 분해와는 달리, 정확한 음수 미포함 행렬 분해는 NP-Hard 문제이다[10]. 이 때문에 실제로는 다항식 시간에 지역 해를 찾는 휴리스틱 방법을 사용하게 된다. 휴리스틱 방법에는 곱셈적 갱신(multiplicative updates)[2], ALS(alternating least squares)[11]-[13], 투영 기울기(projected gradient) 기법[14], 뉴튼(Newton) 기법[15], [16] 등이 있다. 휴리스틱 방법을 사용하는 경우의 시간 복잡도는 계획 행렬 A ∈ R^{m × n}을 계수 r로 분해할 경우 O((mn)^2rr2)로 알려졌다가[17], O((mn)^r2)로 개선되었다[18], [19].

휴리스틱 방법을 사용할 경우 시간 복잡도 문제는 어느 정도 해결이 되며, ALS와 같은 경우는 병렬처리가 가능한 알고리즘이기 때문에, 대용량의 클러스터를 사용하여 병렬 처리하게 되면 시간을 더 줄일 수 있다. 그러나 휴리스틱 방법을 사용하는 경우에는 분해된 행렬이 결정적이지 않고, 매번 랜덤하게 다르게 분해되기 때문에 해석이 매번 달라지는 문제가 있고, 서비스에 사용할 경우 일관적이지 않은 결과를 주게 된다. 또한 모든 원소가 0보다 커야 한다는 제약 조건 때문에 주어진 행렬과의 오차가 특이값 분해보다는 항상 더 크다는 것도 단점이다.

음수 미포함 행렬 분해에 대한 연구는 주로 식 (1)을 효율적으로 풀기 위한 것으로, 음수 미포함 행렬 분해가 분해 대상이 되는 계획 행렬의 데이터 포인트 사이의 코사인 유사도를 얼마나 보존하는지에 대한 연구는 찾기 어려웠다. 본 논문에서는 분해한 행렬이 근접 이웃 방법에 사용될 임베딩이라고 가정하고, 코사인 유사도 보존 측면에서 다른 방법과 비교를 수행하고자 한다.

Ⅲ. 음수 비포함 행렬 분해와 변수 선택 기법의 비교

본 연구에서는 음수 비포함 행렬 분해와 논문에서 제시하는 분산 및 엔트로피에 기반한 변수 선택 기법을 코사인 유사도 보존과 수행 시간 측면에서 비교하였다. 차원 축소의 아이디어는 정보가 담기는 공간의 크기를 줄이면서도 그 안에 담기는 정보를 최대화하는 것이라고 할 수 있는데, 이를 위한 가장 간단한 방법은 계획 행렬에서 정보의 양이 가장 많은 열만 남기는 변수 선택이다. 계획 행렬의 열이 담고 있는 정보의 양을 측정하는 방법으로 첫 번째는 분산을 사용할 수 있고, 두 번째는 엔트로피 역시 그 후보가 될 수 있다. 식 (2)의 계획 행렬 A ∈ R^{m × n}를 계수 r로 차원을 줄이는 경우, 분산이 가장 큰 열의 집합 X를 선택하여 남기는 방법은 식 (3)과 같이 정의될 수 있다. c_ij는 A의 i번째 열 벡터의 j번째 원소를 나타낸다.

엔트로피가 가장 큰 \(r\)개의 열의 집합 X를 선택하는 것은 Y_i가 A의 i번째 열의 고유한 원소값들의 집합이라고 하고 I가 지시 함수(indicator function)일 때, 식 (4)와 같이 표현된다.

앞서 관련 연구에서 음수 비포함 행렬 분해의 휴리스틱 알고리즘을 적용할 경우 시간 복잡도가 위와 같이 계획 행렬과 계수가 주어질 경우 O((mn)^r2)라는 것을 언급하였는데, 식 (3)과 (4)의 시간 복잡도는 모두 O(mn)이 되기 때문에, 시간 복잡도 면에서는 식 (3)과 (4)와 같은 방법이 음수 비포함 행렬 분해에 비해 훨씬 유리하다.

코사인 유사도 보존 측면에서도 비교를 수행하기 위해, 코사인 유사도 보존 정도를 측정하기 위한 지표로 식 (5)와 같은 상대 순위 정확도[20], [21]를 사용하였다. 식 (5)에서 S는 추출된 N개의 삼중항의 집합($$ \left(a_i^T, a_j^T,a_k^T\right)\in S$$))이며, sgn은 값의 부호를 나타낸다. 상대 순위 정확도는 차원 축소 전과 후에 데이터 포인트 삼중항(triplet) 사이의 코사인 유사도에 대한 상대적인 부등관계가 유지되는 비율을 계산한 것으로, 예를 들어 차원 축소 전에 $$ a_i^T$$와 $$ a_j^T$$의 코사인 유사도가 $$ a_i^T$$와 $$ a_k^T$$의 코사인 유사도보다 높았다면, 차원 축소 후에도 이와 같은 부등관계가 유지될 때 상대 순위 정확도가 높아지게 된다.

상대 순위 정확도를 비교한 결과는 그림 1과 같다. x 축은 차원을, y 축은 상대 순위 정확도 값을 나타내며, 붉은색 ×은 식 (3)에 의한 차원 축소된 벡터들의 상대 순위 정확도 결과를, 푸른색 점은 음수 비포함 행렬 분해를 통해 얻어진 벡터들의 상대 순위 정확도 값을 나타낸다. 실험은 Movielens[22], Boardgamegeek[23], Jester[24], Datafinti[25]와 같은 공개 데이터셋에 대해 이루어졌는데, 이 데이터셋들은 모두 사용자가 품목에 대해 평점을 매긴 데이터셋으로 개인화 추천 머신러닝을 위해 사용될 수 있다. 다른 데이터셋은 모두 양의 평점 값을 가지는데 비해, Jester 데이터셋은 -10에서 10까지의 평점 범위를 가지고 있다. 음수 비포함 행렬 분해는 원소가 음수인 경우를 다루지 않기 때문에 Jester 데이터셋 같은 경우에는 모든 평점에 10점을 더하여 평점의 최소값을 0점으로 만든 뒤에 실험을 수행하였다.

Fig. 1.

Comparisons of relative ranking precision between nonnegative matrix factorization and variance based feature selection method

실험 결과에서 흥미로운 점은 20이하의 극도로 작은 차원의 경우를 제외하고는 모두 식 (3)이 더 좋은 결과를 보여준다는 것이다. 따라서 근접 이웃 방법을 위한 임베딩을 생성하기 위해 검토 없이 음수 행렬 분해를 사용하는 것이 아니라, 사용할 임베딩의 차원에 따라서 더 좋은 방법을 선택하는 것이 바람직하다는 것을 보여준다.

모든 차원의 상대 순위 정확도 값에 대해 대응 표본 T 검정을 수행한 결과는 표 1과 같다. 모든 유의확률이 5% 이상으로, 모든 차원에 대한 결과는 두 방법 중 어느 한 쪽이 우위에 있다고 하기 어렵다. 그림 1의 결과가 보여주는 것과 같이, 사용하려는 임베딩 차원에 따라서 더 나은 방법을 적용하는 것이 바람직하다고 생각된다.

Table 1.

Paired t-test compares relative ranking precision between nonnegative matrix factorization and variance based feature selection method

음수 미포함 행렬 분해와 분산 변수 선택 기법의 수행시간을 비교한 결과는 표 2와 같다. 데이터 크기가 작은 경우에는 큰 차이가 없지만 Boardgamegeek과 같이 데이터 차원이 커지고 그에 따라 축소할 차원도 같이 커지는 경우에는 앞서 기술된 두 알고리즘의 시간 복잡도와 같이 큰 차이가 나는 것을 볼 수 있다.

Table 2.

Comparisons of execution time between nonnegative matrix factorization and variance based feature selection method

계획 행렬의 열을 선택하는 방법에 있어 식 (3)과 (4)의 상대 순위 정확도를 비교한 결과는 그림 2와 같고, 계수별 상대 순위 정확도에 대해 대응 표본 T 검정을 수행한 결과는 표 3과 같다. 유의 수준을 5%로 본다면 Boardgamegeek의 경우에는 엔트로피를 사용한 식 (4)가 유의미하게 더 좋은 결과를 보이나, 대체로 다른 데이터셋에 대해서는 유의미한 차이가 없다고 할 수 있다. 실험에 사용된 데이터셋으로는 상대 순위 정확도 측면에서 분산과 엔트로피 중 어떤 쪽을 기반으로 열을 선택하는 것이 더 우위에 있다고 결론을 내리기 어렵다.

Fig. 2.

Comparisons of relative ranking precision between entropy based feature selection method and variance based feature selection method

Table 3.

Paired t-test compares relative ranking precision between entropy based feature selection method and variance based feature selection method

식 (3)과 (4)의 수행시간을 비교한 결과는 표 4와 같다. 두 방법의 시간 복잡도가 모두 O(mn)이기 때문에 실제 실험 결과에서도 거의 차이가 없는 수행 시간을 보여주고 있다.

Table 4.

Comparisons of execution time between entropy based feature selection method and variance based feature selection method

Ⅳ. 결 론

본 논문에서는 음수 비포함 행렬 분해 기법과 분산 및 엔트로피에 기반한 변수 선택 기법이 차원 축소 전과 후에 차원에 따라 코사인 유사도를 얼마나 보존하는지, 여러 가지 공개 데이터셋에 대한 실험을 통해 비교하였다. 그 결과 극도로 낮은 차원 외의 구간에서는 모두 변수 선택 기법이 음수 비포함 행렬 분해 기법에 비해 코사인 유사도를 더 잘 보존하는 것으로 나타났으며, 시간 복잡도에 있어서도 변수 선택 기법이 다항식 시간 내에 계산을 끝내기 때문에 더 우위에 있다고 할 수 있다. 변수 선택 시에 엔트로피를 사용하는 경우와 분산을 사용하는 경우는 통계적으로 유의미한 차이가 없었기 때문에 어떤 방법을 사용하던 실제적으로 무방하다고 보인다. 개인화 추천 머신러닝에서 유저가 선호한 품목과 유사한 품목을 근접 이웃 기법을 사용하여 추천하는 베이스라인을 만들 때, 충분한 검토 없이 음수 비포함 행렬 분해 기법을 사용하는 것보다, 적용하려는 차원에 따라 더 좋은 대안이 있는지 검토하는 것이 필요하며, 본 논문에서 그와 같은 대안으로 분산 및 엔트로피에 의한 변수 선택 기법을 제시하였다고 생각된다.

참고문헌

• Y. Hu, Y. Koren, and C. Volinsky, “Collaborative filtering for implicit feedback datasets,” in Proceedings of the 8th IEEE International Conference on Data Mining, pp. 263-272, 2008.
• D. Lee and H. Seung, “Algorithms for non-negative matrix factorization,” in Proceedings of the 13th International Conference on Neural Information Processing Systems, pp. 556-562, 2001.
• Winning the netflix prize: A summary, [Online]. Available: http://blog.echen.me/2011/10/24/winning-the-netflix-prize-a-summary/, .
• G. Strang, Linear algebra and learning from data. Wellesley-Cambridge Press, 2019.
• M. Grbovic, V. Radosavljevic, N. Djuric, N. Bhamidipati, J. Savla, V. Bhagwan, and D. Sharp, “E-commerce in your inbox: Product recommendations at scale,” in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1809-1818, 2015. [https://doi.org/10.1145/2783258.2788627]
• P. Covington, J. Adams, and E. Sargin, “Deep neural networks for youtube recommendations,” in Proceedings of the 10th ACM Conference on Recommender Systems, pp. 191-198, 2016. [https://doi.org/10.1145/2959100.2959190]
• D. Liu, S. Rogers, R. Shiau, D. Kislyuk, K. Ma, Z. Zhong, J. Liu, and Y. Jing, “Related pins at pinterest: The evolution of a real-world recommender system,” in Proceedings of the 26th International Conference on World Wide Web Companion, pp. 583-592, 2017. [https://doi.org/10.1145/3041021.3054202]
• Cosine similarity, [Online]. Available: https://en.wikipedia.org/wiki/Cosine_similarity, .
• N. Gillis and F. Glineur, “Using underapproximations for sparse nonnegative matrix factorization,” Pattern Recognition, Vol. 43, No. 4, pp. 1676-1687, 2010. [https://doi.org/10.1016/j.patcog.2009.11.013]
• S. Vavasis, “On the complexity of nonnegative matrix factorization,” SIAM Journal on Optimization, Vol. 20, No. 3, pp. 1364-1377, 2010. [https://doi.org/10.1137/070709967]
• D. Chen and R. Plemmons, “Nonnegativity constraints in numerical analysis,” in The Birth of Numerical Analysis, World Scientific, pp. 109-139, 2010. [https://doi.org/10.1142/9789812836267_0008]
• A. Cichocki, R. Zdunek, and S. Amari, “Hierarchical als algorithms for nonnegative matrix and 3d tensor factorization,” in Proceedings of the 7th International Conference on Independent Component Analysis and Signal Separation, pp. 169-176, 2007. [https://doi.org/10.1007/978-3-540-74494-8_22]
• H. Kim and H. Park, “Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method,” SIAM Journal on Matrix Analysis and Applications, Vol. 30, No. 2, pp. 713-730, 2008. [https://doi.org/10.1137/07069239X]
• C. Lin, “Projected gradient methods for nonnegative matrix factorization,” Neural Computation, Vol. 19, No. 10, pp. 2756-2779, 2007. [https://doi.org/10.1162/neco.2007.19.10.2756]
• D. Kim, S. Sra, and I. Dhillon, “Fast newton-type methods for the least squares nonnegative matrix approximation problem,” in Proceedings of the 2007 SIAM International Conference on Data Mining, pp. 343-354, 2007. [https://doi.org/10.1137/1.9781611972771.31]
• R. Zdunek and A. Cichocki, “Non-negative matrix factorization with quasinewton optimization,” in Proceedings of the 8th International Conference on Artificial Intelligence and Soft Computing, pp. 870-879, 2006. [https://doi.org/10.1007/11785231_91]
• S. Arora, R. Ge, R. Kannan, and A. Moitra, “Computing a nonnegative matrix factorization-provably,” SIAM Journal on Computing, Vol. 45, No. 4, pp. 1582-1611, 2016. [https://doi.org/10.1137/130913869]
• A. Moitra, “An almost optimal algorithm for computing nonnegative rank,” SIAM Journal on Computing, Vol. 45, No. 1, pp. 156-173, 2016. [https://doi.org/10.1137/140990139]
• N. Gillis, “The why and how of nonnegative matrix factorization,” Regularization, Optimization, Kernels, and Support Vector Machines, Vol. 12, No. 257, pp. 257-291, 2014.
• C. Yoo, “Estimation of Cosine Similarity Change in Singular Value Decomposition,” Journal of KIIT. Vol. 18, No. 3, pp. 31-37, 2020. [https://doi.org/10.14801/jkiit.2020.18.3.31]
• C. Yoo and H. Kim, “Dimensionality Reduction Method without Model for Personalized Recommendation,” Journal of Digital Contents Society, Vol. 21, No. 3, pp. 587-592, 2020. [https://doi.org/10.9728/dcs.2020.21.3.587]
• Movielens 100k dataset, [Online]. Available: https://www.kaggle.com/prajitdatta/movielens-100k-dataset, .
• Boardgamegeek reviews, [Online]. Available: https://www.kaggle.com/jvanelteren/boardgamegeek-reviews, .
• Jester 1.7m jokes ratings dataset, [Online]. Available: https://www.kaggle.com/vikashrajluhaniwal/jester-17m-jokes-ratings-dataset, .
• Grammar and online product reviews, [Online]. Available: https://www.kaggle.com/datafiniti/grammar-and-online-product-reviews, .