게임 알고리즘 종류 - geim algolijeum jonglyu

추천 알고리즘 (Recommendation algorithm)은 크게 3가지로 구분된다

1. Contents Based (CB)
2. Collaborative Filtering (CF)
3. Latent Factorization (LF)

짧게 요약하면, CB는 수작업이고, CF는 벡터 맞추기, LF는 데이터 가공해서 맞추기 게임이라고 보면 된다.

언뜻 듣고 이해하기 어려울테니 좀 더 상세하게 정리해보자.

1. 추천 알고리즘 수작업 Contents Based (CB)

옷을 사러 매장에 갔다고 생각해보자. 내 마음에 드는 디자인을 골랐는데, 색상이 마음에 들지 않아서 매장 직원에게 물어본다. 혹시 다른 같은 디자인, 다른 색상 옷이 있냐고.

그럼 직원 분이 아마 바코드를 찍어서 화면에 뜬 내용을 보고 몇 번의 클릭을 통해 재고가 있는지 여부를 찾아내 줄 것이다.

그 때 바코드에 찍혀서 나온 정보들의 종류는

• 출시년도, 사이즈, 색상, 디자인 코드, 길이, 너비, 재고수량, 보유지점 등등등

이겠지. 다른 조건은 모두 같은데 색상만 다른 상품을 조건 검색해서, 어느 지점에 남아있는지, 우리 지점에 재고가 있는지 등등을 살펴볼 수 있다. DB를 잘 만들어놨다면.

DB에 위의 정보들을 입력하도록 설계하고, 또 수작업으로 입력하는게 고생은 하겠지만, 어찌됐건 할 수 있는 일이다.

인간의 노동력이 많이 들어갈 뿐.

카테고리 기반의 추천 방식에 의지하고 있는 국내의 (거의) 모든 추천 알고리즘이 위의 방식을 따른다.

광고 타게팅을 한다는 회사들의 99%가 아마도 저런 조건부 검색을 통한 추천 알고리즘을 돌리고 있을 것이다.

1-1. CB의 치명적인 단점

상품이 100개 밖에 없는 작은 상점이 아니라, 수십억개가 있다고 생각해보자. 저런 DB 만들기가 만만치 않을 것이다. 상품 종류가 다양해지니 거기에 맞춰서 카테고리도 새로 만들어야하고, 수작업으로 입력된 그 정보의 양이 너무 커져서 검색 속도도 엄청나게 느려진다.

몇 십억개 상품리스트에서 조건부 검색을 하는 사람이 1명만 있어도 시스템 과부하가 예상되는데, 만약에 사용자도 수백만명이라면?

요즘 대부분의 오픈 마켓이 이런 상황일 것이다.

조건부 검색을 해주기 위해서 굉장히 많은 DB 비용을 지불해야 한다.

빅데이터 서버를 만든다며 하둡이 어쩌고 하는 사람들이 하는 업무가, 저런 DB를 어떻게 잘 설계해야 (정확하게는 무슨 “기술”을 써야) 가장 가성비가 좋은 DB를 만들고, 그래서 오픈 마켓 같은 서비스를 얼마나 효과적으로 지원해줄 수 있는지에 대한 고민이었을 것이다.

DB 설계에 대한 고민하기 전에 했던 더 큰 고민은 사실 상품 카테고리 상세 분배하는 인력 비용에 대한 불만이었을 것 같기는 하지만…

아뭏튼, 아래의 2가지 문제를 가지고 있다는 것을 정리할 수 있다

• DB 효율화에 엄청난 비용이 든다
• 카테고리 수작업에 인건비가 너무 많이 든다

2. 추천 알고리즘 – Collaborative Filtering (CF)

CB의 치명적인 단점을 보완하기 위해 Amazon 같은 회사들이 1999년부터 추천 알고리즘에 대한 고민을 했던 것 같더라. 논문들이 나와있다. 당시 고민했던 주제가 요즘 머신러닝 공부한다는 사람들에게 알려져있는 (그렇지만 한국에서는 어떤 회사도 쓰지 않고 있는) Collaborative Filtering이다.

