YeGoblynQueenne on Hacker News

What is reasoning?

In computer science and AI when we say "reasoning" we mean that we have a theory and we can derive the consequences of the theory by application of some inference procedure.

A theory is a set of facts and rules about some environment of interest: the real world, mathematics, language, etc. Facts are things we know (or assume) to be true: they can be direct observations, or implied, guesses. Rules are conditionally true and so most easily understood as implications: if we know some facts are true we can conclude that some other facts must also be true. An inference procedure is some system of rules, separate from the theory, that tells us how we can combine the rules and facts of the theory to squeeze out new facts, or new rules.

There are three types of reasoning, what we may call modes of inference: deduction, induction and abduction. Informally, deduction means that we start with a set of rules and derive new unobserved facts, implied by the rules; induction means that we start with a set of rules and some observations and derive new rules that imply the observations; and abduction means that we start with some rules and some observations and derive new unobserved facts that imply the observations.

It's easier to understand all this with examples.

One example of deductive reasoning is planning, or automated planning and scheduling, a field of classical AI research. Planning is the "model-based approach to autonomous behaviour", according to the textbook on planning by Geffner and Bonnet. An autonomous agent starts with a "model" that describes the environment in which the agent is to operate as a set of entities with discrete states, and a set of actions that the agent can take to change those states. The agent is given a goal, an instance of its model, and it must find a sequence of actions, that we call a "plan", to take the entities in the model from their current state to the state in the goal. This is usually achieved by casting the planning problem as pathfinding over a graph with a search algorithm like A*. Here, the agent's model is a theory, the search algorithm is the inference procedure, and the plan is a consequence of the theory. Deductive reasoning can be sound, as long as the facts and rules in the theory are correct: from correct premises we can deduce correct conclusions. We know of sound deductive inference rules, e.g. A*, and Resolution, used in automated theorem proving and SAT-Solving, are sound.

The classic example of inductive reasoning is inferring the colour of swans. Most swans are white (apparently) so if we have only seen white swans we have no reason to believe there are any other colours: we are forced to infer that all swans are white. We may only be disabused of our fallacy if we happen to observe a swan that is not white, e.g. a black swan. But who is to say when such a magnificent creature will grace us with its presence, outside of Tchaikovsky's ballets? Induction is thus revealed to be unsound: even given true premises we can still arrive at the wrong conclusions. Another example is the scientific method: imagine an idealised scientist, perfectly spherical, in a frictionless vacuum. She starts with a scientific theory, then goes out into the world and makes new observations about a phenomenon not described by her theory. She constructs a hypothesis to extend her theory so as to explain the new observations. The hypothesis is a set of rules, where the premises are the consequences of the rules in her initial theory. Then, being an idealised scientist, she goes looking for new observations to refute her hypothesis. Science only gives us the tools to know when we're wrong.

Abductive reasoning is the mode of inference exemplified by Sherlock Holmes. We can imagine Sherlock and Watson standing outside a tavern in London, watching as a gentleman of interest steps out of the tavern with egg on his lapel. "Ah, my dear Watson, what can we conclude from this observation?". "Why my dear Holmes, we can conclude that the man had eggs for breakfast". Holmes and Watson can arrive at this conclusion, about a fact that they have not directly observed, because they have a theory with a rule that says "if one eats eggs, one may get some on one's lapels". Working backwards from this rule, and their observation of egg on the man's lapels, they can guess that he had eggs even if they didn't directly observe him doing so. Abduction is also unsound: the man may have swapped coats with an accomplice, who was the one who had eggs for breakfast instead.

And now you know what "reasoning" means. So the next time someone asks: "what is reasoning?", you can let them know and turn the discussion to more interesting, more productive directions.