Skip to main content
edited tags
Link
Nikos M.
  • 2.4k
  • 1
  • 7
  • 11
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user

theThe following is from Understanding Machine Learning: Theory to Algorithm textbook:

Definition of PAC Learnability: A hypothesis class $H$$\mathcal H$ is PAC learnable if there exist a function $m_H : (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following property: For every $\epsilon, \delta \in (0, 1)$, for every distribution $D$ over $X$, and for every labeling function $f : X \rightarrow \{0,1\}$, if the realizable assumption holds with respect to $H,D,f$$\mathcal H,D,f$ then when running the learning algorithm on $m \ge m_H(\epsilon,\delta)$ i.i.d. examples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $L_{(D,f)}(h) \le \epsilon$.

  1. In the function definition $m_H : (0, 1)^2 \rightarrow \mathbb{N}$; what does a) 0 and 1 in the bracket, b) the integer 2, and c) $\rightarrow \mathbb{N}$ refer to?

Thank you!

the following is from Understanding Machine Learning: Theory to Algorithm textbook:

Definition of PAC Learnability: A hypothesis class $H$ is PAC learnable if there exist a function $m_H : (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following property: For every $\epsilon, \delta \in (0, 1)$, for every distribution $D$ over $X$, and for every labeling function $f : X \rightarrow \{0,1\}$, if the realizable assumption holds with respect to $H,D,f$ then when running the learning algorithm on $m \ge m_H(\epsilon,\delta)$ i.i.d. examples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $L_{(D,f)}(h) \le \epsilon$.

  1. In the function definition $m_H : (0, 1)^2 \rightarrow \mathbb{N}$; what does a) 0 and 1 in the bracket, b) the integer 2, and c) $\rightarrow \mathbb{N}$ refer to?

Thank you!

The following is from Understanding Machine Learning: Theory to Algorithm textbook:

Definition of PAC Learnability: A hypothesis class $\mathcal H$ is PAC learnable if there exist a function $m_H : (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following property: For every $\epsilon, \delta \in (0, 1)$, for every distribution $D$ over $X$, and for every labeling function $f : X \rightarrow \{0,1\}$, if the realizable assumption holds with respect to $\mathcal H,D,f$ then when running the learning algorithm on $m \ge m_H(\epsilon,\delta)$ i.i.d. examples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $L_{(D,f)}(h) \le \epsilon$.

  1. In the function definition $m_H : (0, 1)^2 \rightarrow \mathbb{N}$; what does a) 0 and 1 in the bracket, b) the integer 2, and c) $\rightarrow \mathbb{N}$ refer to?
Source Link
tkj80
  • 139
  • 3

PAC Learnability - Notation

the following is from Understanding Machine Learning: Theory to Algorithm textbook:

Definition of PAC Learnability: A hypothesis class $H$ is PAC learnable if there exist a function $m_H : (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following property: For every $\epsilon, \delta \in (0, 1)$, for every distribution $D$ over $X$, and for every labeling function $f : X \rightarrow \{0,1\}$, if the realizable assumption holds with respect to $H,D,f$ then when running the learning algorithm on $m \ge m_H(\epsilon,\delta)$ i.i.d. examples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $L_{(D,f)}(h) \le \epsilon$.

  1. In the function definition $m_H : (0, 1)^2 \rightarrow \mathbb{N}$; what does a) 0 and 1 in the bracket, b) the integer 2, and c) $\rightarrow \mathbb{N}$ refer to?

Thank you!