카테고리 보관물: 인공지능, 기계학습 ML/AI

데이터과학 Data Science, 마케팅, 알고리즘 Algorithm, 애드테크, 인공지능, 기계학습 ML/AI, 통계

MAB (Multi Armed Bandit) – 광고 플랫폼의 캠페인 노출 최적화

댓글 남기기

MAB는 기계학습 강화학습의 일종입니다. 완전한 강화학습은 아니지만 포함해서 취급합니다.

MAB는 “엠에이비”, “멀리암드밴딧”이라고 발음합니다.

“팔 여러 개 달린 산적” “Multi Armed Bandit”은 슬롯머신의 별명인데 이 알고리즘은 이름처럼 “어떤 슬롯 머신의 팔을 당겨야 돈을 딸 수 있는가?” 와 같은 문제를 풀기위한 방법입니다.

엄밀한 의미의 강화학습에 포함되지 않지만 상당히 간단하고 쓸만하고 강화학습의 개념을 익히기 좋기 때문에 강화학습을 설명할 때 가장 먼저 설명하는 것이기도 합니다.

여러 대의 슬롯 머신이 있고 이 슬롯 머신 중 어떤 것의 레버를 당겨야 돈을 딸 수 있는가를 푸는 문제입니다. 한 번에 1대의 슬롯머신의 레버를 당기고 계속해서 반복합니다.

이 문제의 전제 조건이 있는데 한 번에 하나의 슬롯머신의 팔을 당길 수 있다는 것입니다.

그래서 동시에 모든 슬롯머신의 팔을 당겨서 그리고 여러번 당겨서 어떤 슬롯머신이 돈을 딸 학률이 높은지 알아낼 수 없습니다.

그래서 한 번에 하나씩만 선택해서 돈을 최대한 많이 따는 것이 이 문제의 푸는 목적입니다.

복잡한 공식은 여기에 안 적겠습니다. 구글에서 찾아보시면 수식과 코드가 다 있습니다.

첫번째 방법. Greedy 욕심쟁이

모든 슬롯머신에 순차적으로 한 번씩 팔을 내려봅니다. 그래서 돈을 못땄다면 다시 한 번씩 다 팔을 내려봅니다.

몇번을 수행한 후에 딴 돈이 가장 많은 슬롯머신에게 계속해서 몰빵합니다.

이게 그리디(Greedy, 탐욕스러운) 방식입니다. 단순하면서도 조금 무식한 방법입니다.

두번째 방법. epsilon

Greedy 방법을 사용하되 무작정 사용하지 않고 랜덤으로 팔을 당길 확률을 정해놓습니다.

만약 50%의 확률로 랜덤을 고르겠다고 하면 한 번은 지금까지 가장 돈을 많이 딴 슬롯머신을 당기고 한 번은 랜덤으로 아무것이나 고르는 방법입니다.

그나마 다른 것들에게 기회를 준다는 것 때문에 낫습니다.

epsilon이라는 이름은 랜덤으로 고를 확률값을 epsilon이라고 이름을 붙여서 부르기 때문입니다.

세번째 방법. UCB(Upper-Confidence-Bound)

위의 epsilon에서 약간의 공식을 주어서 랜덤 찬스가 왔을 때 무조건 랜덤으로 어떤 슬롯머신을 팔을 다기지 않고 덜 뽑혔던 슬롯머신에 가중치를 두어서 더 뽑아서 팔을 내려줍니다.

네번째 방법. Tompson sampling

톰슨 샘플링은 설명을 하면 조금 복잡해지는데 확률 분포 중 하나인 베타분포를 이용해서 확률이 가장 높은 것을 선택하는 것입니다.

베타분포 함수에 선택된 횟수와 돈을 딴 횟수를 입력하면 베타분포를 각각 구할 수 있고 그 베타분포를 확률 분포로 이용해서 값을 구하면 선택할 것을 찾을 수 있습니다.

저장된 데이터를 이용할 수 있는 장점이 있고 UCB 보다 성능이 조금 더 좋아서 온라인 추천 시스템에서 많이 이용되고 있습니다.

A/B 테스트와 MAB의 관계

A/B 테스트는 통계학의 실험계획법 중 하나 인데 2개 또는 2개 이상의 그룹을 동일한 수(최대한 비슷한 수) 만큼 각각 분할해서 한쪽에만 다른 처리를 해서 두 그룹의 차이를 보는 방법입니다

온라인에서는 흔히 버킷테스트라고 하는 방법입니다.

예를 들어 광고배너가 있는데 원래 배너는 테두리가 하얀색인데 테두리를 빨간색으로 바꿨을 때 사람들이 어떤 것을 클릭을 더 많이 하는지 알아 보고 싶을 때 같은 경우에 합니다.

A/B 테스트가 오랫동안 사용한 방법이기 때문에 잘 알려져 있지만 문제는 두 그룹을 방해받지 않게 불한하는 방법이 상당히 어렵고 두 그룹의 차이를 알아보는 방법이 데이터의 양상과 원래 데이터의 특성에 따라 여러가지 통계적인 방법을 써야하는 데 실수로 잘못된 방법으로 확인을 했다고 하더라도 그 실수를 알아내기 어렵다는 문제가 있습니다.

