In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is there a way to generalize this idea for approximation algorithms? What I thought of:
Given a language $L \subseteq \{0,1\}^*$, a confidence parameter $\delta\in[0,1]$, an error parameter $\epsilon > 0$, and a distribution $D$ over $L$, the algorithm $A$ is a PAC algorithm for $L$ if with probability at least 1 - $\delta$ it holds that $\text{ERR}(A,D)\leq \epsilon$, where $\text{ERR}(A,D) := \Pr_{x\text{~}D}(A \text{ answers wrong on } x)$.
One drawback of this definition is the following: suppose $L$ is a countable infinite set, and let $l_1, l_2,...,l_k,...$ be some enumeration of the elements of $L$. Since $D$ is a probability distribution over $L$, $\sum_{i}D(l_i) = 1$, and hence there must be some index $k$ such that $\sum_{j>k} D(l_j) <\epsilon$.
The algorithm $A$ can be defined as: remember the answers of the first $k$ words. When receiving $w \in \{0,1\}^*$ check if $w$ is saved (and if so answer correctly). Otherwise, answer "0".
Clearly this algorithm is a PAC by the above definition, but not a clever one.
Is there a way to define PAC algorithm for a formal language? Or: can we use the theory of machine learning in the theory of approximation algorithms?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Welcome to CS.SE! What kind of generalization did you have in mind, and what did you mean by "approximation algorithms"? Also in your proposed definition, when you say "with probability at least $1-\delta$", what is that taken over? What is the random variable there? The condition $ERR(A,D) \le \epsilon$ is either true or false; I don't see anything random about that -- it doesn't look like an event that you can attach a probability to. $\endgroup$– D.W. ♦Sep 11, 2018 at 20:31
-
$\begingroup$ My intuition is the following: an approximation algorithm $A$ is an algorithm such that for every input $x$, $A(x)$ is "close to the real answer" - if this is an optimization problem, for example, then $A$ will return an answer which is close to optimum. I want to relax this definition and say something like "$A(x)$ may return an answer which is far away from the optimum, only if $x$ is a rare input". Trying to formalize this as I suggested leads to absurd: for any problem $L$ and distribution $D$, keep a table of "non-rare events". Is there a better way to formalize it? $\endgroup$– SomeoneHAHASep 12, 2018 at 18:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Approximation algorithms don't make sense here, because here the output of the algorithm is 0 or 1. (0 represents "the input is not in $L$", 1 represents "the input is in $L$".) Approximation algorithms are useful when the output is a continuous variable, as then we can ask for the algorithm to output something that is close to the correct answer, but the concept is not useful when talking about algorithms that output a boolean.
Also, in your proposed definition, once you have fixed an algorithm $A$ and a distribution $D$ over $L$, the condition $ERR(A,D) \le \epsilon$ is either true or false. It's not an event that you can assign a probability to. So, it doesn't make sense to ask it to hold with probability at least $1-\delta$.
