15-859(B) Machine Learning Theory 02/27/08 * Computational hardness results for learning ========================================================================= Today: computational hardness results for learning plus some open problems. We saw before that if we are not concerned with computation time, then we can learn any class of function using a number of examples that is polynomial (actually, linear) in the number of bits to write down the target. But what happens when computation time enters the picture? HARDNESS RESULTS ================ Three kinds of computational hardness results in machine learning. (1) Representation dependent. Show that it's hard to find a low-error or near-optimal hypothesis in a given class. - E.g., it's NP-hard to determine whether a given dataset S is consistent with an intersection of 2 halfspaces. Same with 2-term DNF. (Reduction from hypergraph 2-coloring). This then implies it's hard to PAC-learn C by C since you could let D be the uniform distribution over S and use epsilon = 1/(|S|+1). - E.g., it's NP-hard to find the lowest-error OR-function on a given dataset. Same for linear separators. Even finding one of error < 49% under the assumption that there exists one of error 1% is NP-hard. These statements help explain why one expects to see local minima in neural nets, and why all algorithms for training a linear separator always end up minimizing something that is related to but not exactly the same as the "number of mistakes made". On the other hand, they are really talking more about the difficulty of finding the optimal member of some hypothesis class rather than the inherent difficulty of the target concept. For instance, given data consistent with a 2-term DNF, we can easily find a consistent 2-CNF. Big open problem: can you PAC-learn the class of "intersections of 2 halfspaces" using some *other* hypothesis representation. A possibly easier problem: the best approximation guarantee known for finding an OR-function with the fewest errors on a dataset is sqrt(n) [i.e., making sqrt(n)*OPT mistakes]. Can you beat that? (2) by restricting the way the algorithms can interact with the data. We'll see this soon when we discuss the Statistical Query model. These hardness results won't require complexity assumptions. The main drawback here is that it only applies to SQ algorithms. (3) Cryptographic-based hardness. Show that the class of functions contains cryptographic objects. E.g., show that any good learning algorithm would allow you to factor efficiently. These results are nice because they will apply without restricting the form of hypotheses. We are going to focus on hardness results of type (3) today. PRELIMINARIES: 4 learning models we will think about ==================================================== A) Standard PAC model, where h can be any poly-time computable function. B) Same as (A) but restrict D to be uniform on {0,1}^n C) Model (A) but give learning algorithm the additional ability to query target function f(x) on inputs x of its own choosing. These are called MEMBERSHIP QUERIES. They make most sense in contexts where you think of f as a device you want to reverse-engineer. So, algorithm can make MQs, and also see examples from D. Goal is to get low-error over D. D) Model (B) + Membership queries. Here you can think of querying as the *only* thing the algorithm can do, and goal is to find h that agrees with f on 99% of the points in {0,1}^n. Goal is to do learning in time polynomial in size of target function (recall that a "Concept Class" really is also a representation language. So, by "size" we mean size in that language.) Today we'll look at two results + mention some classic open problems. Let's start with the open problems. Some open problems ================== 1. Can DNF formulas be learned efficiently in model (A) or (B)? A very nice result by Jeff Jackson (in his CMU PhD thesis) showed how to learn DNF formulas in model (D). We'll see in a later class an algorithm for using queries to *weak learn* with respect to the uniform distribution. (Note: boosting doesn't *immediately* follow since this is for a specific distribution). Also, under crypto assumptions, it is known that model (C) is as hard as model (A). Intuitively, this is because of difficulty of SAT. (Being able to produce any interesting query at all.) Formally, assumption is the existence of digital signatures. 2. Can Decision Trees be learned efficiently in model (A) or (B)? Interestingly, you *can* learn DTs with queries in model (C). Will see that later. You gave an n^O(log(s))-time algorithm for model (A). 3. Can Monotone DNF be learned efficiently in model (B)? In model (A) they are the same as general DNF. In (B), you can weak-learn but no strong-learning algorithm is known. Best error rate known is 1/2 - 1/sqrt(n). Model (C) is easy (will see that later). Two hardness results for today: =============================== * Assuming factoring is hard, the class of Boolean Formulas (like DNF but not restricted to OR of ANDs -- you allow an arbitrary "formula tree") or equivalently, NC^1 (boolean circuits of logarithmic depth) is not weakly-learnable even in model (D). (Kharitonov) [eqivalence between NC^1 and BF will be on future hwk...] * Under the same assumption, DFA's can't be learned over arbitrary distributions without MQs (model (A)). Later in this course we will see an algorithm that learns them with MQs. Kharitonov's result =================== NC^1 is the class of O(log n) depth, bounded fan-in ciruits. The only fact about NC^1 we will be using is that you can multiply n n-bit numbers modulo an n-bit number. The key idea now is to try to use this power to encode some cryptographic function that is as hard as factoring. Convenient function: BBS pseudorandom bit generator: - Given N = p*q where p and q are primes congruent to 3 mod 4, and given a seed x_0, define x_i = x_{i-1}^2 mod N. b_i = LSB(x_i) - The generator outputs b_0, b_1, b_2, ... This generator has the property that if you could distinguish (I) an m-bit string produced by first choosing a random x_0 and then running the generator m times, from (II) a truly random m-bit string, then you could use this to factor N (in time polynomial in m and running time of your algorithm). In fact, all you need is an algorithm that "weakly distinguishes" them, in the "weak-learning" sense. The idea now is to try to show that for any given N, x_0, there must exist an NC^1 circuit C_{x_0,N} that on input i, produces b_i as output. Before showing that, let's see how that would imply what we want. First of all, define C_{x_0,N,t} to be the same as C(x_0,N) except that all but the last t input bits are hardwired to 0 (it only looks at the last t bits of input i). So, this is in NC^1 too. Now, the way we will use this in a hardness proof is like this: say that A is a proposed poly-time weak learner for NC^1. So, for some k, if the target has n gates, A uses at most n^k time/queries/samples and gets error at most 1/2 - 1/n^k. Now, say we are given an m-bit string that's either of type (I) or (II) above, for m = n^{3k}. What we do is use this as a lookup table. Given an input i, we look at the last 3k*lg(n) bits of i and output the corresponding position in our bit string. Now, since A only has n^k queries or samples, when it comes time for A to make a prediction on a new example, the probability that the new random example has the same suffix as something it has seen already is at most n^k/n^{3k} = 1/n^{2k}. So, if our bit string was type (II), then A would have probability at most 1/2 + 1/n^{2k} of getting it right. On the other hand, if our bit string was type (I), then we have been consistent with C_{x_0,N,3k*log(n)} and so A should have success probability at least 1/2 + 1/n^k. This is a weak-distinguisher and so you could factor. So, we just need to argue that we can make an NC^1 circuit that on input i computes: LSB( (x_0)^{2^i} mod N ) We will do this in two steps. First show how to compute j =2^i mod phi(N) and then how to compute (x_0)^j mod N. Unfortunately, we can't directly do repeated-squaring in NC^1. However, here is a trick. We first precompute 2^1, 2^2, 2^4, 2^8, etc., modulo phi(N), and store these values in the circuit. Then, given input i, we use i to tell us which of these precomputed values we want to multiply together modulo phi(N). Remember, we can multiply n n-bit numbers modulo another n-bit number in NC^1. The second step works the same way. We precompute x_0, (x_0)^2, (x_0)^4, (x_0)^8, ... modulo N, and use j to tell us which of these to multiply together modulo N. Can get statements about AC^0 too (constant depth, unbounded fanin) using stronger assumptions about hardness of factoring. --------------------------- Now, we can use this to show that DFA are hard to learn in the PAC model when you don't have membership queries. Idea: given an NC^1 circuit f over {0,1}^n, will create DFA g over {0,1}^m where m = n*2^{depth(f)}. Also will define a simple mapping r: x -> xxx...x. The DFA g will have the property that g(r(x)) = f(x). Also the number of states in g will be polynomial in m. -> first, how would you create a DFA for the function x_2 OR not(x_4)? This is easy. In fact, notice we can do this so that the DFA always ends up in either a specific accept-state A or a specific reject-state R,and we can get rid of self-loops if we only care about inputs of size n. -> Given a DFA for the function f1 and a DFA for the function f2, how to create a DFA for "f1 AND f2", assuming we're allowed to replicate the input? Just make f1's A state be f2's start state, and have f1's R state go through a chain of dummy states to f2's R state. Similarly for OR. So we double the length of the input needed each time we go up 1 level in the circuit. That's it. Notice that we have *not* shown that DFA's are hard to learn with membership queries (good thing too, since we are going to give an algorithm that learns DFAs using membership queries). The reason is that only queries of the form "xxx...x" actually map back to legal queries for the original NC^1 circuit. We have also *not* shown that DFA's are hard to learn over the uniform distribution on n-bit inputs. (This is a nice open problem).