Tayzwi

In my last post on heuristics and approximation, I asked the question - Given realistic scale and scope, how does the human brain solve such problems (like question-answering)? Does the brain map everything to combinatorial optimization? Can its modus operandi be applied to automated systems so that they solve our problems.... - which leads to further interesting exercises in intellectual masturbation.

Combinational Optimization is about finding the optimal (best/worst) candidate (based on certain acceptable parameters) among all possible options. A large category of problems can be mapped to combinatorial optimization, and most of these are NP-hard. This means that most of them do not have efficient solutions.

But we see humans, with some training and experience, solve many combinatorial optimization problems efficiently using heuristics and instinct. Chess, Go, Sudoku, etc., come into mind. In these games, the human has to search the solution space efficiently to find the correct board/grid position. And we know that humans do not do a brute force search. There is some internal process that short-circuits the search.....somehow.

Now, this somehow-situation could be explained by the following possibilities:

1. The human brain has a clever technique to narrow search space, and come up with exact solutions. This would mean that P==NP, and computer scientists still haven't found a proof for this. A proof of this would simply be an efficient way of solving one of the NP-hard problems (which, according to this bullet, the human brain is doing right now). We just need to know this purported technique formally to claim P==NP. This situation is highly unlikely because computer scientists have been trying since 1960s to find such a procedure in vain. Of course, their fastidious nature is also making them look for a proof that such an efficient procedure cannot exist (P!=NP). Whether the latter will be proven, or whether the question itself is beyond answer - only time will tell. But the former is very unlikely to be true.
2. The human brain has come up with incredibly clever heuristics that approximate the search for the exact solution, and give us only approximate solutions. But these are so good, that they look exact almost always. But the fact that Kasparov got defeated by a computer shows that his heuristics used for chess were not infallible, and the computer's brute force search was much better (after all chess is played on a 8X8 board). Go and Bridge players still kick the machine's ass because of their games' bigger search spaces. This seems to be our Winston Wolfe (see Pulp Fiction) for the somehow-situation.
3. The outlandish situation that my romantic mind wants to use to model itself is a trifle too....er....outlandish. Let me get there. It is known that Factoring a large number into its factors is a computationally hard problem. Its unlikely that a clever technique exists to find exact factors without going through brute force division. But Peter Shor, in 1994, proved that quantum computers can solve the Factoring problem efficiently! Now, quantum computers are still theoretical models which might never get built. Shor and co. coming up with algorithms that work on them motivates physicists and engineers to hopefully come up with a working model of the quantum computer in the future. Now, my outlandish conjecture is that the human brain already has a quantum computer like mechanism built into it, which enables it to solve certain combinatorial problems quickly. Modern physics accepts the reality of quantum mechanical concepts like superposition, etc. in nature. Why is it not possible that such features already physically exist in our brains, and this quantum computing brain is solving problems using quantum algorithms? Is the human brain a realistic quantum computer? Ummmm.....

Its quite possible that a combination of these situations might exist in reality, and there might be more such parameters that actually govern the way we think. Will we ever truly understand ourselves scientifically? or in the end, is it going to be just spiritual enlightenment about the Self? How anti-climactic would that be.

Anti-climax won't do. We need 'em real. That was a long session. Now for the money shot. [insert appropriate onomatopoeia here, in uppercase]

Labels: computer science

Given a problem, we can:

1. Give efficient methods to find exact solutions. When this is possible, all's well. But alas, this is not possible all the time.
   
2. Give inefficient methods to find exact solutions (brute force), and bemoan that P != NP (mostly).
3. Propose intuitively appealing heuristics that are quick, and give "mostly good" results in practice, and hope that the malicious worst case input which can tear the heuristic apart never comes about.
   
4. Prove theoretical approximation guarantees about these heuristics so that even in the worst case, the heuristic won't go bad beyond some known bound.

Personally, I am fascinated by #4. Most current large scale problems rely on #3, which hopefully will get elevated to #4 in a few years time, and theoreticians will tell the practitioners - "Yeah, your heuristic will never give a solution that if off the optimal by 200%." As a budding researcher, is it better to build simulations, concrete systems, models, etc., and show empirically that certain heuristics work most of the time? Or is it better to take some small heuristic and prove without doubt its effectiveness under all circumstances?

The latter appeals to me because of its no nonsense, matter of fact, precise nature. But I can also see how we cannot do without the former. The former (heuristics) gets built to tackle real world problems. Theoreticians follow up later by giving provable approximate guarantees for these heuristics. Combinatorial optimization is rife with this pattern. What about other heuristics though?

Take the everyday example of Question Answering. Given a question, and an essay that might contain the answer to the given question, a reasonably educated person can extract an answer without much difficulty. But this simple task is extremely hard for an automated system. It can manage questions of the type: "how much," "what," and "when"; but will get flummoxed by questions of the type: "why" and "how". Practioners in the area of Natural Language Processing come up with heuristics that attempt to answer these tough questions, but there is no provable guarantee that these heuristics can answer all questions correctly all the time.

Can problems from the "Human Domain" be modeled fully as combinatorial problems so that we can hopefully give some approximation guarantee? Given realistic scale and scope, how does the human brain solve such problems (like question-answering)? Does the brain map everything to combinatorial optimization? Can its modus operandi be applied to automated systems so that they solve our problems while we attack other problems that right now are complicated even for the human mind?

Labels: computer science