A/B 테스트를 하는 것은 많이 어렵지 않지만 A/B테스트의 결과를 해석하는 것은 매우 숙련된 통계학자가 필요하고 시간도 많이 걸립니다.

그래서 A/B 테스트를 하지 않고 각각 반응을 그대로 볼 수 있는 어떤 환경이 있다면 그 환경에서는 각각 매번의 결과에 따라서 결과가 좋은 것에 점수를 더 줘서 그것을 선택하게 만드는 방법을 쓰자는 것입니다.

그래서 MAB는 온라인 시스템의 추천시스템이나 평가에 굉장히 적합합니다.

광고시스템과 MAB

한 번에 5개의 제품을 동시에 보여지는 광고 이미지가 있다고 가정합니다.

사용자 별, 또는 사용자 그룹별로 어떤 제품에 더 관심을 가지는 지를 보고 클릭을 많이 하는 제품을 MAB에 의해서 더 많이 노출한다고 하겠습니다.

흔히 쓰는 방법이지만 이게 문제가 좀 있습니다.

  • 선택할 제품이 매우 많은 경우에는 못합니다. 아마도 제품의 카테고리가 있고 그것들 중에 가장 잘 팔리는가 하는 전략을 취할 수 있지만 상식적으로 좋은 방법은 아닐 것입니다.
  • 선호도는 계절성 효과, 요일 효과, 캠페인에 피로도에 따라 달라집니다. 슬롯머신 처럼 확률이 안변한다는 가정을 두기가 좀 어렵습니다. 변동이 너무 많습니다.
  • 또 가중치를 변경하는 것 때문에 생기는 문제가 파생적으로 생기는데
    • 쿠키로 인해 신규 및 재이용자의 분포에 영향을 미칩니다.
    • 변화에 대한 적응이 느리기 때문에 인해 관성때문에 결과가 왜곡될 수 있습니다.

아주 단순한 경우에만 사용이 가능하며 복잡한 시스템으은 오히려 결과를 왜곡할 수 있습니다.

저렇게 선택한 것이 여전히 가장 좋은 방법 또는 그리 좋은 선택이 아닐 수도 있겠지만 그 자체를 확실하게 확인 못합니다. 이건 다른 알고리즘도 동일한 문제이긴 합니다만.

Python, 데이터과학 Data Science, 데이터마이닝 Data mining, 데이터분석 Data Analysis, 데이터엔지니어링 Data Engineering, 알고리즘 Algorithm, 인공지능, 기계학습 ML/AI

Faiss – 고속 벡터 검색 엔진으로 유사도 검색하기, Vector Search Engine

댓글 남기기

Faiss는 Facebook Lab에서 만든 벡터 검색 엔진입니다.

Faiss는 벡터 갬색 엔진이고 유사도 검색을 하거나 추천, 기계학습로 만든 모델을 활용해서 응용 서비스를 만들 때 사용합니다.

별거 아닌거처럼 보이지만 불가능한 것을 가능하게 만들어 주는 매우 유용한 라이브러려입니다.

라이브러리이기 때문에 자체로 서비를 제공하는 것은 아니고 이 라이브러리를 이용해서 Backend, Frontend 서비스를 개발하거나 응용 프로그램에 넣을 수 있습니다.

벡터 검색 엔진

벡터 검색 엔진이 뭔지를 설명해야 하는데요. 보통 그래프 서치라고도합니다. 이것들은 주로 수치를 찾는 것을 말하는데 지도검색 같은데서도 사용하는 것으로 매우 쓸모가 많은 엔진입니ㅏㄷ.

일반적으로 검색 엔진이라고 말하면 흔히 텍스트를 검색하는 것을 생각합니다. 구글의 웹 검색, 네이버 검색, 다음 검색 같은 것은 검색 포털이요. 그게 아니면 Elastic Search나 Lucene갈은 검색 엔진을 생각할 텐데요.

하지만 벡터 검색은 텍스트가 아닌 벡터를 빠른 속도로 찾는 것을 말합니다. 벡터는 수열을 말합니다.

아래와 같이 10개의 숫자가 묶여 있으면 이걸 10차원 벡터라고 합니다. 숫자가 100개 있으면 100차원 벡터, 1000개면 1000차원 벡터입니다.

[-0.00709967 -0.01956441  0.03790117 -0.00150699 -0.02145613 -0.06128123
  0.04965064 -0.05588596  0.08241648 -0.05128423]

이런 것들이 수억개가 있고 수억개 중에 어떤 벡터와 가장 가까운 벡터를 찾아야 한다면 문제가 어려워집니다.

가장 가까운 것을 주어진 입력 벡터와 수억개의 벡터를 모두 하나씩 연결해서 서로의 거리를 계산한 다음 가장 가까운 것을 찾아야 하기 때문입니다.

가장 가까운 것을 찾는데 수십분이 걸릴 수 있습니다. 이러면 실제 서비스에서는 쓸 수 없습니다.

