Saturday, December 23, 2006

Strong and Weak Artificial Intelligence

Artificial Intelligence (AI) is almost an umbrella term today. Different people use it to refer to different things, and all of the uses taken together cover a lot of ground. Image processing, pattern recognition, various types of automated statistical analysis and syntactic reasoning have all been called artificial intelligence.

The AI of this article refers to the ideal of creating a computer with human-like behaviour or consciousness. That last sentence is already a loaded one. To some people, creating human-like behaviour is the same as creating human-like consciousness. Others argue that behaviour and consciousness are fundamentally different. The two are called, respectively, Weak AI and Strong AI.

Weak AI refers to the ideal of creating, via artificial means (artificial meaning demonstrably algorithmic, for instance via a program on a computer), a set of behaviours which are indistinguishable from human behaviour.

Strong AI refers to the notion that the human mind is in fact algorithmic. Not only can it be simulated using an algorithm, it is an algorithm.

Distinguishing between Weak AI and Strong AI can be hard. Although they appear to be different, the argument goes that if something behaves exactly like a human, then it is human, at least mentally. This may seem counterintuitive at first, but the crucial condition is that it behave like a human in all aspects. If this argument is accepted, then simulating something that behaves like a human is the same thing as creating a human. To understand this point of view, it helps to try to identify the difference between a "true" human and a "simulated" human from the mental perspective. Is there any aspect of the mentality of humans that cannot be simulated, which does not manifest in any form of behaviour? That is, is there anything about the mentality of humans that is not "simulatable", even if every part of the behaviour is simulatable?

Opponents of the equality of Strong AI and Weak AI use arguments based essentially on the philosophical notion of qualia, or unique individual perceptions. For example, an organism experiencing pain has a unique, unified experience of the sensation. Opponents of the equality essentially claim that such an experience or quale cannot be simulated on a computer, even if the behaviour associated with the experience can.


Friday, December 22, 2006

Gödel's Theorem and Artificial Intelligence

In 1931, the mathematician Kurt Gödel published a paper that proved his famous incompleteness theorems. The first of these theorems has the following as one of its consequences: in any consistent axiomatic formal system rich enough to include arithmetic, there are true statements that cannot be proven as theorems. That is, there are statements which are true, but whose truth cannot be determined by any algorithm starting only from the axioms of the system.

Gödel's theorem has had a lot of consequences, though it has not affected the development of most fields of mathematics or science. The theorem has been used by various people to claim various things, including that the Bible is incomplete, that God doesn't exist, and that God must exist. This result has also been used by some people (most notably the mathematical physicist Roger Penrose) to claim that both Strong AI and Weak AI are impossible. I find this claim very interesting, and the arguments that are used are not easy to refute.

I think the arguments are so hard to refute because the natural languages we converse in (English, in this case) are sometimes not nuanced enough to clearly express our thoughts. We use the same phrase to mean two different things and confuse ourselves. The following attempts to address this by highlighting a potential flaw in Penrose's argument. The flaw arises because Penrose fails to distinguish between the knowledge that there exists an object having a certain property from the knowledge of an object having that property. That is, he fails to recognize that we may believe that an object with the property exists, without knowing what the object is.

Gödel's theorems are notoriously hard to grasp. Part of the reason is the unfamiliarity of the setting in which the theorems are developed (first order languages). Luckily, there is a far more familiar setting in which Gödel's theorems come to play under a different guise: that of algorithms and programs, which many people are familiar with today. So let us understand an analogue of Gödel's first theorem in the setting of algorithms, and use this setting to make our arguments, instead of the mathematical logic setting Gödel originally used.

Algorithms and the Halting Problem

Rather than try to define exactly what an algorithm is, I assume that it is well-defined, and note that any algorithm can be encoded as a finite string. An algorithm can have an input and an output; if A is an algorithm with 3 inputs i1, i2, i3, then we use the notation o = A(i1, i2, i3) to indicate that o is the output of the algorithm when executed with the inputs i1, i2, i3. An algorithm can have any number of inputs, and the number of inputs itself needn't be fixed. That is, A could have 3, 4, 66, 1,003,478, or any other number of inputs.

