매칭, 검색, 추천 시스템의 차이점에 대하여

 

서비스를 만들다 보면 A와 B를 짝지어 주고 싶다는 요구사항을 정말 자주 만나게 된다. 예를 들면 다음과 같다.

• 개발자 <-> 프로젝트(프리랜서 플랫폼)
• 학생 <-> 멘토(멘토링 플랫폼)
• 유저 <-> 유저(소개팅/친구 매칭)

이런 문제들을 한꺼번에 다루는 것을 매칭 시스템(matching system)이라고 부른다.

 

겉으로 보기에는 검색/추천 시스템과 비슷해 보인다. 하지만 어떻게 문제를 모델링하느냐에 따라 알고리즘 자체가 완전히 다른 세계가 된다. 이 글에서는

1. 매칭 시스템이 무엇인지
2. 검색/추천 시스템과는 무엇이 다른지
3. 어떤 상황에서 매칭 시스템을 쓰는 게 맞는 선택인지
4. 대표적인 매칭 알고리즘을 어떻게 이해하면 되는지

위와 같은 내용들을 정리해본다. 이번 포스팅에서는 매칭이라는 개념에 대해서 폭넓게 알아볼 예정이며, 그 중에서도 기술적으로 매칭과 검색 그리고 추천의 차이점에 대해서 자세하게 알아볼 예정이다. 개인적으로 소개팅 시스템이나 기업-지원자 인턴 매칭 시스템을 구축한 경험을 바탕으로, 그리고 검색이나 추천 시스템 같은 매칭과 비슷한 시스템에 대해서 질문을 받아본 입장으로 각 개념에 대한 혼동이 없이 매칭이란 무엇인지 자세하게 이해할 수 있도록 하는 것을 목표로 포스팅을 작성할 예정이다.

 

본론

매칭 시스템이란?

조금 수학적으로 말하면, 매칭 문제는 각 요소에 대한 선호도 순서가 주어지면 동일한 크기의 두 요소 집합 간에 안정적인 일치를 찾는 문제이다. 안정적이라는 것의 의미는 매칭 하에서 현재 파트너보다 서로를 선호하는 다른 쌍(A,B)이 존재하지 않을 때를 의미한다.

 

이러한 문제를 안정적인 매칭 문제(Stable matching problem)이라고 부르며, 대표적으로는 안정적인 결혼 문제(stable marriage problem)이 있다. 다음과 같이 명시되어 있다.

n명의 남성과 n명의 각 이성의 모든 구성원을 선호하는 순서대로 순위를 매긴 경우, 남성과 여성을 결혼시켜 현재 파트너보다 서로를 갖고 싶어하는 두 명의 이성이 없도록 합니다. 그러한 쌍이 없을 때 결혼 생활은 안정적인 것으로 간주됩니다.

 

이러한 설명들은 stable matching problem이라는 위키피디아 문서에서 확인할 수 있으며, 아주 오래전부터 이 문제는 많은 사람들이 접하는 문제였다. 자세한 내용은 아래의 레퍼런스를 참고하여 확인할 수 있다.

• [wikipedia] 안정적인 매칭 문제 : https://en.wikipedia.org/wiki/Stable_matching_problem

Stable matching problem - Wikipedia

 

한 가지 재미있는 점은 이러한 매칭 시스템을 기술적으로 구현해야하는 상황이 아닌 경우에도 많이 쓴다. 예를 들어서 우리가 기업 <-> 지원자를 매칭시키는 플랫폼을 만드는 경우가 아니라, 일반적으로 병원이나 대학교에서도 이러한 매칭 시스템을 통해서 지원자를 받고 있다. 실제로 이러한 매칭 알고리즘을 발명함으로써 2012년에 노벨 경제학상을 받은 사람 또한 존재한다.

 

이러한 안정적인 매칭을 위한 알고리즘은 다양한 수학적 기호로 정의되어있으며, 많은 알고리즘이 존재하고 변형 또한 다양하다. 두 그룹이 n명으로 같은 상황에서 서로에 대한 선호도가 있는 경우에 쓰이는 Gale-Shapley 알고리즘, 두 그룹이 각각 n명과 m명으로 다르며, 선호도도 다 다른 경우에 쓸 수 있는 hospital-resident 알고리즘 등 다양한 알고리즘이 존재한다. 이 두 알고리즘에 대해서는 예전에 아주 간략하게 포스팅을 진행한 적이 있다.

 