어떤 사용자가 온라인 서적 판매사이트에 접속했을 때 그 사람에게 책을 추천해줘야 하는데 추천할 책 목록을 검색하는데 10분씩 걸린다면 서비스에 적용하지 못합니다. 다른 서비스도 마찬가지구요.

Faiss는 인덱싱 방식을 다르게 해서 데이터가 많아도 짧게는 밀리초 단위 길게는 수초 이내에 결과를 찾아 줍니다. 즉 온라인 추천 서비스에 빠르게 적용하는 추천 시스템 등을 개발하는데 사용할 수 있습니다.

Python Faiss library

Faiss는 Python wrapper를 공식 지원하고 있습니다. c++로 만들어졌으니까 다른 언어로도 연결해서 사용할 수 있습니다. Go lang이나 Node.js, Kotlin 같은 것을 쓰면 Python 보다는 성능이 더 좋을 것입니다.

깃헙 레파지토리: https://github.com/facebookresearch/faiss

레파지토리에 있는 것을 설치해도 되고 그냥 pip를 이용해서 설치해도 됩니다.

pip3 install faiss-cpu

gpu 버전을 설치하고 싶으면 gpu 버전ㅇ로 명시해서 설치하면 됩니다.

pip3 install faiss-gpu

사용법은 매뉴얼을 봐야 하겠지만 기본 사용법은 쉽습니다.

Faiss로 유클리디안 거리로 벡터 검색하기

아래 코드는 유클리디안 거리(Euclidean Distance)로 찾는 예제입니다.

이런 것은 KNN (K-nearest-neighbor) 와 같은 기계학습 모델에 사용하는 것입니다. KNN은 판별 모델에서 사용할때 매우 강력한 알고리즘이지만 검색할 때 너무 느리고 자원을 많이 사용하는 문제로 인해서 실제로는 거의 사용을 못하는 알고리즘이지만 Faiss를 이용하면 이걸 쓸 수 있습니다.

Faiss 색인을 생성할 때 벡터의 차원을 지정해주고, Index의 유형도 결정을 해줘야 하는 것이 중요합니다. 검색은 입력한 k의 갯수만큼 리턴하게 되어 있고 벡터의 색인 번호와 거리를 리턴하게 되어 있늡니다.

색인 번호는 그냥 입력한 입력한 벡터의 순번입니다.

import faiss
import numpy as np
import random

# Euclidean distance 기반으로 가장 가까운 벡터를 찾는다.

# 랜덤으로 10차원 벡터를 10개 생성
vectors = [[random.uniform(0, 1) for _ in range(10)] for _ in range(10)]
# 10차원짜리 벡터를 검색하기 위한 Faiss index 생성
index = faiss.IndexFlatL2(10)
# Vector를 numpy array로 바꾸기
vectors = np.array(vectors).astype(np.float32)
# 아까 만든 10x10 벡터를 Faiss index에 넣기
index.add(vectors)
# query vector를 하나 만들기
query_vector = np.array([[random.uniform(0, 1) for x in range(10)]]).astype(np.float32)
print("query vector: {}".format(query_vector))
# 가장 가까운 것 10개 찾기
distances, indices = index.search(query_vector, 10)
# 결과룰 출력하자
idx = 0
for i in indices:
    print("v{}: {}, distance={}".format(idx+1, vectors[i], distances[idx]))
    idx += 1

Faiss로 코사인 유사도로 검색하기

유클리디안 거리(Euclidean Distance)로 가장 가까운 벡터를 찾으면 특정 차원의 양적 수치에 따라는 거리가 가깝다고 판별되는 편향의 문제가 있습니다. 이게 문제가 될 때가 있고 그렇지 않을 때가 있는데 이것은 문제의 도메인에 따라 다릅니다. 그러니까 문제가 주어진 환경에 따라 그때그때 다르다는 뜻입니다.

이런 문제를 피하는 방법은 유사도를 계산할 때 거리측정 방법을 유클리디안 거리를 사용하지 않고 코사인 유사도를 사용해서 벡터의 방향이 가까운 것을 찾는 것입니다. 보통 검색엔진들도 이 방법을 기본으로 사용합니다.

Faiss도 이걸 지원하는데 예제는 아래 코드를 보시면 되고 앞서 설명했던 유클리디안 거리 기반의 검색과 다른 점은 index를 생성할 때 타입을 다르게 생성해야 하고 벡터를 노말라이즈 해줘야 한다는 것입니다. 벡터가 이미 노말라이즈되어 있다면 안해도 됩니다.

import faiss
import numpy as np
import random

# 코사인 유사도 (Cosine Similarity) 를 이용해서 가장 가까운 벡터를 찾으려면 몇가지를 바꿔줘야 한다.
# 코사인 유사도 (Cosine Similarity) 를 사용하려면 벡터 내적으로 색인하는 index를 만들면 된다.
# 코사인 유사도를 계산하라면 벡터 내적을 필연적으로 계산해야 하기 때문이다.