We all know that algorithms execute in a series of "steps", and any program executes a finite number of steps before it halts. We also know that programs sometimes don't halt at all -- an operating system hang, for example, a loop such as "while(1){}" in C, or a program written to halt when it finds an odd number divisible by 2. The Halting Problem refers to the following question. Is there any algorithm A, which, given another algorithm B as input, halts and returns 1 if B halts, and halts and returns 0 if B doesn't halt? That is, A(B) = 0 if B doesn't halt, A(B) = 1 if B does halt. Important points to note:
  1. A(B) must halt -- after a finite number of steps, it must stop.
  2. The answer it returns (0 or 1) must be correct.
  3. A() must be able to do 1. and 2. above for any program B.
The answer to this question is known; there cannot exist any such algorithm A.

HL1: For any algorithm A, there is an algorithm, call it G(A), such that either A doesn't halt on input G(A), or A(G(A)) is wrong (0 if G(A) halts, 1 if G(A) doesn't halt).

We write G(A) instead of just G to emphasize that G(A) depends on A.

Now suppose we insist on considering only algorithms A which either halt with a correct answer (they halt only when they have determined beyond doubt whether their input halts or not), or don't halt at all. These algorithms never return a wrong answer. Let us call these sound algorithms. Note that a sound algorithm never answers incorrectly, no matter what its input. It can be shown that:

HL2: For every sound algorithm A, there exists an algorithm G(A) such that neither G(A) nor A(G(A)) halts.

This result is the analogue of Gödel's first theorem in the setting of algorithms. Note the following:
  1. A is a sound algorithm.
  2. G(A) doesn't halt; this is a fact.
  3. However, A cannot determine the above fact; A(G(A)) does not halt.
We are now equipped to state the usual objection to AI based on this analogue of Gödel's theorem.

The Halting Problem and AI

The usual objection to the possibility of Strong and Weak AI based on the halting problem argument goes as follows.
  1. Suppose I am a sound algorithm, say A.
  2. There is an algorithm G(A) which does not halt such that A(G(A)) does not halt.
  3. However, I know with certainty that G(A) does not halt.
  4. Therefore, since I am A, A knows with certainty that G(A) does not halt, and will perform the following:
    1. If the input B is not G(A), A can determine whether B halts in a finite number of steps; A does so and returns the correct answer.
    2. If the input is G(A), simply return 0 (for "does not halt"). This is correct.
  5. Thus:
    1. A is sound; we have not violated this assumption.
    2. A(G(A)) does halt.
  6. So A(G(A)) does not halt (from 2. above) and A(G(A)) does halt (from 5.2. above), a contradiction.
  7. Therefore 1. must be an invalid assumption.
Since the only assumption in the above is that I am a sound algorithm, and we have a contradiction, the assumption must be false; that is, I cannot be a sound algorithm.

This "proof" is slightly blurry in steps 4.1 and 4.2, in the sense that G(A) may not be unique. There will be many algorithms satisfying the requirements for G(A). However, this is a non-issue: we could have considered G(A) to be the class of all algorithms satisfying those requirements and used set membership instead of equality, and this issue would have disappeared.

Disproof

This "proof" conceals several points, which we deal with sequentially.

Objection 1. The first objection is to Step 1 in the proof; this is the most common objection to the proof. Why should we suppose that we are sound algorithms? We may be unsound algorithms. Recall that in the first statement of the halting lemma (HL1), we don't know whether G(A) halts or not. So if we are an unsound algorithm A, we don't know whether our G(A) halts or not, and the proof doesn't go through at all. Penrose does try to defend the assumption that we are sound algorithms.

Objection 2. To move on to the next objection, suppose we grant that if we are algorithms, we would have to be sound algorithms. Is the proof correct in this case? This second objection has to do with what A really is. In steps 4.1 and 4.2 of the proof, we would appear to be modifying the algorithm A itself. Since we assumed "I am A", such a modification may not be permissible. In any case, if A is modified to A', then we need to be concerned with G(A'), not with G(A) any longer. However, this objection is weakened by the chance that steps 4.1 and 4.2 could already be part of A, without any modification. That is, the behaviour of A is to check whether its input is G(A) or not, and base its actions on that test.