User기반으로 볼 때, A 유저가, 1,2,3 상품을 보고 4번 상품을 구매했는데, B 유저가 똑같이 1,2번 상품을 보고 있으면 3,4번 상품을 추천해주는 방식이다.

수학적으로는 유저별 데이터를 Vector로 정리해서 Vector간 유사성을 계산하는 작업이고, 공식용어로는 Look-a-like 유저 타게팅이라고 한다. (이걸 S대 교수 + 어느 타게팅 광고회사 자문 및 연구소장인 분께 말씀드렸더니 “그런 타게팅이 있냐? 연령, 성별, 지역 타게팅, 앱 설치 안 한 사람 타게팅 같은거만 있는거 아님? 새로운 타게팅이 나왔나보네, 기술 발전이 빠르네요 ㅎㅎㅎ” 라며 필자를 쳐다봤던 기억이 난다. 불과 1달 전의 일이다.)

이걸 하기 힘든 가장 큰 이유는 데이터를 Flow형태로 바꿔야되기 때문이다.

위의 CB에서는 유저들의 행동 데이터 로그를 쌓아야할 필요가 전혀 없다. 단순히 알바들이 상품 카테고리만 잘 나눠놓으면 된다.

근데, CF를 하려면 유저들이 뭐하고 갔는지 로그를 남겨놓고, 그 로그를 1,2,3,4 상품 보고갔다는 형태의 Flow 데이터로 전환시켜야 한다.

데이터 저장 방식을 어떻게 해야할지에 대한 고민부터, 누구는 상품 2개, 누구는 60개 찍고 갔는데 이걸 어떻게 “전처리”해야 Vector간 유사성을 계산할 수 있는지를 고민하며 DB를 만들어야하는데, 당장 CB에도 허덕이는데 CF용 DB를 설계할 수 있는 사람이 얼마나 될까?

CF는 DB로 끝나는게 아니라, 저렇게 비슷한 Vector들을 어떤 계산을 이용해서 맞춰주느냐에 대한 고민도 해야한다. 이걸 “딥러닝이라는 알고리즘을 쓰면 되지 않나요?”라고 묻는 경우들을 종종 보는데, 이미 여러차례 이야기했듯이 그건 어리석은 짓이다. 실제로 글로벌 탑 티어 회사들은 아무도 그런 바보짓을 하지 않고, 가장 심플한 Logistic regression을 쓴다. 계산비용이 너무 비싸기 때문이기도 하고, 더 결정적인 이유는 “열등한” 모델이기 때문이다. (“딥러닝이 제일 열등한 모델인데 몰랐냐?” 참조)

Logistic regression을 쓴다는 말을 바꾸면, 변수를 어떻게 써야할지에 대한 통계모델 레벨에서의 고민을 해야된다는 뜻이다.

그리고, 그 전에 엄청난 고민을 담은 데이터 전처리를 해야한다. 가짜 클릭, 오류 클릭 같은 숫자를 제거하는 작업이 하나의 예시일텐데, 일반 유저에게 가장 쉽게 다가오는 예시로 보통 컨닝한 학생의 시험점수를 걸러내고 학교 전체 성적 평균을 계산하는 예시를 든다. 점수만 보고 어떻게 아냐고? 알 수 있다. 교육학하는 분들의 데이터 전처리 작업이 이런거더라.

2-1. CF의 치명적인 단점

CF가 CB보다 우월해보이지만, 사실 이상한 데이터가 잔뜩 들어가 있으면 모델 자체가 꼬이고, 시간 변화에 따른 Serial Correlation 제거부터 시작해서 온갖 종류의 데이터 전처리 작업, 통계 모델 업그레이드 작업이 장기간 들어가야한다.

DB부터 새로 만들어야한다는 것도 상당한 비용 지출을 감당해야하는데, 또 처음 들어보는 통계 모델링, “이상한” 수학 쓴 데이터 전처리해야된다고하니 보통 회사들이 할 수가 없는 것도 당연한 이치.

데이터가 아예 없을 때는 결국 CB로 추천해 줄 수 밖에 없다는 점도 고려해보면, CF가 무조건 좋은 모델은 아니다.