# 랜덤으로 10차원 벡터를 10개 생성
vectors = [[random.uniform(0, 1) for _ in range(10)] for _ in range(100)]
# 10차원짜리 벡터를 검색하기 위한 Faiss index를 생성
# 생성할 때 Inner Product을 검색할 수 있는 index를 생성한다.
index = faiss.IndexFlatIP(10)
# 아래는 위와 동일하다.
# index = faiss.index_factory(300, "Flat", faiss.METRIC_INNER_PRODUCT)

# Vector를 numpy array로 바꾸기
vectors = np.array(vectors).astype(np.float32)
# vectors를 노말라이즈 해준다.
faiss.normalize_L2(vectors)
# 아까 만든 10x10 벡터를 Faiss index에 넣기
index.add(vectors)
# query vector를 하나 만들기
query_vector = np.array([[random.uniform(0, 1) for x in range(10)]]).astype(np.float32)
print("query vector: {}".format(query_vector))
# 가장 가까운 것 10개 찾기
distances, indices = index.search(query_vector, 50)
# 결과룰 출력하자.
idx = 0
for i in indices:
    print("v{}: {}, distance={}".format(idx+1, vectors[i], distances[idx]))
    idx += 1

노트북 코드

위 코드의 노트북은 깃헙 레파지토리에 올려 두었습니다.

https://github.com/euriion/python-exams/blob/main/faiss/faiss-exam.ipynb

다음 번에는 기회가 되면 Faiss를 이용한 간단하고 빠른 추천 엔진을 만드는 예제를 올려보겠습니다.

미분류, 인공지능, 기계학습 ML/AI, 책 book, 통계

공짜책 – 케빈 머피의 새 기계학습 책

댓글 남기기

무료책입니다. 아래 링크를 방문하시면 됩니다.

https://probml.github.io/pml-book/book1.html

기계학습 서적의 저자로 유명한 Kevin Patrick Murphy의 새 책 이라고 합니다.

현재는 Draft 판과 Python 코드를 다운로드 받을 수 있습니다.

저는 아직 읽어 보지는 못했습니다만 목차만 살펴봤을 때는 다른 기계학습 서적과 대동소이한 구성으로 보입니다.

데이터마이닝 Data mining, 미분류, 알고리즘 Algorithm, 인공지능, 기계학습 ML/AI

CART – 결정 트리와 회귀 트리 Decision Tree and Regression Tree #1

댓글 남기기

결정트리(Decision Tree)인 CART 알고리즘에 대해 포스팅합니다.

제 계획대로라면 벌써 몇년전에 포스팅을 했어야 했지만 계획대로 되는 것은 언제나 그렇듯이 없습니다.

CART는 GBDT, Random Forest, XGboost, LightGBM 등의 트리계열 알고리즘의 근간이 되는 매우 중요한 알고리즘입니다. 요즘 트리 계열 알고리즘에서 가장 좋은 성능을 보이는 XGboost에게는 할아버지쯤 되는 알고리즘입니다.

CART에는 결정 트리(Decision Tree)와 회귀 트리(Regression Tree)라는 알고리즘이 2개 들어 있습니다. 한 개가 아닙니다. 그런데 둘은 거의 비슷하기 때문에 1개라고 봐도 무리가 없긴 합니다. 일란성 쌍둥이라고 생각하면 됩니다. CART는 Classification And Regression Trees의 약어인데 여기에도 분류와 회귀를 하는 트리라는 것을 알려주고 있습니다.

어쨌든 이 둘의 차이는 뒤에 설명하겠습니다.

알고리즘의 컨셉

알고리즘의 컨셉은 간단합니다. 학습 데이터를 해석해서 알아서 트리 구조를 자동으로 만든 다음 만들어진 트리를 이용해서 분류, 예측 문제를 해결하는 모델을 만드는 것입니다.

여기서 중요한 것은 트리를 자동으로 만든다는 것입니다. 트리를 사람이 만들어줘야 한다고 상상하시는 분들이 있는데 아닙니다.

분류 트리와 회귀 트리의 차이

분류 트리와 회귀 트리의 차이를 살펴보겠습니다.

결정 트리(Classification Tree)는 클래스(등급) 또는 레이블(표 딱지)을 예측하는 것으로 “남”또는 “여”, “예” 또는 “아니오”, “A”, “B”, “C” 와 같이 어떤 것인 맞추는 것(판별)이고

회귀 트리(Regression Tree)는 연속형 숫자인 1,2,3 123, 28.5와 같은 숫자를 맞추는 것입니다. 사람의 키를 맞춘다거나, 대출 상환 예상액을 맞춘다거나 하는 것(예측)입니다.

CART의 탄생

뭐든 그렇지만 자세한 설명 전에 역사를 조금 살펴보면 이해하는데 도움이 됩니다.

CART는 1980년대에 발표된 것으로 이제 나이가 들대로 든 알고리즘이지만 아직도 현역에서 많이 쓰입니다. 기계학습 알고리즘이 다들 독특한 면이 있긴하지만 CART도 상당히 독특한 기계학습 알고리즘입니다. 이 알고리즘은 학술상의 갈래로 보면 데이터마이닝 계열로 많이 분류됩니다. 비즈니스적인 결정을 과학적으로 해서 가치 창출얼 하기 위한 것. 그러니까 좋은 결정을 내리는 것을 자동화하기 위한 용도로 만들어진 것입니다.