Objection 3. Next, we grant that A already includes 4.1 and 4.2 and as a consequence these steps do not constitute a modification to the algorithm. This brings us to what I think is the most crucial flaw in the proof. The proof involves the test: "if the input B is G(A)". A crucial question is, would A be able to recognize G(A)? A knows that G(A) exists, but does not know what G(A) is. The knowledge of the existence of G(A) does not enable A to test whether B = G(A). Note also that, as noted below the proof, G(A) is not unique. Thus even if A could find one G(A) and compare B against it, this would not suffice. A would have to compare B against all possible G(A)s -- this could be an infinite set. Thus A would have to determine using some clever method (not simply by comparing against candidates for G(A)) whether B is a valid candidate for G(A). If we assume that A can do this in a finite number of steps, we now have two assumptions in the proof, and the contradiction at the end would only imply that any one of them could be wrong.

Conclusion

Several people have published various versions of this proof, but if it is the proof in the above, it would seem that the fallacy outlined in the third objection settles the issue. As pointed out at the beginning of this article, it is the free form of the English language that makes it so hard to pin down what is really going on. When we say we know that G(A) doesn't halt, we imagine we also know what G(A) is -- this is not the case here. This distinction, between knowing that "there is a G(A) such that G(A) and A(G(A)) don't halt" and knowing that "G(A) doesn't halt", is the crucial one. Weak and Strong AI are still very much alive!



Tuesday, December 19, 2006

The Chinese Room Experiment - Part I

The Chinese Room Experiment is a thought experiment building on the Turing Test put forward by the philosopher John R. Searle.

The intention of the thought experiment is to demonstrate that the hypothesis of Strong Artificial Intelligence (Strong AI), which claims that the human mind is an algorithm, is wrong. The Strong AI argument says that every human mental process is algorithmic, that is, it follows a predefined sequence of steps. This appears to be different from the Weak AI hypothesis, which claims that every human mental process can be simulated on a computer, but that the human mind itself is not an algorithm. Some argue that mental processes are essentially particular behaviours (behaviouralism) or a way of looking at physical processes (functionalism), and as a consequence there is no significant distinction between the Strong AI and Weak AI hypotheses. (Read about Strong and Weak AI.)

The Chinese Room Argument asks one to imagine that there is a native English speaker, Steve, sitting in a closed room with two windows. Steve knows nothing of Chinese. In the room is a book containing detailed information on how to respond to any sentence in Chinese. Outside the room is Wong, a native Chinese speaker. Steve receives a sentence in Chinese from Wong via the input window, consults the book, and responds in Chinese at the output window. Steve carries on such a conversation with Wong without understanding either the input, the output, or the logic behind the exchange.

Searle claims that to Wong, Steve would appear to "know", or "understand", Chinese. But Steve doesn't. He is simply following an algorithm; he has no clue what any of the Chinese exchange means. Thus, according to Searle, no algorithm constitutes understanding or consciousness.

Objections to the Chinese Room Argument

There are several answers to Searle's Chinese Room Experiment from people claiming that it does not prove the impossibility of Strong AI. Here are some of them:
  1. The Systems Reply
    1. Objection This objection says that, while Steve does not understand Chinese, the system consisting of Steve and the book does. This can be viewed as a single, larger entity which does understand Chinese.
    2. Searle's Reply Searle replies to this objection by suggesting a modification of the experiment in which Steve memorizes the entire translation book and steps out of the room, talking face to face with Wong. Steve still does not understand Chinese, says Searle. He is still applying the rules without any understanding of Chinese.
    3. Rejoinder The problem with Searle's reply is that it invites us to think of all of Steve's memory as an integral part of his consciousness or ego, while in this modification to the experiment, Steve is using his memory as if it were just separate storage, no different than copying the book onto his forearm. Steve and his memory, taken together as a system, do understand Chinese.
  2. The Complexity Reply
    1. Objection This objection, due to Daniel Dennett, says that it is not easy to duplicate consciousness without being extremely complex. Ignoring this complexity in the Chinese Room Experiment fools our intuition into thinking the Steve+Book combination is ignorant of Chinese, since we think the book is "just a book". In fact, if we considered the complexity of the algorithm required to converse in Chinese, we would be forced to conclude that the "book" is actually complex enough to be considered conscious. (The notion of a book being conscious may seem ridiculous, but this really refers to the algorithm contained in the book, not the physical book itself.)
    2. Searle's Reply Searle interprets Dennett's objection as the statement "You can't have a book like that", and goes on to say that the whole point of thought experiments is to imagine a situation that is conceivable, even if it we don't know the details of how to set it up. He says Dennett is essentially denying the idea behind thought experiments.
    3. Rejoinder Dennett is not saying it is impossible to have a book that complex; he is saying anything that complex is already conscious and aware. If Searle insists on having a thought experiment where a book is complex enough to converse in Chinese but is not conscious, he is assuming too much and is begging the question.