알고리즘 문제풀이 사이트 백준(beakjoon)에서도 관련하여 안정 결혼 문제에 대한 태그를 지원한다. 아래의 포스팅과 함께 안정 결혼 문제 태그를 가진 백준 문제풀이에 대한 코드를 남겨 두었다.

• [marsboy] 매칭은 어떻게 구현할까? : https://marsboy.tistory.com/37

매칭은 어떻게 구현할까? (안정 결혼 문제, 매칭 알고리즘)

 

매칭 시스템 (혹은 매칭 알고리즘)을 간단하게 설명하면, 조건을 만족하면서 좋은(good) 매칭을 찾는 것을 의미한다. 여기서 좋다의 기준은 문제에 따라 다르다. 흔하게 쓰는 기준은 다음과 같다.

• 안정성(stability) : 서로 현재 파트너보다 더 서로를 선호하는 "불만족 쌍(blocking pair)"이 없는 상태
• 최적성(optimality) : 전체 만족도(sum of scores)를 최대화, 혹은 특정 한쪽을 최대한 만족시키기
• 공정성(fairness) : 특정 그룹이 구조적으로 불리한 매칭을 받지 않도록 하는 것

매칭 시스템은 이 목표를 이루기 위해서 설계된 알고리즘 + 시스템 구성이라고 볼 수 있다. 일반적으로 안정성을 가장 기본에 두고 있으며, 상황에 따라서 매칭 알고리즘을 다양하게 선택할 수 있다. 가장 기본적인 gale-shapley 알고리즘의 경우에는 한쪽 그룹을 대상으로 반대쪽 그룹에 대해서 평가를 진행한다. 이쪽에서 대상이 되는 그룹은 청혼자(proposing)이라고 부르며, 일반적으로 좀 더 만족스러운 상대를 고르게 된다.

https://www.youtube.com/watch?v=0m_YW1zVs-Q&t=264s

 

매칭 시스템에도 이러한 제약이 있으며, 이런 점들을 고려해 적절한 매칭 알고리즘을 잘 골라야 한다. 뿐만 아니라, 매칭의 목표를 잘 고려해야한다. 더욱 많은 매칭 쌍을 만들기 위해서 스코어나 필터링을 후하게 하는 경우, 매칭의 품질은 떨어질 수 있다. 그렇게 유저들이 이탈할 수 도 있다. 결국 목표를 잘 선택하는 것이 중요하다.

 

다음으로는 매칭 시스템을 좀 더 자세하게 살펴보기 전에, 비슷한 느낌이지만 기술적으로는 완전히 다른 검색 시스템과 추천 시스템에 대해서 간단하게 살펴보려고 한다.

 

검색 시스템, 추천 시스템이랑 다른가?

예전에 벡터 검색에 관련한 논문을 작성하면서 매주 리포트를 진행했다. 관련해서 어떤 연구를 하고 있고, 어떤 결과를 얻었는 지에 대한 이야기를 하는 자리였는데, 당시에 나는 추천 시스템이랑 검색 시스템에 대한 큰 고민이 없었다. 검색이랑 추천과의 차이는 그저 이름 짓기의 차이다. 데이터를 검색해주는 것을 보고서 "추천 시스템"이라고 부를 수도 있을 것이라고 생각했다.

 

사실 기술자라면 검색 시스템과 추천 시스템을 완전히 분리해서 생각해야 했다. 무언가를 추천해주는 로직을 "검색 시스템"으로 설계할 수도 있다. 이번 섹션에서는 검색 시스템이란 무엇인지에 대해서만 간단하게 다룬다. 예전에 embedding을 사용해서 테이블 데이터(.csv)를 통해서 데이터를 검색해주는 논문을 작성한 적이 있다. 자세하게 알고 싶다면 해당 포스팅을 참고하는 것을 추천한다.

• [marsboy] embedding을 이용한 검색 엔진: https://marsboy.tistory.com/58

embedding을 이용한 검색 엔진/추천 시스템 만들기

 

