개발블로그

하계 (Lower Bounds) 이번 챕터는 밴딧 알고리즘이 할 수 없는 일들에 대해서 다룬다. 우리는 지난 챕터에서 다룬 후회값 비율이 가능한 최적이라는 것을 내포하는 두가지의 근본적인 결과를 보여준다. 우리는 다른 어떠한 밴딧 알고리즘도 더 좋은 후회값을 얻지 못하는, 즉 모든 밴딧 알고리즘들에 적용 가능한 하계(lower bound)에 대해 관심이 있다. 우리는 이번 챕터를 전반적으로 $\Omega(\sqrt{KT})$ 하계를 증명하는데 사용한다. 그리고 우리는 종속적인 하계 $\Omega(log T)$를 정의하고 이것에 대해 다룬다. 이러한 하계값들은 어떠한 상계값이 얻을 수 있는 최적의 값인지에 대한 감각을 심어준다. $\Omega(\sqrt{KT})$의 하계는 다음과 같이 명시한다: Theor..

확률적 밴딧 1.5 참고 문헌 및 용어 정리 이번 챕터는 멀티암드밴딧에 폭넓게 유용한 몇가지 기법들을 소개한다. 이는 네가지 알고리즘 기법 (탐색-우선, 입실론-그리디, 연속적 제거, UCB기반 슬롯 선택), 분석을 위한 완전이벤트 기법, 그리고 수식 (1.12)에 설명한 UCB 트릭이다. 연속적 제거는 Even-Dar et al. (2002)에서, $UCB1$는 Auer et al. (2002a)에서 소개되었다. 탐색-우선과 입실론-그리디는 매우 긴 시간 동안 알려져 왔고, 이들은 최초의 언급자에 대한 부분은 명확하지 않다. 최초의 $UCB1$ 버전은 다음과 같은 신뢰 반경을 가졌다. $r_t(a) = \sqrt{\alpha \cdot \frac{ln(t)}{n_t(a)}}$ (1.14) $\alpha..

확률적 밴딧 1.4 초기 정보를 가진 밴딧 문제에 대한 정보가 알고리즘에게 먼저 알려질 수 있고, 이는 알고리즘의 성능을 개선하기 위해 사용될 수 있다. 이러한 "초기 정보"는 평균 보상 벡터 $\mu$에 큰 도움을 준다. 초기 정보를 부여하기 위한 두가지 일반적인 방법이 있다: $\mu$에게 "얌전함"(well-behaved)을 강요하는 것, 그리고 베이지안(Bayesian) 사전 확률을 부여하는 것이다. 중요한 후회 범위를 가지는 어떤 모델들은 슬롯의 숫자에 영향을 받지 않고, 따라서 무수히 많은 슬롯을 수용할 수 있다. $\mu$에 얌전함을 강요하는 것 정석적인 모델은 다음과 같다. 슬롯은 $\mathbb{R}^d$ 내의 포인트들과 일치한다. 우리는 $\mu$를 각 슬롯을 알맞는 평균 보상에 연결하..

확률적 밴딧 1.3 적응적 탐색 탐색-우선 기법과 입실론-그리디 기법 모두 탐색 스케쥴이 관측된 보상의 기록과는 관계 없다는 큰 결점이 존재한다. 하지만 탐색시에는 관측된 보상에 적응적으로 대응하는 것이 보통은 더 좋은 결과를 낸다. 비공식적으로, 우리는 "적응적"과 "비적응적" 탐색으로 분리한다. 이번 챕터에서 우리는 적응적 탐색을 구현하고 더 나은 에이전트를 얻기 위한 두가지 알고리즘을 소개한다. $K = 2$의 경우부터 시작해보자. 한가지 자연스로운 아이디어는 둘 중 하나의 슬롯이 다른 슬롯보다 더 월등하다는 것을 찾을때 까지 하나씩 번갈아하며 선택하는 방법이다. 하지만 우리는 어떻게 하나의 슬롯이 다른 슬롯보다 월등하다는 것을 정확하게 정의할 수 있을까? 1.3.1 완전이벤트와 신뢰범위 이전에 다..

확률적 밴딧 1.2 균등한 탐색 간단한 아이디어로부터 시작한다: 이전에 관측된 결과가 무엇이든 슬롯을 균등하게(같은 비율로) 탐색(explore)하고, 경험적으로 최적의 슬롯을 활용(exploit)한다. "탐색-우선"으로 알려진 이 알고리즘은 첫 라운드 들을 탐색에 집중하게 하고, 나머지 라운드들을 활용에 사용한다. 알고리즘 1.1: 매개변수 N을 사용한 탐색-우선 알고리즘 1. 탐색 단계: 각 슬롯을 $N$번 선택에 시도한다; 2. 가장 높은 평균 보상을 주는 슬롯 $\hat{a}$를 선택한다 (동점시에는 임의의 선택을 따른다); 3. 활용 단계: 슬롯 $\hat{a}$를 나머지 모든 라운드에 사용한다. 매개변수 $N$은 미리 선정된 값이다. 추후에 이 값은 시간수평선 $T$와 슬롯의 수 $K$의 함수..