만든 분들의 말에 의하면 통계 분석이나 문제 해결을 할 때 마다 회귀모델같은 통계 모델이나 여러 수리 모델을 매번 디자인하고 적용하는 것이 비효율적이라서 싫었다고 합니다.

데이터마이닝 계열이라고 했지만 이것도 기계학습 알고리즘이고 만들어진 원리를 보면 꽤 깊은 고급 통계 이론과 정보 이론이 함축되어 있습니다. 만만한 알고리즘은 아닙니다. 이 알고리즘의 저자들이 총 4명인데 통계학, 과학, 의학, 경제학, 컴퓨터 공학에 매우 뛰어난 석학들입니다. 이 알고리즘이 이런 분야에 고루 쓸 수 있는 다목적 도구라고 해석해 볼 수 있습니다.

CART의 저자와 논문

보통 알고리즘은 논문으로 많이 발표되는데 CART 알고리즘은 논문이 없습니다. 논문으로 발표된 알고리즘이 아니고 책으로 발표된 알고리즘입니다. 논문을 찾다가 논문이 없고 대신 책이라는 사실에 충격받았던 기억이 있습니다.

https://www.amazon.com/Classification-Regression-Wadsworth-Statistics-Probability/dp/0412048418

오래된 책인 만큼 표지가 매우 촌스럽습니만 아마존에서 아직도 판매하고 있습니다. 출판일을 보면 1984년 1월 출판이 첫판입니다.

CART의 저자들

앞서 말씀드렸듯이 책 표지에 있는 저자 4명은 모두 각 분야에서 상당히 유명한 분들입니다. 아래의 4명입니다.

  • Leo Breiman – University of California, Berkeley
  • Jerome H. Friedman – Stanford University
  • Richard A. Olshen – Stanford University
  • Charles J. Stone – University of California, Berkeley

책의 저자들까지 나열한 것은 위의 저자들 중에
Leo Breiman (레오 브라이먼)
Jerome H. Friedman (제롬 프리드먼)
이름을 굳이 외우실 필요는 없습니다만 이 두 사람은 알아두는 것이 기계학습을 깊이 공부하신다면 도움이 되기 때문입니다. 이 두 사람은 CART 발표 이후에 Random Forest(랜덤 포레스트)와 GBDT (Gradient Boosted Decision Tree), GBRT(Gradient Boosted Regression)를 만든 사람들입니다. 아마 기계학습을 조금이라도 공부하신 분들은 이 알고리즘들의 이름을 알고 있을 것입니다. 특히 랜덤포레스트는 너무도 유명하지요. 그리고 부럽게도 위키피디아에도 이 분들 이름이 등록되어 있습니다.

CART와 유사한 알고리즘

ID3, C4.5, C5.0 이라는 결정 트리(Decision Tree)알고리즘이 있습니다. 나열한 순서대로 개량된 버전인데 C4.5가 가장 많이 알려져 있습니다. CART와 유사하다고 하는데 동일한 시대에 발표된 것이지만 관련은 없다고합니다. 구조도 서로 비슷하다고 알려져 있습니다만 제가 이 알고리즘은 잘 알지 못합니다.

CART가 현재는 라이센스가 없이 무료인 반면 C4.5 구현체가 판매되었던 알고리즘이라서 사용자가 많지는 않습니다. 성능은 꽤 좋다고 하며 CART와 C4.5의 성능은 비슷하다고 알려져 있습니다.

CART의 개량형, 강화형

CART의 개량형, 강화형 또는 영향을 받은 것은 다음과 같은 것들이 있습니다.

  • Random Forest
  • Gradient Boosted Decision Tree / Gradient Boosted Regression Tree
  • XGboost
  • lightGBM
  • CatBoost
  • Isolation Cut Forest
  • Robust Random Cut Forest

앞서 말했듯이 요즘 각광받는 XGboost, lightGBM도 모두 CART 계열입니다. 현재 결정 트리 계열 중에 가장 주목받는 것은 lightGBM 입니다. 그래서 요즘은 CART를 사용하지 않고 바로 lightGBM이나 XGboost를 사용하는 경우도 많습니다. 다만 CART만 앙상블 모델이 아니고 다른 알고리즘은 모두 앙상블 모델입니다. 앙상블 모델은 여러 모델을 합쳐서 하나의 모델로 만든 것을 말합니다.

위의 알고리즘 중에서 저는 개인적으로 lightGBM을 매우 좋아합니다만 그 이유는 XGboost이 비해서 가볍고 범주형 변수를 지원하기 때문입니다. 자세한 얘기는 다음 기회에 하기로 하겠습니다.

Decision Tree와 Regression Tree의 차이

Decision Tree(결정 트리, 분류 트리)와 Regression Tree(회귀 트리)는 매우 유사합니다. Decision Tree가 남,녀와 같이 클래스 또는 레이블로 된 것을 분류해주는 Classification(분류) 문제 해결이라면 Regression Tree는 몸무게, 키, 확률 등의 연속형 수치값을 추정해주는 Regression 입니다.