More information on this interesting topic can be found in the following books:

Consciousness Explained - by Daniel Dennett
The Mystery of Consciousness - by John R. Searle


Thursday, December 14, 2006

Reservations - The Right Way

by "Armchair Guy"

Reservations are back in the news, and have been for a while. The Congress government has proved resolute and determined to implement reservations in sweeping steps. There are multiple consequences, including nationwide protests, accusations of a sacrifice of merit, concerns about the impact on the economy should reservations be approved for the private sector, increased polarization and mutual distrust among various socioeconomic classes.

The reason given for reservations is that in the current socioeconomic milieu, different categories of people face different challenges in obtaining education and employment. The social and economic obstacles are hypothesized to be so large that, even if education assistance is substituted for reservations, the impact would not be sufficient to ensure sustainable overall equality.

Multiple Index Related Affirmative Action (MIRAA)

One question that arises often is, why only caste? It would appear that the optimal way to ensure equality would be to use a basket of indicators including caste, gender, economic status etc. One such basket, named Multiple Index Related Affirmative Action (MIRAA), has been suggested by Prof. Purushottam Agrawal. The argument for using caste alone is that caste is the biggest indicator of underdevelopment. Indices such as MIRAA could certainly be more effective in improving the condition of people than caste alone, since they would allow reservations to be effectively targeted at the people who need them the most.

To understand MIRAA, we first consider the basket of socioeconomic indicators it suggests. The primary considerations when choosing such indicators should be as follows:
  1. The indicators should be indicative of education and employment levels
  2. Information on the indicators should be readily available
The indicators considered by Prof. Agrawal under MIRAA are the following:
  1. Caste/Tribe
  2. Gender
  3. Economic status
  4. Kind of schooling received
  5. Region where candidate spent formative years
  6. Educational status of parents/family
Each candidate is awarded 0 to 5 points based on his/her status on each of these indicators, for a maximum of 30 points. This then forms 30% of the score used by any institution to determine admissions.

Debating MIRAA

This system is already being debated on Tehelka. Praise for the system includes the fact that is is proven: Jawaharlal Nehru University has used it successfully in the past. The system is a self-organizing score in the sense that it targets the right sections of society in a manageable way. The need to target the right people is mentioned by several readers on the Tehelka debate. The system also appears to balance the needs of the group and the rights of the individual. Put another way, 70% of the final admission score is "merit" based.

Criticisms include one from Amit Sen Gupta, another commentator on Tehelka, who believes that:
Targeting of affirmative action to a section within “backward” castes will be used as a powerful tool to deny the benefits to as many as possible
and that the system would be a non-starter on a nation-wide scale. Some readers on Tehelka also expressed concerns about the exact weights given to various indicators.

The points raised by Mr. Gupta bear thinking about. One strength of MIRAA is that it is a single transparently computable score. This is good for scalability. MIRAA also does not explicitly target a section within backward castes. It targets those who are suffering the most; as an implicit consequence, it will target backward castes. Within backward castes, it would target specific sections, but this is still implicit. The system as a whole remains simple, based on a single score, and thus not prone to overly high levels of manipulation.

