Deductive vs. Inductive Algorithms

My dissertation is almost complete. As I prepare for the defense I started reading some textbooks on machine learning and came across “Artificial Intelligence - A Textbook” by Charu C. Aggarwal. Normally graduate-level textbooks, especially technical ones, are dry but Chapter 1 of this book blew my mind. It discussed many of the algorithms I was already familiar with and viewed them through the lens of deductive vs. inductive reasoning.

This article is essentially a “book report” on the first chapter. I will attempt to simplify the material for an undergraduate audience in the hopes that I could integrate the material into a future section of my IS 425 class at UMBC. I always tell my students that in order to create an artificial intelligence it is important to understand human intelligence and human thought processes. The best solutions have been a mixture of cognitive psychology and computer science. The psychologist studies the human mind and the computer scientist studies computers and machines.

The primary objective of this article is to explain the difference between deductive reasoning and inductive learning and to describe the types of problems (both computational and human) that these approaches attempt to solve. A student should be able to look at a problem and attempt to classify it as either deductive or inductive.

My preferred definition of artificial intelligence is machines doing what humans do. Before the development of modern machine learning and deep learning techniques, programmed computers were already good at tasks that humans did. In this sense, a series of if/then/else statements and other common programming motifs already constitute an artificial intelligence. In a previous article I even described a computer game having an artificial intelligence because that is what the human player perceives it as (independent of the coding behind the scenes to make it happen).

Machines are good at fast and simple calculations. They are good at repetitive tasks.

Deductive Reasoning

Computers are good at following a series of logical statements if they are accurately programmed (the if/then/else statements mentioned earlier) and are provided a comprehensive series of facts to reason with (a knowledge base).

Deductive Reasoning - Facts and logical rules are used to make conclusions.

One tries to reason using logic (or other systematic methods like search) with a well-established base of hypotheses in order to make provably correct conclusions.

Most middle or high schoolers are taught deductive reasoning when they take a Geometry class. Students are provided with a series of lines and angles they use rules developed by the ancient Greeks (like the opposite angle rule) to deductively prove basic hypotheses.

Inductive Learning

It became quickly obvious that there are cognitive limits to computing if those computers were restricted to deductive thought. Psychologists knew that a lot of human thought doesn’t stem from a series of logical statements. This includes creative attempts and breakthrough innovations. In fact, most innovations usually require breaking traditional rules about how organizations should operate.

Much of human intelligence is gleaned from evidentiary experience in day-to-day life that supports intuitive choices (but may not result in provably correct conclusions). Making non-obvious inferences often requires the sacrifice of provable correctness.

Inductive Learning - Data instances provide the evidence needed to build hypotheses and make predictions from them (rather than assume pre-defined hypotheses).

In my field (Information Technology) most operations are conducted with a series of rules (technological and organizational) that dictate how those roles work. Yet even in a rigid computational field such as IT, I have met people who had developed instincts and intuitions that can only come from experience. The ability to make leaps in logic from experience is a product of inductive learning and it can be very powerful.

The hope for inductive learning (and its associated algorithms) is the ability for computers to learn with minimal input. Current language translation programs (like the ones phones have) are written using a library of vocabulary words and a series of syntax rules that are refined by experts in those languages (a deductive system). The inductive learning equivalent would be a program that listens or reads samples of a given language and automatically figures out the vocabulary and syntax of that language. That is, it gains knowledge of a language by observation, just like how humans learn language.

Differences Between Deductive Reasoning and Inductive Learning

To summarize the previous two sections:

• Requirements

  • Deductive Reasoning requires a set of established facts that we assume to be true and a series of logical reasoning rules that we can apply to those facts.

  • Inductive learning requires a set of examples/observations (the evidence).

• Processes

  • Deductive reasoning takes existing facts and applies logical reasoning rules to test those facts or to derive new facts.

  • Inductive learning attempts to create generalized conclusions or hypotheses about the examples provided to it.

  • The classical scientific method involves both of these: Newton observed gravity (induction) before attempting to test/prove it (deduction). In general, scientists observe something in nature, create a hypothesis based on those observations (induction) and then use the scientific method to test those hypotheses (deduction).

• Conclusions

  • Deductive reasoning produces conclusions that are provably true and follow from rules applied to facts.

  • Inductive learning produces fuzzier results that aren’t 100% provable but these conclusions can be non-obvious.

    • This is okay. Producing fuzzy but generalizable conclusions can be useful. At work, sometimes I would go to my boss and say, “I have a hunch, trust me” and great things would come from it. Inductive learning can lead to “out of the box” ideas.

How This Relates to Machine Learning

I will list a series of topics discussed in my class and I will classify them as either inductive or deductive.

• Deductive

  • Knowledge Engineering and Expert Systems. These are usually hard-coded databases and inference rules that help provide answers to users. WebMD is a good example of an expert system.

  • Traditional computer logic (written using various programming languages).

  • Traditional machine learning algorithms like clustering, association and classification.

• Inductive

  • Deep learning algorithms such as neural networks.

Most current computer programs employ deductive reasoning to come to its conclusions.

The definition of what is considered a deductive reasoning system is rather broad. Almost any computer program that accomplishes a particular goal with a well-defined and logical control flow (starting with a set of hypotheses) and coming to logically provable conclusions can be considered a deductive reasoning system.

Some Final Observations

• Deductive reasoning problems tend to be more narrowly focused whereas inductive learning problems produce more generalized results.

• Explainability

  • The results of deductive reasoning tend to be more interpretable and more explainable.

  • The “black box” nature of many deep learning algorithms makes inductive learning techniques less explainable.

• While developments in deductive reasoning continue to be refined, research in inductive learning has the potential to produce giant leaps in computational ability.

• Inductive reasoning techniques (like deep learning techniques) are harder

Examples

For my class, I am thinking about providing examples of computational problems and then asking students whether they’re inductive or deductive. I will provides some examples from Aggarwal’s book and include some of my own.

Deductive Reasoning Examples

• Tax-filing systems like TurboTax. TurboTax is sophisticated but in the end it is a series logical statements and calculations based on the current tax codes.

• WebMD Symptom Checker. A knowledge base of symptoms written into a database and a series of rules designed to take the user’s input and search that database.

• Learning a language with a grammar book.

Inductive Learning Examples

• Tesla Full-Self Driving. Admittedly I can’t be sure if this applies to the full software but the parts that recognize the environment around the car (scene recognition) are neural networks. There are many videos by Tesla’s head of AI, Andrej Karpathy, detailing these.

• Learning a language by observing speakers of that language.

• A phone’s ability to identify the faces of your friends in your photos based on prior-tagged sample photos.

• “Perusing a worked example to learn algebraic manipulation.”