참고로 Regression Tree에는 흔히 말하는 Linear Regression과 같은 회귀 모델이 들어 있지 않습니다. 연속형 값을 추정하는 것을 넓은 의미로 Regression(회귀)라고 하는데 Regression Tree는 종단 노드에서 평균을 사용해서 결과값을 추정합니다. 평균을 사용해서 추정하는 것은 넓은 의미에서 회귀라고 말 할 수 있습니다.

설명이 어려워졌는데 쉽게 말하자면 Regression Tree에서 말하는 Regression은 Linear Regression(선형회귀)나 Logistic Regression(로지스틱 리그레션)에서 말하는 그 회귀(Regression)이 아닙니다.

CART의 원리

복잡한 수식 같은 것을 적으려면 시간과 지면이 많이 필요합니다. 우선 원리만 적고 자세한 것은 나중에 업데이트하도록 하겠습니다.

cart algorithm에 대한 이미지 검색결과

CART 위와 같은 트리를 자동으로 만드는 것입니다. 위의 그림은 CART에서도 Decision Tree를 설명한 것인데 남 (Male), 여 (Female)를 구분하는 판별 모형을 만들때 입력 변수(Input variable, feature, 자질)인 키 (Height)와 몸무게 (Weight)를 이용하는 Decision Tree입니다.

입력 변수는 범주형 변수를 넣을 수도 있습니다. 만약 머리색을 입력 변수 중 하나로 추가해서 넣는다고 하면 Black, Brown, Pink 등과 같은 것이 됩니다.
출력 클래스도 남, 여가 아닌 남,여,모름 이렇게 3개 이상을 지정할 수 있습니다. 단 Decision Tree에 해당하고 Regression Tree는 안됩니다.

CART의 신비는 저 “트리를 어떻게 자동으로 만들어 주느냐”입니다.

이 다음 설명은 다음 편으로 짤라서 쓰겠습니다.

인공지능, 기계학습 ML/AI

앙상블 모델 – 배깅 Bagging

댓글 남기기

기계학습 부류. 분류(classification) 또는 예측(prediction)에서 여러 모델을 합쳐서 더 좋은 결과를 얻는 방법을 앙상블(Ensemble) 모델이라고 합니다.  앙상블 기법은 배깅(Bagging), 부스팅(Boosting), 스태킹(Stacking) 3종류로 나눌 수 있습니다. 
이 포스트에서는 우선 배깅(Bagging)에 대해서 설명합니다.

앙상블 모델을 배울때 보통 Bagging과 Boosting을 알게 되고 그 다음 Stacking을 생각하게 됩니다. 순서는 중요하지 않지만 기법들이 생각보다 많이  다르고 복잡함의 종류도 다릅니다. 그래서 한꺼번에 설명하기 어렵습니다.

앙상블 모델은 보통은 지도학습(supervised learning)에 사용됩니다. 군집화나 학습데이터가 없는 아웃라이어 감지(outlier detection), 어노멀리 감지(anomaly detection), 클러스터링(clustering) 같은 것에는 쓰기 어렵습니다.

비지도학습(unsupervised learning)에도 앙상블을 할 수 있다고 하는데 실제로 사례를 본적은 없습니다.

배깅 Bagging

배깅은 모델을 병렬로 연결해서 취합하는 방법입니다.
예를들어 결정트리(Decision Tree; 분류 나무)와 같은 알고리즘을 병렬로 연결한다고 하면 여러 개의 트리를 만들어서 결과를 취합합니다.  결합할 때는 다수결(Majority vote)를 쓸 수도있고 가중치(Weighted Majority Vote)를 쓸 수 있는데 기본으로는 다수결을 쓴다고 알려져 있습니다.

배깅의 대표적으로 알려진 알고리즘은 Leo Brieman이 만든 그 유명한 랜덤포레스트(Random Forest)가 있습니다. 이름이 랜덤포레스트인 이유도 배깅과 관련이 있기 때문입니다. 랜덤요소를 이용해 트리를 여러 개 만들고 합쳐서 숲을 만듭니다.

앙상블에서 모델을 몇 개를 결합할지는 보통 초매개변수(Hyper parameter)로 만드는 사람에 의해서 정해지게 됩니다. 결정트리를 앙상블로 결합하는 경우는 보통 100개 이상입니다.

배깅을 조금 구체적으로 설명하면 데이터로 입력값을 주면 Y 또는 N를 알려주는 트리모델을 결합해서 배깅으로 앙상블시키려고 하면 가지고 있는 학습데이터로 100개의 트리 모델을 만들고 실제로 판별에 사용할 때 입력을 100개의 트리모델에 주고 각 트리들이 Y과 N을 각각 던져 주면 그 중 많은 것을 답으로 취하는 방식입니다.  물론 이것은 아주 간단한 예이고 더 복잡하게도 변형이 가능합니다.

