Artificial Intelligence (8) 썸네일형 리스트형 Online learning Online learning이란 매 타임스텝마다 새로운 instance를 관측 후, 예측을 하고, 정답 label을 관측하는 프레임워크이다. Online learing에서는 정답과 다르게 예측하는 mistake의 갯수를 줄이는 것을 목표로한다. Online learning에서 learnability 를 알기 위해 mistake bound를 정의한다: Definition (Mistake bounds, [1]) Let $\mathcal{H}$ be a hypothesis class and $A$ be an online learning algorithm. Given any sequence $(x_1,h^*(y_1)),\dots,(x_T,h^*(y_T))$, $M_A(S)$ is the number of mis.. Online learning algorithms 1. Follow the leader algorithm 2. Follow the regularized leader algorithm 먼저 Regret을 어떻게 정의했는지 다시 생각해보자: $$\text{Regret}_A(\mathbf{w}^*,T)=\sum^T_{t=1}f_t(\mathbf{w}^{(t)})-\sum^T_{t=1}f_t(\mathbf{w}^*)$$ 1. Follow the leader algorithm Online convex optimization은 online learning에서 convex optimization 알고리즘을 이용하는 것이다. 그 중 대표적인 것이 Follow the leader algoirthm 이다 : $$w^{(t)}=arg\min_{w \in \mathcal{H.. Non-uniform learnability 이번 목차는 다음과 같습니다. 1. Non-uniform learnability 2. Strutural risk minimization 1. Non-uniform learnability Definition 1 (Non-uniformly learnable, [1]) A hypothesis class \( \mathcal{H} \) is non-uniformly learnable if there exist a learning algorithm, \(A \), and a function \( m^{\text{NUL}}_{\mathcal{H}} : (0,1)^2 \times\mathcal{H} \to\mathcal{N} \) such that for every \( \epsilon ,\delta \in (0,1.. PAC learning and uniform convergence 먼저 Agnostic PAC learnability를 소개하겠다. Definition 1. (Agnostic PAC learnability, [1]) A hypothesis class \( \mathcal{H} \) is agnostic PAC learnable if a learning algorithm has following sample complextiy \(n_{\mathcal{H}}:[0,1]^2\rightarrow \mathbb{N}\) : For arbitrary \( \delta,\epsilon \in (0,1) \) and for every distribution \(\mathcal{D}\) over \(\mathcal{X}\times\mathcal{Y}\), \( n \geq n_{\m.. VC-dimension 이번 글의 목차는 다음과 같습니다. 1. Growth function과 VC-dimension 2. $\epsilon$-net theorem and PAC learnability 1. Growth function과 VC-dimension Definition 1 (Growth function,[1]) Let \( \mathcal{H} \) be a hypothesis class. Then the growth function of \( \mathcal{H} \), \( \tau_{\mathcal{H}} : \mathbb{N}\to\mathbb{N} \) is defined as: \begin{align*} \tau_{\mathcal{H}} (m) := \max_{C\subset\mathcal{X}:|C|=m.. No free lunch theorem Universal algorithm이 있을까? Learning task란 sample $\{(\mathbf{x}_i,y_i ) \}_{i=1}^n$들을 generate하는 어떤 unkown distribution $\mathcal{D}$가 있을 때, $L_{\mathcal{D}}(h)$가 낮아지는 predictor $h$를 찾는 것이다. No free lunch theroem은 어떠한 learner에 대해서도 learnable하지 않은 distribution이 있다는 것을 보여준다. Theroem 1. [No free lunch theorem, [1]] Let \(A\) be any learning algorithm for the task of binary classification with respec.. Supervised Learning Terminology Instance Space : 가능한 모든 sample들의 집합 Hypothesis Space : 가능한 모든 가설들의 집합 - 예시 : 가능한 모든 정사각형 Empirical Error : 가설과 training set과의 error Generalization Error : Future Sample 까지 고려한 error but 알 수 없음 ( target concept이 무엇인지 모르므로?) Margin : Hypothesis 의 boundary 와 가장 가까운 instance 사이의 거리 - Margin이 큰 hypothesis? Or 작은 hypothesis? 어느게 더 좋은 것인가? Consistent(h,D) : Empirical Error가 zero이다. Most specific hypoth.. Parametric method - Regression 흔히 말하는 선형회귀에서의 Least Sqaure Method를 Maximum Likilihood Estimation 관점에서 보면 동일한 회귀식이 유도된다. 즉, 선형회귀 역시 주어진 Data Point가 관측될 확률을 높이는 Parameter를 찾는 Parametric method인 것이다. $y=w_1x+w_0$라는 식이 있다면 $w_1,w_0$가 parameter가 된다 Polynomial 식도 Linear Regression 관점에서 접근할 수 있다. $y=ax^2+bx^1+cx^0=az_2+bz_1+cz_0$ -multivariate (x가 vector) -multivariate polynomial 이전 1 다음