Answers.Body: <p>The size of a concept representation is important because the time to write/process this representation is a lower bound on the running time of the learning algorithm.</p>
  <p>For example, you can represent the boolean parity function with a circuit composed of <span class="math-container">$\land$</span>, <span class="math-container">$\lor$</span> and <span class="math-container">$\neg$</span> such that its size is polynomial in <span class="math-container">$n$</span>, while, if you used a disjunctive normal form (DNF) representation, you might need an exponential number of terms. <a href="https://www.cs.toronto.edu/%7Etoni/Courses/Complexity2015/lectures/lecture7.pdf" rel="nofollow noreferrer">This</a> may give you some intuition behind this example.</p>
  <p>For some concept classes, <span class="math-container">$\text{size}(c)$</span> is already bounded by a polynomial in <span class="math-container">$n$</span>, so the only practical requirement that you need in those cases is that the algorithm runs in time polynomial in <span class="math-container">$n$</span>. For example, if you consider the class of DNF with <strong>at most</strong> 3 terms, then you know that the number of literals is at most <span class="math-container">$3n$</span> (i.e. each term can contain at most <span class="math-container">$n$</span> literals, either <span class="math-container">$x_i$</span> or <span class="math-container">$\neg x_i$</span> but not both, for all literals <span class="math-container">$x_1, \dots, x_n$</span>).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-17T10:45:55.613Z
Answers.LastActivityDate: 2022-01-17T10:45:55.613Z
Answers.UserDisplayName: nbro
Body: <p>My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions.</p>
  <p><strong>Definitions:</strong></p>
  <p>Define the <strong>input space</strong> as <span class="math-container">$X_n = {\left\{ 0,1\right\} }^n$</span> and a <strong>concept</strong> <span class="math-container">$c$</span> as a subset of <span class="math-container">$X_n$</span>. For example, all vectorized images of size <span class="math-container">$n$</span> representing a particular numeral <span class="math-container">$i$</span> (e.g. '5') collectively form the concept <span class="math-container">$c_i$</span> for that numeral. A <strong>concept class</strong> <span class="math-container">$C_n$</span> is a set of concepts. Continuing our example, the vectorized numeral concept class <span class="math-container">$\left\{ c_0, c_1, \dots c_9\right\}$</span> is the set of all ten vectorized numeral concepts for a given dimension <span class="math-container">$n$</span>.</p>
  <p>As an extension to include all dimensions we define <span class="math-container">$\mathcal{C} = \cup_{n \geq 1} C_n$</span>. A <strong>hypothesis set</strong> <span class="math-container">$H_n$</span> is also a fixed set of subsets of <span class="math-container">$X_n$</span> (which might not necessarily align with <span class="math-container">$C_n$</span>) and we define <span class="math-container">$\mathcal{H} = \cup_{n \geq 1} H_n$</span>.</p>
  <p>The following definition of efficient PAC-learnability is adapted from <em>An Introduction to Computational Learning Theory</em> by Kearns and Vazirani.</p>
  <p><span class="math-container">$\mathcal{C}$</span> is <strong>efficiently PAC-learnable</strong> if there exists an algorithm <span class="math-container">$\mathcal{A}$</span> such that for all <span class="math-container">$n \geq 1,$</span> all concepts <span class="math-container">$c \in C_n$</span>, all probability distributions <span class="math-container">$D$</span> on <span class="math-container">$X_n$</span>, and all <span class="math-container">$\epsilon, \delta \in \left(0,1\right)$</span>, the algorithm halts within polynomial time <span class="math-container">$p{\left( n, \text{size}{\left(c\right)}, \frac{1}{\epsilon}, \frac{1}{\delta}\right)}$</span> and returns a hypothesis <span class="math-container">$h \in H_n$</span> such that <span class="math-container">$$ \underset{x \sim D}{\mathbb{P}}{\left[ h{\left(x\right)} \neq c{\left(x\right)}  \leq \epsilon\right]} \geq 1 - \delta.$$</span></p>
  <p><strong>Question:</strong></p>
  <p>Now, in the polynomial <span class="math-container">$p{\left(\cdot, \cdot, \cdot, \cdot \right)}$</span>, I understand the dependence on <span class="math-container">$\epsilon$</span> (accuracy) and <span class="math-container">$\delta$</span> (confidence). Additionally, I understand why the polynomial should depend on <span class="math-container">$n$</span> - the concept of learnability should be invariant to the time burden incurred from increasing the dimension of the input space (e.g. increasing the resolution of the image). What I do not understand is why the dependence on the size of the target concept (which I believe is usually taken to mean the smallest encoding of the target concept)?</p>
  