그런데 한뭉치의 학습데이터로 모델을 여러 개를 만든다고 했는데 어떻게 여러 개를 만드느냐가 의문입니다.
100개의 결정트리를 만들려면 학습데이터를 100등분해서 각각 만들면 되지 않을까라고 생각하겠지만 그렇게 나눌 양이 되지 않는 경우가 많고 학습 데이터가 부족해서 10묶음 교차검증(10 Fold Cross Validation)같은 것 까지 하는 판국에 학습데이터를 잘게 쪼개서 모델을 만들 여유가 없게 됩니다.
지도학습에서는 학습데이터의 양이 항상 문제입니다. 언제나 부족하다고 느껴집니다. 사회과학이나 의료같은 문제에서는 대량의 학습데이터를 얻기 어려운 경우가 많으니까요.  이미지 인식같은 종류의 자연과학 데이터로 부터 문제를 해결하는 딥러닝하고는 입장이 많이 다릅니다. 100등분을 해서 나눌 여유도 없고 그렇게 나누면 각각의 모형들이 편향이 생기거나 분산이 커질 여지가 많습니다.
그래서 학습데이터를 분할해서 모델을 각각 만든다는 것이 다소 비현실적인 경우가 많습니다. (다 그런것은 아닙니다)

적은 데이터로 모델을 여러개 만드는 방법은 배깅이라는 명칭을 풀어보면 알 수 있습니다.

배깅이라는 단어는 영어사전에서 찾을 수 있는 단어는 아니고 부트스트랩 어그리게이팅 Bootstrap AGGregING의 약어 입니다.

풀어서 보면 부트스트랩(Bootstrap)은 샘플을 다시 샘플링하는 것을 부트스트래핑(Bootstraping)이라고 하고 어그리게이팅은 그냥 취합한다는 뜻입니다.  즉 부트스트래핑 기법으로 학습데이터를 뻥튀기하는 효과로 여러개의 트리를 만드는데 사용하고 그 결과들을 취합합니다. 그것을 배깅이라고 부릅니다.

부트스트래핑은 통계학의 샘플링에서 매우 중요하게 다루는 개념 중 하나입니다. 어렵고 내용이 길어지므로 설명은 다음기회에 해보겠습니다.

부트스트래핑(뻥튀기)을 조금 더 쉽게 설명하면
10000개의 레코드로 된 데이터세트가 있다고 가정합니다.
10000개의 레코드를 10000번 복원추출(resampling)을 합니다. 그러면 갯수는 똑같이 10000개가 됩니다. 다시 이 과정을 반복해서 100번을 해서 10000개 짜리 데이터세트를 100개를 만들고 이 것으로 각 모델들을 만듭니다. 그러면 100개의 조금씩 다른 모델을 만들 수 있습니다.

“10000개에서 10000개를 표본추출(샘플링)하면 똑같은 것 아닌가?”
라고 생각할 수 있습니다.  또
“똑같은 것 100개를 만들어서 각각 모델을 만들면 다 똑같은 것 아닌가?”
라고 생각할 수 있습니다.
복원추출을 했기 때문에 안 똑같습니다.
복원추출은 영어로 리샘플(Resample)이라고 합니다. 가지고 있는 학습데이터가 모집단으로 부터 표본추출한 데이터라고 볼 수 있습니다. 즉 모집단에 대한 샘플데이터입니다.  
표본추출한 것을 데이터 갯수 만큼 복원추출을 다시 하게 되면 어떤 것은 같은 것이 중복해서 뽑히고 어떤것은 아예 뽑히지 않게 됩니다.  이것이 배깅의 효과인데 이게 무슨짓인가 싶겠지만 이렇게 표본을 다시 복원추출하면 원래 모집단의 특성을 더 잘 반영되도록 재구성되는 경향이 있다고 알려져 있습니다. (중심극한정리와 비슷해 보이지만 다른 것입니다)

이 특성을 이용해서 조금씩 다른 모델들을 만들고 그것들의 결과를 취합하는 것입니다. 
“데이터가 전부 비슷하니 결과도 별차이가 없겠네”
라고 생각할 수 있겠지만 데이터가 빼곡해지는 효과가 있고 조금씩 다른 모델들이 투표를 하는 방식이므로 배깅으로 만들어진 앙상블 모델은 결과들에 대한 편차가 크지 않고 안정적인 결과를 보여지도록 향상됩니다.
학습데이터가 원래 편향이 있다면 그로 인한 편향문제까지는 해결하지는 못하지만 미지의 데이터(Unseen data)에 상당히 괜찮은 성능을 보이고 노이즈나 아웃라이어에 대해서도 강해지는 것으로 알려져 있습니다.
실제로 단순한 트리모형과 랜덤포레스트 모델을 만들고 비교를 해보면 차이를 알 수 있겠습니다.

데이터마이닝 Data mining, 데이터분석 Data Analysis, 인공지능, 기계학습 ML/AI, 텍스트마이닝

유클리디안 거리 – Euclidean Similarity

댓글 12개

유클리디안 유사도라고도 하는데 원래 유클리디안 거리(Euclidean distance)라고 말하는 것이 맞는 것 같습니다. 유클리디안 유사도는 다소 이상한 단어의 조합이라는 생각이 듭니다. 하지만 유클리디안 유사도라는 말도 많이 통용되므로 이 포스트에서도 그냥 그렇게 하기로 하겠습니다.