The unstated but most contentious issue is likely the low overall weight given to caste/tribe - just 5 points out of 30, or in the bigger picture, just 5% of the total candidate score. Resolving this bone of contention is crucial; most of the difficulties with MIRAA are likely to be about the relative weighting of the indices and about the total percentage of the MIRAA score included in the total candidate score.

Objections by other readers serve to strengthen this assertion. The exact weights used to compute the score here were selected based on the individual reasoning, personal experience, or personal preferences of a person or some persons. The 30% number was arrived at the same way.

In a word, MIRAA as it stands today is a subjective system.

Making MIRAA Objective: the Modified MIRAA Score

Turning MIRAA into an objective system requires only a little tweaking of the system itself. It would, in addition, involve some survey sampling and statistical analysis.

To understand how to make MIRAA an objective system consider what we mean when we say that a person belonging to a certain category, say an SC candidate, is at a disadvantage compared to a forward caste (FC) candidate.

An objective way of defining the amount of disadvantage is the following. In an examination, suppose the average SC candidate scores 12% less than the average FC candidate. Then the SC candidate is at a disadvantage of 12 percentage points compared to the FC candidate. In the above situation, the SC candidate should get a MIRAA score of 12. This is the correct score because it neutralizes the real disadvantage the average SC candidate has relative to the FC candidate. It is objective because the score is completely data driven; personal opinions don't come into the picture. The data and methods used to establish the actual disadvantage would be a matter of public record.

The MIRAA set of indices can be used to refine the above further. For example, SC women may, on the average, score 18% less than FC men, while the difference for SC men may be 10%. SC women should get a MIRAA score of 18, while SC men should get a MIRAA score of 10.

The same system can be extended to include all 6 variables. In this modified MIRAA system, there is no artificial percentage attached to group needs, such as the 30% in the original MIRAA. Their modified MIRAA score is is simply added to their score in the entrance exam to determine the candidate's final score. This final score may add up to more than 100, but that is not a problem if rank (based on the final score) is used to determine admission.

The modified MIRAA system handles the balance of merit and group needs in a more correct way by restoring to each candidate exactly the amount of merit that he/she was deprived of by the socioeconomic system.

Potential Drawbacks of the Modified MIRAA Plan

This method appears to have a drawbacks as well.

First, it appears to reward poor performance. The strata that perform the worst would have the highest MIRAA score. Thus it could be argued that this system may actually encourage poor performance. This objection is not valid in reality however. A counterpoint is that, within each stratum, candidates are selected by fair competition according to merit. Thus there is a strong incentive for each candidate to perform higher, and those who perform lower within each stratum would fail to obtain seats.

The second objection is that there is no single standardized exam in India (analogous to the SAT in the USA) on which the difference in score between different strata could be evaluated. This objection can be resolved by using statistical methods (such as "grading on a curve") to normalize the scholastic achievements in different educational boards. Alternatively, if it is felt that there are fundamentally different categories of examinations and the score should be different in each, several categories of exams could be created, with a different table of modified MIRAA scores for each.

Discussion and Conclusions

The existing reservation system does not necessarily get resources to those who need them the most; however, some sort of assistance must be provided to those who have historically suffered from socioeconomic discrimination. Prof. Agrawal's suggestion of MIRAA takes 6 important indices, as well as merit, into account when computing a score, and is simple enough to be implemented transparently. If implemented, it would be instrumental in giving specific socioeconomic strata of people the assistance they need. However, MIRAA as it stands today faces some objections that can be traced back to the subjective origins of its scoring system.

A "Modified MIRAA" score is proposed that achieves the same objectives as the original MIRAA system but eliminates the subjectivity of the score, potentially increasing its acceptability. The Modified MIRAA is also perfectly fair: it compensates each socioeconomic stratum for exactly the loss in merit imposed by the socioeconomic system. As a consequence it also balances merit and socioeconomic status in a natural way. The price paid for the objectivity of the Modified MIRAA score is data collection and statistical analysis; however, this could also be done using simple and transparent protocols.

"Armchair Guy" would like to invite comments and criticisms of the Modified MIRAA score proposed in the above article. Comments or criticisms should be based on rationale rather than rhetoric.