확률적 밴딧 이 챕터는 가장 기본적인 형태의 멀티암드밴딧인 IID(identically independently distributed, 독립적이고 동일하게 분포된)의 보상을 가진 밴딧에 대해 다룬다. 우리는 몇가지의 알고리즘을 소개하고, 해당 알고리즘들의 성능을 후회값(regret)으로 분석한다. 이 챕터에서 소개된 개념들은 기본적인 모델에 이어 이 책의 모든 부분에 적용된다. 1.1 모델과 예제 우리는 확률적 밴딧(stochastic bandits)이라 불리는, IID의 보상을 가진 기본적인 모델을 살펴본다. 이 알고리즘은 알고있는 숫자 $K$와 $T$에 대해 $T$개의 라운드 동안 $K$개의 가능한 행동(arm, 슬롯)이 선택 가능하도록 주어진다. 각 라운드에서 이 알고리즘은 어떤 슬롯에서 보상을 수..

데이터사이언스 표본 (sample) 대개의 경우 모집단을 정확하기 알 수 있는 길은 없다. 또한 모집단을 정확히 밝혀낸다고 해도, 크게 의미있는 결과를 얻어내는 것은 드물것이다. 따라서 분석이나 추론을 할 때, 모집단을 잘 반영한 표본집단을 추출한다. 추출된 표본은 편향을 최소화하여 모집단을 잘 반영해야만, 실제 분석과 추론이 효과적으로 이루어질 수 있다. 표본(sample)이란 큰 데이터의 집합으로부터 추출한 더 작은 데이터의 집합이다. 모집단(population)이란 표본이 추출된 큰 데이터의 집합을 말한다. 표본추출 (sampling) 표본을 추출할 때 중요한 것은 표본이 모집단을 잘 반영해야 한다는 것이다. 이를 통계적 대표성이라고 하는데, 대표성을 띄지 못하는 표본을 표본편향(sample bia..

데이터사이언스 기술통계(Descriptive Statistics)란 데이터를 통계적으로 설명할 수 있는 기법들을 말한다. 많은 경우 분석에 사용될 데이터는 많은 양의 데이터를 포함하고 있기 때문에, 이를 간단하게 설명해주고 데이터의 집합의 특성을 알아낼 지표가 필요하다. 이 때 가장 기초적으로 사용되는 대표값 들을 사용해 설명하는 것이 기술통계이다. 경향성 데이터의 경향성을 살펴보기 위한 가장 기초적인 값들은 다음과 같다. 이들은 기초적인 대표값들인 동시에, 데이터를 특정 방법으로 요약하는 값들이기도 하다. 이러한 값들은 또한 측정지표(metric)이라고도 불린다. 평균 (mean, average) 모든 값의 합을 갯수로 나눈 값. 통상적으로 평균은 그리스어 $\mu$로 표기된다. 각 데이터를 $x$, ..

데이터사이언스 데이터란 현실에서 수집 가능한 모든 정보의 집합을 말한다. 기존에는 데이터(data)와 정보(information)를 나누어, 가공되기 전의 상태를 데이터, 가공후의 상태를 정보라고 지칭하였다. 하지만, 빅데이터의 영향으로 데이터 자체가 의미를 갖는 상황이 생겨났기 때문에, 최근에는 두가지를 분류해서 정의하지 않는다. 데이터의 종류 데이터분석에서 활용되는 데이터는 둘로 나뉜다. 정형데이터와 정형화되지 않은 비정형데이터이다. 정형데이터 정형화된 데이터란 우리가 흔히 알고있는 테이블로 표현 가능한 데이터이다. 대개는 한번의 정제 과정을 거쳐 테이블(데이터베이스)로 적제 되거나, 개발자나 DBA가 정의한 스키마로 저장될 수 있도록 유도된다. 비정형데이터 비정형데이터란 정형화되지 않은 모든 데이터..

강화학습 패키지 설치¶ 다음 코드는 세가지 패키지가 선행 되어야 합니다. sudo apt-get install ffmpeg pip install gym pip install gym_minigrid gym.render() 코드가 에러를 발생할 경우, 다음 패키지를 설치하고: sudo apt-get install xvfb 주피터 노트북을 다음 명령어를 통해 실행합니다: xvfb-run -s "-screen 0 1400x900x24" jupyter notebook In [1]: import warnings; warnings.filterwarnings('ignore') import numpy as np import pandas as pd import random import gym import matplotli..