유클리디안 유사도(Euclidean similarity)는 유클리디안 거리를 구해서 두 벡터의 유사도로 사용한다는 뜻입니다.

유클리디안 거리는 직선 거리다

유클리디안 거리는 기하학적으로 볼 때 두 점의 직선거리를 구하는 것입니다.  또는 선형대수에서 주로 다루는 벡터 스페이스(Vector space)라고 불리는 선형 공간에서도 동일하게 최단 거리를 구하는 것을 말합니다.

코사인 유사도를 설명할 때 언급한 적이 있습니다만 유사도는 2개의 데이터만 가지고 계산해서 결과값을 뽑아내도 그것만으로는 아무짝에도 쓸모가 없습니다.

세상에 사람이 둘 만 남았다면 두 사람은 서로 닮은 걸까요? 안 닮은 걸까요? 모릅니다.

유사도는 다음과 같은 방식으로 주로 사용합니다.

  1. 여러 개의 데이터에서 주어진 것과 가장 가까운 것이 어떤것인가?
  2. 여러 개의  데이터에서 가장 가까운 것들끼리 묶어보자

유클리디안 거리는 데이터마이닝이나 기계학습에 익숙하시다면 K-means (K민즈, K중심값, K평균 이라고 번역합니다) 같은 것에서 사용하는 것을 본 적이 있을 것입니다. 유사도라는 것이 사실은 거리를 측정하는 방법(distance measurement)일 수 밖에 없습니다. 거리를 측정하는 방법을 어떤 것을 쓰느냐에 따라 이름을 무슨 무슨 유사도 이렇게 “유사도”라는 단어를 붙여서 부릅니다.

유클리디안 거리 구하기

유클리디안 거리를 구하는 방법은 간단하고 매우 쉽습니다.
피타고라스 정리를 알면 됩니다.

직각삼각형의 빗변의 길이를 구하는 것입니다.

위키피디아를 보면 거기에 그림을 아래와 같이 넣어놓고 설명해 놨습니다.

간단 한 수식이 있지만 그림으로 보니 눈이 아프군요.

그림에서 p와  q의 유클리디안 거리는 p와 q의 직선거리를 구하면 되는 것이고 가운데 만들어진 삼각형이 직각삼각형이니까 피타고라스 정리를 쓰면 빗변의 길이, 즉 대각선의 길이를 구할 수 있습니다. 이 대각선의 길이가 유클리디안 거리입니다.

결론은 삼각형의 빗변의 길이를 계산하면 됩니다.

참고로 피타고라스 정리가 3차원 이사의 고차원에서도 되는 건지 헷갈릴 수 있겠습니다.  당연히 3차원 이상에서도 적용이 됩니다.  3차원, 4차원, 5차원, …, R차원 다 됩니다.

수학자들이 증명해 놓은 것이 있습니다. 그냥 믿고 쓰시면 됩니다.

5차원인 경우를 예를 들어서 설명하면
아래와 같이 2개의 5차원 벡터가 있다고 하고

a = (1, 2, 3, 4, 5)
b = (2, 3, 4, 5, 6)

벡터의 멤버수가 5개씩이므로 둘 다 5차원 벡터입니다.  차원이 다르면 안됩니다. 맞춰 줘야지요.

각각 차원(축)을 맞춰서 순서때로 빼준 다음에 제곱해서 더한 다음에 루트를 씌우면 됩니다.

1번째 차원: 1 – 2를 계산해서 제곱 = 1
2번째 차원: 2 – 3을 계산해서 제곱 = 1
3번째 차원: 3 – 4를 계산해서 제곱 = 1
4번째 차원: 4 – 5를 계산해서 제곱 = 1
5번째 차원: 5 – 6를 계산해서 제곱 = 1

다 더한 다음에 루트

sqrt(1 + 1 + 1 + 1 + 1)

답은 2.236068 입니다.

R코드로는 이렇게 하면 됩니다.

a_vector <- c(1, 2, 3, 4, 5)
b_vector <- c(2, 3, 4, 5, 6)

dist(rbind(a_vector, b_vector))

추가로 유클리디안 거리는 양적인 것을 기반으로 하는 것이라서 축의 스케일이 맞지 않으면 이상한 측정이 됩니다.  축의 스케일을 맞춰야 할지 말아야 할지는 그때 그때 다릅니다.

이런 말이 나오면 항상 골치만 아픕니다만 어쨌든 뭐든 쉽게 쓸 수 있는 것은 없는 것 같습니다.

예를 들면 이런 경우입니다.

a = (1, 2, 3000000, 4, 5)
b = (2, 3, 4000000, 5, 6)
c = (3, 4, 5000000, 6, 7)

3번째 차원, 3번째 축의 값에 의해 가장 큰 영향을 받습니다. 다른 차원의 값들은 구실을 못하게 됩니다.

기회가 되면 다른 포스트에 스케일을 맞추는 여러가지 방법도 적어 보겠습니다.