CF의 Look-a-like 유저 찾아주는걸 쇼핑몰 버젼이라고 치면, 타게팅 광고한다는 회사들의 CTR 모델, Conversion 모델, ROAS 모델 같은 것도 유사한 수학 모델에 기반한다고 할 수 있는데, DB 비용 다 내고, 계속해서 알고리즘 업데이트하고 있으면 아마 마진이 엄청 높아야 광고 서비스를 유지할 수 있을 것이다.

CB가 구식이라 무조건 안 좋은 줄 알았는데, CF를 못하는 현실적인 이유가 있는 것이다.

정리하면

• CB보다 DB설계가 복잡하고
• 데이터 전처리에 수학이 너무 많이들어가고
• 모델링에 수리통계학이 너무 많이 들어간다

3. 진화된 추천 알고리즘 – Latent Factorization (LF)

Netflix에서 영화 골라보고 있으면 추천해주는 알고리즘의 외부에 알려진 명칭은 Latent Matrix Factorization (LMF)다. 영화 감상하는 유저들의 행동 패턴 데이터를 그대로 쓰는게 아니라, 그 데이터에서 Factor를 추출해낸 값으로 영화 추천을 하겠다는 것이다.

데이터는 저 위의 CF모델에서 쓴 데이터를 쓰는데, 적절한 계산을 통해 숨겨진 변수가 들어간 형태로 행렬을 분리하는 작업이 계산작업의 핵심이다.

뭔가 새로운 지식은 아니고, Latent Factor를 찾아내는 이야기는 100년도 더 전에 이미 확립된 Factor Analysis(FA)로 계산이 가능하다. 다만 선형결합만 보는 FA는 정규분포 형태의 데이터에서만 정확하니까 영화 감상 같은 패턴 데이터에서는 FA대신 다른 계산법이 효과를 발휘할 수 있다.

FA의 비선형 모델에 대해서도 이미 장기간 연구가 되어 있기 때문에, 대형 데이터를 이용해서 연구하는 모든 학자들은 이미 비슷한 테크닉들을 다양하게 쓰고 있다.

Netflix가 저 알고리즘을 Kaggle Competition을 통해서 받았는데, 당시 1위 수상자가 물리학 박사 1학년 학생이었다. 보통 박사 과정에서 배우는 통계학 지식을 이용한 것이다.

LF를 이용하면, 영화별 카테고리를 알 필요도 없고, 비슷한 다른 유저를 찾으려고 노력할 필요도 없다. LF에서 Latent factor란 영화 속에 숨겨진 변수를 말하는데, 스칼렛 요한슨이 나온 영화를 좋아하는건지, 여배우의 섹시미가 강조되는 영화를 좋아하는건지 어느쪽인지를 그 유저의 행동패턴을 통해서 추측해내는 계산을 말한다.

좀 더 쉬운 이해를 위해 다시 교육학의 예시를 갖고 오면, 중간고사 20과목 시험 점수를 결정짓는 요소는 언어능력, 수리능력, 암기력, 체력이라는 4개의 숨겨진 변수 밖에 없다는 연구들이 있다. (4개가 맞는지에 대해서는 여전히 갑론을박이 있긴 하지만…)

인공지능이라고 열심히 공부할만한 지식들 중에 Latent Factor를 쓰는 주제들은 PCA 같은 단순 선형 Variance reduction 알고리즘부터, GAN, LDA 정도가 떠오른다.

언뜻 들으면 마치 CB, CF보다 월등히 우월한 모델인 것 같지만, 데이터가 대규모로 쌓이기 전까지는 아무런 의미가 없는 모델인데, 정작 숨겨진 변수를 계산하기 위해서 DB에 대형 행렬계산까지 해야한다.

CB용 DB만드는 것도 최상위 클래스 개발자들이 투입되어야하는데, CF는 넘사벽으로 멀어보여서 못하고 있고, LF는 아예 그렇게 만든 DB를 비싼 계산까지 해줘야되는 모델이다.

이득이 있으려면 한번 계산하면 자주 안 바뀌는 “숨겨진 변수”가 있어야될텐데, 이런 경우가 얼마나 될까?

