A Negative Comment on Negations

src

Michael I. Jordan of the University of California, Berkeley, is a pioneer of AI that few outside of his field recognize. “He’s known as the Michael Jordan of machine learning,” quips Oren Etzioni, director of the Seattle-based Allen Institute.

Today, Ken and I discuss some linkage between machine learning and computational complexity theory.

The quip by Etzioni runs longer—see this. The Allen Institute’s Semantic Scholar project aims to achieve content-based associative search for academic publications, so one can search for X that are close to a topic Y you have defined. They created an “influence graph” for millions of academic publications that goes well beyond citation counts. The graph’s most influential computer science paper was one by Jordan.

Neither Jordan has ever worked in complexity theory. Somehow, I thought the above is relevant to complexity theory. It got me thinking about MIJ and his connection to machine learning (ML). This is connected to complexity theory again, and so

My thoughts converged on how the notion of monotone plays in both fields. Influence strikes us as naturally monotone—“negative influence” is still influence—and building the graph is a kind of positively weighted transitive closure. Many ML algorithms work by monotonically increasing an objective function, such as expectation-maximization as expounded by MIJ. Non-monotone components such as negative (inhibiting) neural links and line–search add-ons to gradient descent are employed, but when and to what extent are they critical? We think negation is critical in complexity theory, but maybe not so much. Here are my thoughts.

Upper Bounds and Lower Bounds

Complexity theory is all about how hard is it to solve some problem. How hard is it to decide if a number is a prime? How hard is it to find a factor of a composite number? How hard is to color a graph with three colors? And so on.

There are two issues:

Upper Bounds Find an algorithm for the problem that is more efficient in some manner. Often in number of steps, but can be in other measures of complexity like memory used or amount of randomness and so on.

Lower Bounds Show that no algorithm for the problem is more efficient in some manner. For example, show that no algorithm can solve the problem is fewer than a certain number of steps.

The first is an problem; the second is a . An upper bound is proving there exists an algorithm that is efficient enough. You job is to present an algorithm that solves the problem. A lower bound is proving all algorithms that solve the problem, must take more steps than allowed.

There is something about that is fundamentally simpler than . An upper bound requires you to design an algorithm that works in some clever manner. The algorithm must exploit some trick about the problem that is powerful. For example to decide if a number is a prime, do not try all possible factors. Rather use a key consequence of a number being a prime: use the value of the number raised to a high power.

The lower bound requires you to show that there is no algorithm that operates more efficiently that a certain bound. You must show that being too fast, for example, makes you wrong.

Negations

One approach to lower bounds is via Boolean complexity. The idea is that any computation can be done with , , and . But, if we leave out , some computations cannot be done. However:

Suppose that you wish to show that something cannot be computed efficiently. An obvious first step is to explain what operations are needed to compute it at all. Once you fix on operations that are enough, you can then focus on the question of whether the given operations can efficiently compute it.

Suppose you wish to show that it will take a long time to get from A to another location B. How can you prove this? You might measure how long the distance is between A and B. Then if you know that you must drive a car from A to B, a lower bound is simple: How fast can the car go at maximum and argue that the time is therefore at least

Here M is the maximum speed the car goes.

Suppose that Distance is miles and the car can go at most miles per hour. Then a simple calculation is that it must take at least

Of course it could be higher if sometimes you go slower—perhaps you have to stop now and then for traffic lights.

Monotone Circuits

There are many theorems like this:

Theorem 1 Any monotone circuit that computes correctly has size at least exponential in .

These theorems are often hard to prove and require clever methods, but there are now tons of them. The field of complexity continues to extend and refine these theorems.

This feeds in to the approach of showing via Boolean circuit complexity. That is, to show that for some particular -complete problem, any Boolean computation for it requires a super-polynomial number of gates. A big idea is to build off the monotone lower bound results by moderately adding negation.

But there is a big issue: it takes only order negations to make the results fail. We covered some recent attempts by Norbert Blum to make this kind of idea work, but they do not seem to have established a new base camp for this approach, beyond previously–known results and more–recent advances.

This failure led many to think that negations are somehow the “final frontier.” But we do not agree with this either. We feel that negations are not the critical issue.

The Slice Issue—Again

The key is the concept of slice. A slice of is a subset that has all the elements the same weight. That is, its member binary strings have the same number of s.

There are many theorems like this:

Theorem 2 Any monotone circuit that computes correctly has size polynomial in . Provided it only need work on some slice of .

For a simple insight, suppose we want to say that a given bit of a string is . If we are promised that belongs to a slice with s, then we can do this with a monotone function: one saying that bits and collectively have at least s.

For an example of how slices show that negations cannot be the issue, consider factoring of bit numbers. This requires perhaps super polynomial size circuits. But note that if we fix factoring to -bit numbers that have ‘s, say, then it becomes a function on a slice. And it is easy to see that a computation without any negations is at most order bigger. Thus negations cannot be the secret to factoring. This is the key insight.

We still have not said anything new. This insight says that strong lower bounds on monotone complexity for slice functions will give lower bounds for general circuits. But we still do not know how to get such bounds. We have shifted around the side of the mountain, but the resulting “Slice Gap” seems to block ascent as before.

Climbing Mount ML

This is what has me thinking about whether machine learning can supply new insight.

Here is a simple old story of what I mean. One of the limits on the simple neural model of perceptrons that was shown a half-century ago by Marvin Minsky and Seymour Papert is that they cannot compute the binary XOR function. This led people to expect that small assemblages of perceptrons would be similarly powerless. But it only takes three layers of perceptrons to compute XOR. The point is, a small control structure over monotone can replace the free use of negation.

To go deeper—into deep learning for instance—we’ve peeked at the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David. The latter we know for some work on Boolean circuits and P=NP. The nub is more easily approached via a 2014 talk by the former, titled “On the Computational Complexity of Deep Learning,” and his 2016 followup. One point is that “theoretically weak” structures perform well when requirements of worst-case correctness and realizability are lifted—and the details make us wonder about possible parallels to the case of slices. The point also prompts us to ask:

What control structures, or intermediate operations short of full negation, create practically powerful algorithms that are still theoretically nearly as weak as monotone? Can researching them help us close the gap on lower bounds?

To go wider, it seems that both we humans and ML algorithms perform well at many tasks using largely monotone components. Can they help give an account relevant to complexity of what power necessarily comes from non-monotone components? We note caveats expressed by MIJ in a much-noted 2014 interview for IEEE Spectrum about generalizing from brain function to ML practice, but our intent is to look for particulars.

Open Problems

Can machine learning help us understand the power of monotone functions?