Tags: <machine-learning><computational-learning-theory><pac-learning>
Title: What is the relevance of the concept size to the time constraints in PAC learning?
UserDisplayName: OlimData
ThreadText: # What is the relevance of the concept size to the time constraints in PAC learning?
  
  (Asked by: username_0 on 2021-12-23)
  
  My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions.
  
  **Definitions:**
  
  Define the **input space** as $X\_n = {\left\{ 0,1\right\} }^n$ and a **concept** $c$ as a subset of $X\_n$. For example, all vectorized images of size $n$ representing a particular numeral $i$ (e.g. '5') collectively form the concept $c\_i$ for that numeral. A **concept class** $C\_n$ is a set of concepts. Continuing our example, the vectorized numeral concept class $\left\{ c\_0, c\_1, \dots c\_9\right\}$ is the set of all ten vectorized numeral concepts for a given dimension $n$.
  
  As an extension to include all dimensions we define $\mathcal{C} = \cup\_{n \geq 1} C\_n$. A **hypothesis set** $H\_n$ is also a fixed set of subsets of $X\_n$ (which might not necessarily align with $C\_n$) and we define $\mathcal{H} = \cup\_{n \geq 1} H\_n$.
  
  The following definition of efficient PAC-learnability is adapted from *An Introduction to Computational Learning Theory* by Kearns and Vazirani.
  
  $\mathcal{C}$ is **efficiently PAC-learnable** if there exists an algorithm $\mathcal{A}$ such that for all $n \geq 1,$ all concepts $c \in C\_n$, all probability distributions $D$ on $X\_n$, and all $\epsilon, \delta \in \left(0,1\right)$, the algorithm halts within polynomial time $p{\left( n, \text{size}{\left(c\right)}, \frac{1}{\epsilon}, \frac{1}{\delta}\right)}$ and returns a hypothesis $h \in H\_n$ such that $$ \underset{x \sim D}{\mathbb{P}}{\left[ h{\left(x\right)} \neq c{\left(x\right)} \leq \epsilon\right]} \geq 1 - \delta.$$
  
  **Question:**
  
  Now, in the polynomial $p{\left(\cdot, \cdot, \cdot, \cdot \right)}$, I understand the dependence on $\epsilon$ (accuracy) and $\delta$ (confidence). Additionally, I understand why the polynomial should depend on $n$ - the concept of learnability should be invariant to the time burden incurred from increasing the dimension of the input space (e.g. increasing the resolution of the image). What I do not understand is why the dependence on the size of the target concept (which I believe is usually taken to mean the smallest encoding of the target concept)?
  
  **Tags:** machine-learning, computational-learning-theory, pac-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-01-17. Score: 0
  
  The size of a concept representation is important because the time to write/process this representation is a lower bound on the running time of the learning algorithm.
  
  For example, you can represent the boolean parity function with a circuit composed of $\land$, $\lor$ and $\neg$ such that its size is polynomial in $n$, while, if you used a disjunctive normal form (DNF) representation, you might need an exponential number of terms. [This](https://www.cs.toronto.edu/%7Etoni/Courses/Complexity2015/lectures/lecture7.pdf) may give you some intuition behind this example.
  
  For some concept classes, $\text{size}(c)$ is already bounded by a polynomial in $n$, so the only practical requirement that you need in those cases is that the algorithm runs in time polynomial in $n$. For example, if you consider the class of DNF with **at most** 3 terms, then you know that the number of literals is at most $3n$ (i.e. each term can contain at most $n$ literals, either $x\_i$ or $\neg x\_i$ but not both, for all literals $x\_1, \dots, x\_n$).
  
  
  ---
  
  