상품이 계속 들어오고 나가는, 유저도 계속 들어오고 나가는 오픈 마켓 쇼핑몰, 게임업계에서 쓰기는 어렵다. 온라인 광고 시장에 가장 큰 물주 2개 산업이 못 쓰는 서비스인 것이다.

Netflix에서 가능한 이유는 유저는 왔다갔다해도 영화는 그대로 쌓여있기 때문이다.

정리하면

• CF보다 더 어려운데 쓸 곳은 별로 없다

나가며 – LF를 쓸만한 곳

파비가 만들고 있는 광고 타게팅 서비스가 정확하게 LF에 기반한 사업모델이다. 유저들의 행동 데이터를 가공처리하는 Latent Factorization을 거쳐서 “숨겨진 변수”로 바꾸고, 그 숨겨진 변수들로만 타게팅 작업을 한다. 들어온 유저가 계속 빠져나간다면 어쩔 수 없지만, 장기간 이용하는 유저들의 LF값의 정확도는 점점 올라가게 된다. Netflix는 영화가 계속 남아있어서 영화의 숨겨진 변수를 찾았고, 파비 사업모델은 유저가 계속 남아있어서 유저 행동의 숨겨진 변수를 찾는 것이다.

얼마 전, 어느 토익시험 문제를 AI Tutor가 추천해준다는 서비스를 봤다. 한 눈에 CB 기반의 수작업 서비스라는 걸 알 수 있겠던데, 글로벌 시장에 진출할 수 있는 “어디든지 쓸 수 있는 인공지능”을 적용했다고 홍보해놨더라.

현실은, 가장 범용성이 높을 LF를 쓸려고해도 데이터 스타일에 맞춘 데이터 전처리 작업은 필수다. 실제로 다른 데이터 셋에서 같은 Latent Factor를 찾아내기란 여간 어려운 일이 아닌데, 설령 같은 시험 점수라고 해도 컨닝 같은 사건이 있었을 수도 있고, 특정 학생 몇 명이 엄청난 Outlier였을 수도 있다. 이런 데이터 전처리가 무슨 단순한 공식처럼 적용할 수 있는건 아니다.

CB기반이면서 LF라고 우기는게 보기 좀 그렇기는 하지만, 어쨌건 LF로 돌리고 있었다고 해도 전세계에서 한국인만 치는 시험인 TOEIC처럼 단순 패턴화가 잘된 시험에서 얻은 경험치로 TOEFL 같은 시험으로 이게 확장가능하냐고 물으면, 고급 통계학 적용해서 만든 논문 하나에서 쓴 모델을 그대로 다른데다 갖다 붙이면 새롭게 좋은 논문이 나오냐고 되묻고 싶다. 논문 1개만 쓰면 순식간에 100개로 뚝딱 늘어나냐? ㅋㅋ

“어디든지 쓸 수 있는 인공지능”이라는게 불가능하다는걸 보여주는 용도로 LF를 넣은 TOEIC 문제 추천 서비스 하나 제작하는 것 정도는 가능해보인다. 누군가에겐 처음보는 데이터 전처리와 Latent Factorization같은 황당한 계산법 때문에 불가능의 영역이겠지만, 내 눈엔 간단한 Toy 프로젝트 정도로 보이는데, 다른 시험은 제쳐놓고 토익 시험에라도 인력 투입 없이 LF 기반의 문제 자동 분류, 시험점수 예측이 가능하도록 만들면 관심있는 국내 교육회사가 있을까?

좀 더 생각해보니 TOEIC 시험이 매달 출제 문제도 패턴이 있어서 쪽집게 강사들도 많던데, 그것도 LF로 찾아낼 수 있어 보인다. 약한 영역만 집중적으로 1시간동안 쪽집게 예상 기출 문제 풀어보고 시험장 들어가면 100점 상승 이런거 가능해보이는데? ㅋ

+ 가만보니 TOEFL, SAT, GRE, GMAT, LSAT 같은 ETS 주관 시험들에 전부 다 가능해보이는데? 어차피 패턴 매칭이잖아?