전체 글 (144) 썸네일형 리스트형 Sigma-algebra Sigma-algebra의 간단한 예시들을 살펴보겠습니다. Example 2.3) $\mathcal{A}:=\{ A\;\text{or}\;A^c\;\text{is countable}\}$. $ (\cup_i A_i )^c \subset A_{i_0}^c $. 따라서 $A_{i_0}^c$가 countable하므로, $\cup_i A_i \in \mathcal{A}$이다. Example 2.6) Let $X=[0,1]$ and $B_1,\dots,B_8$ be subsets of $X$ which are pariwise disjoint and whose union is all of $X$. Let $\mathcal{A}$ be finite unions of $B_i$'s and empty set. Then .. Subspace topology 이번에는 Subspace topology에 대해 알아보겠다.Definition (Subspace topology, [1]) $X$가 topological space with topology $\mathcal{T}$라고 하자. $Y$가 $X$의 subset이면, the collection$$\mathcal{T}_Y:=\{ Y \cap U \mid U \in \mathcal{T} \},$$is a topology on $Y$, 이고 이것이 subspace topology이다.즉, subspace topology는 original topology의 open set들과의 intersection으로 정의된다. Subspace topology $\mathcal{T}_Y$도 topology가 된다는 것을 알 수 있.. 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.. 이전 1 2 3 4 5 ··· 18 다음