검색 시스템(Search System)

먼저, 검색 시스템은 기본적으로 데이터를 벡터 공간(vector space) 위에 저장한다. 검색에 포함하고 싶은 대상들을 모두 백터 공간 위에 나타낸 후에, 검색하고자 하는 데이터를 같은 embedder를 써서 임베딩으로 나타낸 후에 검색을 시도한다.

4*3의 .csv 데이터를 임베딩하는 경우

 

여기서 임베딩(embedding)이라는 개념은 특정 데이터를 백터 공간 위에 나타내는 것을 말한다. 그렇게 임베딩을 시켜주기 위한 임베더(embedder)가 존재한다. 예를 들어 word2vec이라는 임베더는 단어를 임베딩시켜주는 역할을 한다. 사과, 바나나, 지하철이라는 단어를 임베딩하게 되면 어떻게 될까? 세 개의 데이터를 벡터 공간 위에 나타내고 나서, 딸기로 검색하려고 한다. 그렇다면 딸기를 word2vec으로 임베딩으로 나타낸 후에, 딸기의 임베딩과 가장 가깝게 있는 데이터를 가져오는 것이다.

딸기로 검색한다면

 

많은 데이터가 있다고 치자. 그렇다면 우리의 직관에 따르면 "지하철"과 "사과"가 있다고 하면, 딸기와 조금이나마 연관이 있는 것은 "사과"일 것이다. 그렇게 해서 사과와 딸기가 벡터 공간 위에 가깝게 위치하게 되고, 가장 가까운 데이터를 반환하는 검색 시스템의 알고리즘에 따라서 사과를 반환하게 된다.

 

이것이 딸기를 통해서 검색했을 때의 결과이다. 가장 가까운 데이터를 가져오는 것은 코사인 유사도 혹은 L2 distance 같이 거리를 고려하여 측정한다.

 

검색(Search)

벡터 공간 위에서 가깝게 위치하는 데이터를 가져오는데, 코사인 유사도 혹은 L2 distance를 쓴다는 것은 크게 어려운 개념이 아닐 것이다. 기하와 벡터를 배운 사람의 입장에서도, 그렇지 못한 사람의 입장에서도 두 물체간의 거리를 계산하는 공식을 통해서 데이터를 가져오는 것은 직관적으로 이해하기 어렵지 않다.

 

https://www.ibm.com/kr-ko/think/topics/knn

 

이렇게 데이터를 가져오는데에 있어서는 이러한 알고리즘을 쓴다. 더 나아가서 검색 엔진의 성능을 높이고 있다면, 인덱스를 통해서 임베딩 간의 거리를 미리 계산할 수도 있고, 그냥 단순하게 '가장 가깝게 있는 k개를 가져온다'가 아니라, 다른 방법으로 데이터를 가져올 수 있다. 가장 가까운 k개의 데이터를 가져오는 것을 knn 알고리즘이라고 부른다. k-최근접 이웃 알고리즘이라는 표현을 쓴다.

 

그렇다면, 벡터 공간 위에 데이터를 나타내는 것은 어떻게 되는 걸까? 이전 글에서는 간단하게 임베딩을 시켜주는 것이기 때문에 임베더(embedder)라는 표현을 썼지만, 좀 더 일반적으로 자주 쓰이는 용어로는 임베딩 모델(embedding model) 혹은 인코더(encoder)라고 부른다.

 

인코더(encoder)

컴퓨터에게 있어서 사과와 딸기, 그리고 바나나가 가깝다는 것이 이미 학습되어있는 모델을 의미한다. 예를 들어 다음과 같은 문장이 있다고 생각해보자.

• 나는 사과를 먹었다
• 그는 딸기를 좋아한다
• 아침에 바나나를 먹고 나왔다.

"사과", "딸기", "바나나"는 비슷한 자리(문맥)에 등장하니, 이 단어들은 비슷한 의미를 가진다라고 보고 벡터도 비슷하게 가도록 학습시키는 것이 핵심이다. 이러한 모델을은 이미 대량의 데이터를 통해서 학습되었으며, 우리가 특정 데이터를 넣으면 학습된 내용에 따라서 결과를 반환한다. 그렇게 반환된 데이터들은 d 차원을 가진 벡터값이며, 내가 일반적으로 논문을 작성할 때에는 256차원 혹은 768차원의 벡터값이 반환되었다.

 

