Difference between Supervised and Unsupervised Learning
.Supervised Learning: Predicts labels for new data using labeled datasets.
.Unsupervised Learning: Groups unlabeled data into clusters. Clustering is a representative model.
Clustering Models
.K-Means: Predetermines the number of clusters and iteratively adjusts centroids for optimal clustering.
.DBSCAN: Density-based clustering, identifying clusters based on density and effectively handling noise.
.Hierarchical Clustering : Agglomerative
< Clustering: Builds clusters by merging data points.
< Divisive Clustering : Starts with a single cluster and splits into smaller clusters.
Reinforcement Learning
.Learns optimal actions through trial and error to maximize rewards.
.The agent interacts with the environment (state observation → action → reward) to accumulate experiences.
.Balances exploration (new trials) and exploitation (optimizing existing knowledge).
.Solves dynamic decision-making problems using the Markov Decision Process (MDP).
머신러닝 군집
앞에서 설명한 지도학습의 분류classification는 레이블이 있는 학습 데이터를 기반으 로 분류를 위한 판별식을 만든 후 이 판별식을 이용해 새로운 미지의 데이터의 레 이블을 예측하는 것이다. 반면에 비지도학습은 레이블이 없는 데이터를 분류하는 것이기 때문에 현재 데이터세트를 같은 특성을 가진 그룹으로 묶는 데 그 목적을 두고 있다. 비지도 학습의 대표적인 모델이 군집Clustering이다. 군집 모델은 두 가지 주요 목적이 있다. 하나는 레이블이 없는 데이터세트의 요약 정보를 추출하는 것이고, 두 번째는 그러한 요약 정보를 통해 전체 데이터세트가 가지고 있는 특징을 발견하는 것이다. 군집 모델에는 평할Flat 또는 분할 기반의 군집partition-based clustering 기법과 계 층적 군집hierarchical clustering 모델이 있다. 분할 기반 군집 모델에는 k-means, k-medoids, DBSCAN이 대표적이다. 계층적 군집은 병합적 군집agglomerative clustering과 분할적 군집divisive clustering으로 구별된다. 군집 모델의 활용 분야는 매우 다양하다. 예를 들면, 앞에서 설명한 1850년대 영국 런던에 퍼진 치명적인 콜레라로부터 사람의 생명을 구한 존 스노 박사의 콜레라 오염 지도 역시 군집 모델 중 하나다. 최근에는 마케팅 분야에서 시장 및 고객 분 류 등에 활용되고 있으며, 페이스북과 같은 소셜 네트워크 서비스에서는 관심사가 같은 사용자를 위한 커뮤니티를 만들 때도 사용된다. 구글은 뉴스 서비스에서 같 은 주제의 뉴스들을 같은 카테고리로 묶어주는 데 군집 모델을 사용하고 있다. 링 크드인Linkedin은 최근 1억 개 이상의 잡 타이틀job title을 26개의 영역으로 분류하는 데 성공하면서 좀 더 정교한 광고를 통해 약 60억 원 이상의 광고 수익을 올렸다고 한다.
k-means 클러스터링
k-means는 레이블이 없는 데이터들을 군집화하는 가장 간단한 비지도학습 중 하 나다. K-means에서 다루는 레이블이 없는 데이터에서는 몇 개의 클러스터가 존 재하는지 모르기 때문에 분류할 클러스터의 수를 미리 정한다. k-means에서의 k 가 바로 클러스터의 개수를 의미한다. 분류할 클러스터의 수가 정해지면 각 클러스터마다 초기 중심initial centroid을 정한다. k-means에서 사용되는 중심centroid의 의미는 클러스터를 대표하는 가상의 레이 블이며그룹, 각 학습 데이터가 자신이 속한 클러스터를 결정하는 데 기준점이 된다. 초기 중심은 임의로 정해지며, 학습이 진행되면서 각 클러스터마다 최적의 중심으 로 이동한다. 최적의 중심을 구하는 것이 k-means 알고리즘의 핵심이다. 최적의 중심을 구하 는 개념은 매우 직관적이고 간단하다. 즉, 모든 데이터는 임의로 정한 k개의 초기 중심까지 거리를 계산하고 가장 가까이에 있는 중심을 자기 클러스터의 중심이라 고 생각한다. k개의 클러스터가 정해지면 각 클러스터에 속한 학습 데이터의 좌표 값 평균을 구해 이를 새로운 중심으로 정한다. 다시 모든 학습 데이터는 새롭게 정 의된 k개의 중심까지 거리를 계산하고 가장 가까운 중심을 자기가 속한 클러스터 로 정의한다. 이를 반복하면서 데이터가 클러스터의 소속을 바꾸는경우가 생기지 않으면 종료한다. 이를 알고리즘으로 표현하면 다음과 같다.
k-means 알고리즘
1. 클러스터 개수 결정(k=n) 후 임의의 중심 n개설정
2. 모든 데이터는 n개의 중심까지 각각 거리를 계산한 후 가장 가까운 중심을 자신의 클러스터 중심이라 고정함
3. 2각 클러스터마다 학습 데이터의 좌표값 평균을 계산한 후 이를 새로운 중심으로 설정
4. 새로 보정 후 이동된 중심을 기준으로 2, 3단계를 반복
5. 만약 모든 학습 데이터 중에서 자신이 속하는 클러스터를 변경하는 경우가 발생되지 않으면 학습 완료
DBSCAN 클러스터링
DBSCAN Density Based Spatial Clustering of Application with Noise2 은 k-means 방법과 같이 비 지도학습 모델이며, 이름에서 알 수 있듯이 노이즈 및 아웃라이어 데이터 식별에 강한 군집 모델이다.
DBSCAN이 제안하는 새로운 군집화 개념에 의하면 '밀도 있게 연결돼 있는density- '데이터 집합은 동일한 클러스터라고 판단한다. 여기서 '밀도 있게 연결돼 있다'라는 것이 DBSCAN의 핵심이며 k-means와 다른 개념이다.
k-means 모델에서는 모든 데이터들이 자기가 속한 클러스터를 정할 때 k개의 중 심으로부터 거리를 측정해 가장 짧은 거리에 있는 중심을 자신의 클러스터라고 정 하지만 DBSCAN은 일정한 밀도를 가지는 데이터의 무리가 마치 체인처럼 연결돼 있으면 거리의 개념과는 관계없이 같은 클러스터로 판단한다.
DBSCAN은 앞서 예시한 KNN, SVM, k-means 등과 같이 학습 데이터를 좌표공 간에 표시하는 것으로 시작한다. 좌표공간에 좌표점으로 표현된 각 학습 데이터는 그림 6.2와 같이 코어core, 경계border, 노이즈noise의 3가지 형태로 구분된다.
DBSCAN은 위 3가지 형태의 좌표점들을 다음과 같은 기준으로 정의한다. 기준을 정의하기 위해서는 DBSCAN에서 사용하는 '밀도'라는 개념을 설명할 필요가 있다.
밀도라는 것은 간단히 말해 자기를 중심으로 반지름 안에 있는 다른 좌표점의 개 수다. 예를 들면, 반지름 안에 자신을 제외한 다른 좌표점의 개수가 3이면 이 좌 표점의 밀도는 3이다. 그리고 DBSCAN에서는 어떤 좌표점이 클러스터를 형성할 수 있는 필요조건을 최소 좌표점 개수, MinPts로 정의한다. 즉, 어떤 좌표점의 밀도 가 최소 좌표점수 MinPts 이상이면 이 좌표는 클러스터를 형성할 수 있다.
이제 위에서 말한 세 가지 좌표점 형태를 정하는 기준으로 돌아가 보자. 만약 좌표 점 A의 밀도가 MinPts 이상이면 A는 코어라고 한다. 만약 좌표점 B가 코어 A의 영 영역반지름& 내부 안에 있고, B의 중심으로부터 반지름 8 내에 MinPts만큼의 점들이 존재하지 않으면 B는 A의 경계가 된다. 만약 좌표점 C는 코어 A 영역 안에 있지도 않고, C를 중심으로 반지름 8 내에 MinPts 미만의 점들이 있다면 C는 노이즈라고 정의한다. 이를 기호로 정리하면 다음과 같다.
DBSCAN 용어 정리
X : = 학습 데이터 전체 집합
ε : = 밀도 측정 반지름
MinPts : = 반지름 2 내에 있는 최소 데이터 개수
N(x) : = 데이터 X의 반지름 & 내에 있는 이웃 데이터(neighbor) 수
{x} : = 데이터 X의 반지름 & 내에 있는 이웃 데이터
X : = Xcore :만약 N(x)> MinPts VxEX
X := Xborder : 만약 X∈{Xcore}이고 N(x) <MinPts ∀ xex
X := Xnoise : 만약 X≠ {Xcore}이고 N(x) <MinPts ∀ xex
DBSCAN에서 군집화 과정은 코어가 중심이 된다. 어떤 학습 데이터가 코어로 정 의되면 주변의 이웃 데이터와 함께 하나의 레이블을 갖는 클러스터를 구성할 수 있다. 이후 반지름 내에 있는 이웃 점들을 차례로 방문하면서 각 점들이 코어인 지 아닌지 판단한다. 코어이면 앞서 진행했던 방법과 마찬가지로 재귀적으로 반복 하고 경계이면 진행을 중단한다. 이때 처음 방문한 점들은 방문 여부를 표시해서 중복 계산을 피한다.
이렇게 진행되는 기준을 밀도 접근성density-reachability 이라고 하는데, 이웃 점들이 코 어의 기준을 만족할 때만 그 이웃 점으로 확장해서 계속 군집화를 진행해가는 방 법이다. 즉, 군집화의 진행 과정은 코어 → 코어 → 코어. → 경계로 가는 방 향성을 띠며, 경계→ 코어로는 진행하지 않는다. 만약 이웃 점들이 코어가 없으면 학습 데이터 세트에 있는 다음 점으로부터 다시 시작한다. 새롭게 시작할 때는 새 로운 클러스터 라벨을 갖는다. 이러한 군집화 확장은 모든 점들이 방문이 완료되 면 중단하고 확보된 클러스터를 반환한다. 다음은 이를 알고리즘으로 표현한 것 이다.
DBSCAN 알고리즘
1. 밀도 반지름(e), 반경 내 최소 데이터 개수(MinPts) 정의
2. for EX EX do
3 X에 처음 방문했다면 방문했다고 표시
4. 만약 N(x) <MinPts 이면
5. X := 노이즈
6. 데이터 세트에 있는 다음 점으로 다시 시작
7. 만약 N(x) 2 MinPts 이면
8. X := 코어
9. X가 아직 소속 클러스터가 없으면 클러스터 C 할당
10. for x' E {x}에 대해 2단계 반복 do
계층형 군집 모델
계층형 군집Hierarchical Clustering 모델은 비지도학습의 여러 분야에서 다양하게 사 용되고 있는 군집 모델 중 하나다. 기본적인 개념은 유사한 특성을 지닌 데이터를 그리디greedy3하게 묶어 이진 트리 형태로 만들어 가는 방법이다. 이진 트리가 완성되면 이를 계통수dendrogram라고 한다. 계층형 군집 모델에서는 k-means나 k-medoids처럼 초기에 클러스터의 개수를 미리 정할 필요가 없다. 계층형 군집 모델에는 두 가지가 있는데, 그중 하나는 병합적 군집agglomerative clustering이고 다른 하나는 분할적 군집di divisive clustering이다. 병합적 군집은 상향식 군 집이라 하고, 분할적 군집은 하향식 군집이라 한다. 병합적 군집을 상향식이라고 하는 이유는, 군집 과정이 처음에 데이터세트의 모든 점을 군집의 원점으로 시작해 유사한 클러스터끼리 합쳐 나가면서 원하는 클러스 터 개수가 될 때까지 진행되기 때문이다. 즉, 최초에 모든 학습 데이터는 일단 자 기 자신이 하나의 클러스터가 된다. 자기 자신이 유일한 구성 요소인 클러스터다. 다음 단계로 각 클러스터는 다른 모든 학습 데이터를 검색해 자신에게 가장 근접 한특성이 유사한 데이터를 찾고 두 개의 데이터또는 클러스터는 하나의 클러스터로 묶인다. 그리고 위 작업을 동일하게 반복한다. 만약 클러스터의 개수가 하나가 되면 군집 과정을 완료한다.
병합적 군집 알고리즘
1. 모든 데이터를 단일 클러스터로 정의한다
2. 각 클러스터 간 유사성을 계산한다
3. 유사성이 가장 높은 두 개의 클러스터를 합한다
4. 2, 3단계를 (전체 클러스터 개수 = 1)이 충족될 때까지 반복한다
분할적 군집은 모든 데이터세트가 단일한 클러스터에 속한다고 정의하고 시작한 다. 분할적 군집은 병합적 방법과 반대로 가장 관련성이 없는 관계를 분리하는 작 업을 반복한다. 모든 클러스터의 크기가 1이 되면, 즉 클러스터가 단일 데이터 값을 갖게 되면 군집을 완료한다.
분할적 군집 알고리즘
1. 모든 데이터를 포함하고 있는 단일 클러스터를 만든다
2. 각 클러스터 간 유사성을 계산한다
3. 유사성이 가장 낮은 두 개의 클러스터를 분리한다
4. 2, 3 단계를 (전체 클러스터 개수 = 데이터 개수)가 충족될 때까지 반복한다
일반적으로 병합적 방법이 분할적 방법보다 직관적이고 간단하다. 또한 분할적 방 법은 상위 클러스터에서 잘못된 결정이 하위 클러스터로 파급되는 정도가 크다는 단점이 있다. 이러한 이유로 비 지도학습의 계층형 군집 모델을 사용할 때는 병합 적 군집 모델이 더 많이 사용되는 경향이 있으며, 이 책에서도 병합적 방법을 중심으로 계층형 군집 모델을 설명하기로 한다.
강화 학습
강화학습relloeetient Vesamine은 지도학습에 속한 모델로 분류하기도 하고 강화학습 자체의 독립적인 영역으로 분류하기도 한다. 지도학습으로 분류되는 이유는 학습 중에 사람으로부터 피드백, 즉 지도를 받기 때문이다. 한편 독립적으로 분류되는 이유는 강화학습이 가지고 있는 최적의 의사결정 프로세스가 치도학습의 대표적 인 방식인 레이블 기반을 통한 색을 구하는 방식과는 구별되는 학습 모델이 때문이다.
강화학습은 시행착오 과정을 거쳐 학습하기 때문에 사람의 학습방식과 매우 유사 하다. 이러한 이유로 혹자는 강화학습이 인공지능의 핵심이라고 말하기도 한다. 강화학습과 같이 시행착오를 통해 스스로 배우는 알고리즘이 고성능 컴퓨터에 이 식돼서 무궁무진한 디지털 데이터로 학습한다면 강인공지능 Super Artificial Intelligence의 출현도 결국 시간 문제일 듯하다. 구글 딥마인드가 설계한 알파고의 핵심 알고리즘도 강화학습을 기반으로 한다. 알 파고는 인터넷에 공개된 기보를 토대로 기본적인 바둑의 정석을 익힌 후 무수히 많은 시행착오를 통해 스스로 바둑을 학습했다. 그 결과 지금은 인간의 수준을 넘 어서는 기력을 보유하고 있다. 이번 장에서는 강화학습의 기본적인 개념과 강화학습에서 사용되는 대표적인 알 고리즘인 마코프 디시즌 프로세스MDP; Markov Decision Process를 가지고 몇 가지 적용 사례를 중심으로 설명하고자 한다. 이번 장에서 사용한 일부 강화학습 예제는 알 파고 개발을 주도했던 구글 딥마인드 수석 엔지니어인 데이비드 실버David Silver 박 사의 강의 노트를 참조했음을 밝힌다.
강화학습
지금의 강화학습 수준까지 오기까지 반세기 이상 오랜 시간이 소요됐는데, 여러 분야의 학문이 강화학습에 영향을 끼쳤다. 다양한 분야의 연구가 마치 퍼즐을 맞추듯이 연결되면서 강화학습에 필요한 알고리즘들이 완성돼 나갔고, 컴퓨터 성능의 비약적인 발전도 강화학습 발전에 큰 역할을 했다.
강화학습에서는 다른 인공지능 분야와는 구별되는 특이한 연구 분야가 있다. 어떤 의미에서는 이 분야가 강화학습의 가장 근간이 되는 학문이라고도 할 수 있다. 그 분야란 바로 행동심리학이다.
"Of several responses made to the same situation, those which are accompanied or closely followed by satisfaction to the animal will, other things being equal, be more firmly connected with the situation, so that, when it recurs, they will be more likely to recur; those which are accompanied or closely followed by discomfort to the animal will, other things being equal, have their connections with that situation weakened, so that, when it recurs, they will be less likely to occur. The greater the satisfaction or discomfort, the greater the strengthening or weakening of the bond. (Thorndike, 1911, p.244)"
미국의 심리학자 에드워드 손다이크Edward Thorndike는 “동물이 어떤 행동을 선택할 때는 강화된 사건reinforced event에 영향을 받는다”라는 '효과의 법칙Law of Effect'을 발표 했다. 이 논문이 발표될 당시에는 아직 인공지능이 탄생하기 훨씬 전이었지만 이 이론은 나중에 강화학습이 탄생하는 데 핵심적인 동인이 된다. 여기서 말하는 효 과의 법칙은 쉽게 말해 시행착오rial and error다. 지금도 사람과 동물은 수많은 시행 착오를 통해 학습해 나가고 있으며, 이러한 과정을 분석하는 행동심리 연구는 고 스란히 인공지능에 적용되고 있다. 인공지능 분야에 시행착오라는 행동심리학 이 론을 처음으로 컴퓨터 공학에 적용한 사람은 아마도 프린스턴 대학의 마빈 민스키 박사일 것이다.
그는 1954년 자신의 박사논문에서 이러한 이론을 기반으로 아날로그 컴퓨터인 SNARCStochastic Neural Analog Reinforcement Calculators을 설계했는데, SNARC은 쥐가 미로를 찾는 것을 시뮬레이션하는 컴퓨터였다. 이후 그는 1961년에 발표한 논문 『Steps Toward Artificial Intelligence』에서 시행착오 이론을 사용했는데, 이 논문 은 향후 강화학습에 많은 영향을 미쳤다.
시행착오 개념이 적용된 강화학습은 다음과 같이 요약할 수 있다. 에이전트agent는 환경environment으로부터 상태 state를 관측observation하고 이에 따른 적절한 행동action을 하면 이 행동을 기준으로 환경으로부터 보상reward을 받는다 (그림 7.2). 관측은 상 태로 변환된다. 에이전트는 이러한 일련의 '관측- 행동 - 보상' 상호작용을 반복 하면서 환경으로부터 얻은 보상을 최대화하는 태스크를 수행해야 하는데, 그 태스 크를 수행하기 위한 일련의 과정이 바로 강화학습이다. 여기서 '관측- 행동 - 보 상의 과정을 경험experience이라고도 한다.
에이전트가 빠른 시간 내에 주어진 환경에 존재하는 모든 상태를 파악하고 보상을 최대화할 수 있는 행동을 취하기 위해서는 소위 활용exploitation과 탐험exploration의 절 충trade-off 문제를 해결해야 한다. 행동은 우리가 가지고 있는 경험 중에서 가장 좋 은 것이 선택된 것이고 그러한 경험을 쌓기 위해서는 다양한 새로운 시도가 필요 하다. 즉, 새로운 시도를 해야만 우리의 경험이 풍부해지고 그러한 풍부한 경험은 더 나은 선택을 가능하게 한다. 여기서의 딜레마는 새로운 시도는 항상 기회 비용 이라는 위험이 동반된다는 사실이다.
제임스 마치James G. March2 는 활용과 탐험을 다음과 같이 정의한다. 활용은 정교화 refinement, 선택choice, 생산production, 효율efficiency, 선택selection, 구현implementation, 실행 execution 등의 의미가 있고, 탐험은 탐색search, 다양화variation, 위험 감수risk taking, 실 험experimentation, 놀이play, 유연성lexibility, 새로운 발견discovery, 혁신innovation 등의 의 미가 있다. 예를 들면, 식당을 고를 때 내가 가장 선호하는 식당을 가면 활용이고 새로운 식당을 찾아가는 것은 탐험이다. 만약 새로운 식당에 가서 좋은 기억이 있 으면 다음에 선택받을 수 있는 식당 중 하나로 '활용될 수 있다. 그렇지 않으면 한 번 더 좋은 식당을 갈 수 있는 기회를 잃게 되는 것이다.
강화학습을 구현하는 실무적인 관점에서 활용은 기억memory, 탐험은 탐색search으로 연관시킨다면 기억과 탐색의 결합은 강화학습의 핵심이라 할 수 있다.
강화학습에 핵심적인 공헌을 한 또 하나의 연구분야는 최적 제어optimal control 분야 다. 최적 제어는 1950년대 말에 등장한 이론으로 동적시스템dynamic system4의 효율 성을 최적화하는 조작장치 설계를 위해 시작됐다. 동적시스템 최적화 문제에는 시 간의 흐름에 따라 각 과정별 최적의 의사결정을 내리는 것인데, 미국의 수학자인 리처드 벨만Richard Bellman은 불연속적인 시간 문제에 대해 마코프 디시즌 프로세스 모델MDP을 도입해 이 문제를 해결했다.
이후 MDP는 공장 자동화에서 사용되는 동적시스템 최적화 문제를 포함해서 물 류/재고관리, 금융의 파생상품 설계, 방송통신에서 자원 할당 등 다양한 분야에서 이용되고 있으며, 특히 강화학습에서는 거의 독보적인 프레임워크framework로 자리 잡고 있다. 강화학습은 결국 MDP 문제를 푸는 것인데 효율적인 알고리즘을 찾는 것이 강화학습에서 주요 이슈다.
80년대 말까지는 리차드 벨만이 제안한 최적가치함수optimal value function 기반의 동 적 프로그래밍dynamic programming과 확률적인 시뮬레이션을 통해 의사결정을 내리 는 몬테카를로 방법 Monte Carlo methodo이 주류를 이뤘는데, 1988년 리차드 서튼Richard Sutton이 발표한 시간차 방법TD; temporal difference learning method이 위 두 가지를 결합하 면서 지금까지 가장 많이 인용되는 알고리즘으로 자리매김하고 있다.
책 제목 : 알고리즘으로 배우는 인공지능, 머신러닝, 딥러닝 입문
지은이 : 김의중