따라서, 이러한 인코더는 임베딩을 만드는 함수라고 생각할 수 있고, 대부분의 신경망 모델이다. word2vec, BERT, OpenAI의 text-embedding-3-large 이런 것들이 다 인코더-임베딩을 만드는 함수-에 해당한다.

 

문장을 통한 검색

그렇다면, 만약에 문장 단위의 검색 시스템을 만드려면 어떻게 해야 할까? 단어 수준의 검색에서는 word2vec처럼 단어를 벡터로 만드는 임베딩 모델을 사용할 수 있다. 문장 단위의 의미 검색을 하고 싶다면, 문장을 직접 벡터로 변환해주는 문장 임베딩 모델을 필요로한다. 실무에서는 보통 BERT 계열의 Transformer 모델을 문장 임베딩용으로 튜닝한 Sentence-BERT(SBERT) 등의 모델을 사용한다.

 

다만 반드시 BERT여야 하는 것은 아니며, 문장을 고정 길이 벡터로 표현할 수 있는 어떤 임베딩 모델도 사용할 수 있다.

 

추천 시스템(Recommendation System)

그렇다면 이번에는 추천 시스템은 검색 시스템과 뭐가 다를까? 처음에는 그게 그거 아닌가? 라고 생각했지만, 검색하여 가져다주는 것을 "검색"이라고 부르든, "추천"이라고 부르든 결국 리스트만 잘 뽑아주면 되는 것 같았다.

 

하지만 실제로 시스템을 설계하는 입장에서 보면 둘은 관점과 입력이 다르다.

 

• 검색 시스템
  • 유저가 먼저 "딸기"처럼 쿼리를 던진다
  • 시스템은 그 쿼리에 가장 잘 맞는 데이터를 찾아서 보여준다.
• 추천 시스템
  • 유저가 아무 말도 안 해도,
  • 이 유저라면 아마 이런 것을 좋아할 것이라며 먼저 후보를 던져준다.

https://medium.com/swlh/netflix-and-the-recommendation-system-e806f062ba74

 

기술적으로는 둘 다 "어떤 기준으로 상위 k개를 뽑아오느냐" 라는 문제인데, 그 기준이 검색에서는 쿼리 문자열, 추천에서는 유저(혹은 세션)의 상태라는 차이가 있다.

 

유저-아이템 행렬(user–item matrix)

추천 시스템을 이야기할 때 빠지지 않는 게 하나 있다. 바로 유저-아이템 행렬이다. 이러한 행렬의 개념과 벡터의 개념은 비슷하다. 그래서 기술적으로 깊게 들어갈 수록 검색과 추천 시스템은 비슷할 수 있다. 

https://www.linkedin.com/pulse/collaborative-filtering-how-build-recommender-system-redisinc-l3exc/

 

위 그림은 레디스의 수석 엔지니어가 작성한 그림으로, 행렬과 함께 벡터가 있는 전반적인 아키텍처를 볼 수 있다. 이러한 내용을 통해서 간단한 예시를 들어가며 추천 알고리즘에 대해서 알아보자.

 

다음과 같은 기본 개념이 있다.

• 행(row): 유저
• 열(column): 아이템(영상, 상품, 글, 곡 등)
• 칸(cell): 유저와 아이템 사이의 상호작용 기록

예를 들어서 유저의 동작에 따라서 상호작용을 설명하면

• 유저 A가 영화 1에 별점 5점을 줬다 → A, 영화1 칸에 5
• 유저 B가 상품 3을 여러 번 클릭했다 → B, 상품3 칸에 1 (혹은 가중치)
• 유저 C는 어떤 콘텐츠도 본 적이 없다 → C의 행은 거의 다 비어 있음

실제 서비스에서는 이 행렬이:

• 유저 수: 수만~수억
• 아이템 수: 수천~수백만
• 대부분의 칸은 비어 있음 (안 본 조합이 훨씬 많기 때문)

이 유저-아이템 행렬을 어떻게 잘 이용해서:

“A가 5점을 준 영화들과 비슷한 영화들을 B에게도 보여줄까?”
“C가 최근에 본 곡들과 비슷한 곡을 더 추천해줄까?”

 

를 결정하는 게 추천 시스템의 핵심 중 하나다. 따라서 우리가 유튜브나 넷플릭스에서 무언가를 선택하는 것은 나와 비슷한 사람들이 본 영상들이 함께 뜨는 것이며, 같은 현상을 겪은 사람들이 있는 지 모르겠지만, 10년 전의 유튜브 영상이 알고리즘에 떠서 들어가보면, 10년 전이나 된 영상인데도, 최근 1주 정도에 사람들이 댓글을 달면서 "왜 이게 내 알고리즘에 뜬 지 모르겠다"와 같은 내용을 담는 경우가 많다.

 

행렬 분해와 임베딩: 유저도 벡터, 아이템도 벡터

검색 시스템에서 아이템들을 벡터로 바꿔서 벡터 공간 위에 올려놓은 것처럼, 추천 시스템에서도 결국엔 유저와 아이템을 둘 다 벡터로 표현하게 된다. 아이디어는 단순하다. 조금 수학적인 내용이 많이 들어간다.

1. 유저-아이템 행렬을 떠올려본다.
2. 이 큰 행렬을 두 개의 얇은 행렬로 분해해본다.
   • 하나는 유저 쪽 행렬 → 각 유저를 d차원 벡터로 표현
   • 하나는 아이템 쪽 행렬 → 각 아이템을 d차원 벡터로 표현
3. 유저 벡터와 아이템 벡터의 내적(dot product) 또는 코사인 유사도가 “좋아할 확률” 비슷한 값이 되도록 학습

이렇게 학습이 끝나면:

• 각 유저는 u_i ∈ R^d
• 각 아이템은 v_j ∈ R^d
• u_i · v_j (또는 코사인 유사도)이 크면,
  “유저 i가 아이템 j를 좋아할 것”이라고 보는 것이다.

여기서 나온 u_i, v_j가 바로 유저 임베딩, 아이템 임베딩이다. 검색에서 “문장 → 벡터”를 만드는 인코더가 있었다면, 추천에서는 “유저 → 벡터”, “아이템 → 벡터”를 만들어주는 모델이 있는 셈이다.

 

벡터 공간에서의 추천

이제 벡터 공간 관점에서 추천을 그려보자.

• 검색에서는:
  • 쿼리 문장을 임베딩해서 q라는 벡터를 만든 뒤
  • q와 가장 가까운 아이템 임베딩들을 가져온다.
• 추천에서는:
  • “유저 i”를 임베딩해서 u_i라는 벡터를 만든 뒤
  • u_i와 가장 가까운 아이템 임베딩 v_j들을 가져온다.

즉, 추천도 결국엔 일종의 k-NN 검색이다.

• 검색: 쿼리 벡터 기준으로 가까운 아이템을 k개 가져오는 것
• 추천: 유저 벡터 기준으로 가까운 아이템을 k개 가져오는 것

차이점은 단 하나, “쿼리가 텍스트냐, 유저냐” 정도다. 그래서 실제로는 추천 시스템의 후보 생성 단계에서 벡터 DB와 같은 검색 기술을 그대로 사용하기도 한다.

 

마치며

개인적으로는 매칭 시스템이나 검색 시스템에 대해서만 자세하게 공부해본 적이 있었고, 추천 시스템은 대략적으로나마 알고 있었다. 하지만 이번 포스팅을 준비하면서 자세하게 협업 필터링 등의 추천 시스템 기술에 대해서 공부해보니 행렬을 다루게 되면서, 생각해보면 벡터와 비슷하다는 생각을 하게 되었다.

 

추천 시스템 또한 재미있는 기술이다. 이미 많은 부분의 개발이 이루져서 추천 시스템은 비슷비슷하게 고착화되어 있는 것 처럼 보인다. 성능 개선을 위해서 다양한 시도들을 계속 하고 있는 도메인으로 보이는데, 중간에 레디스를 통한 추천 시스템 구현 아키텍처 그림에서 나온 bloom filter라는 개념은 자세하게 공부하고 싶었던 부분이었는데, 나중에 포스팅으로 다뤄도 좋을 것 같다.