Artificial Intelligence: Knowledge

It seems a new smart phone hits the market every other week these days! Faster computers with faster GPUs. Better graphics for next-gen gaming consoles. How did these machines get so intelligent? Well to put it frankly, computers without these fancy computations are actually pretty dumb. The systems embedded within the application to seek reason and draw conclusions, those systems are quite sophisticated.

Knowledge-Based Agents

Agents that reason by operating on internal representations of knowledge.

Let’s start answering this with a Harry Potter example. Consider the following sentences:

1. If it didn’t rain, Harry visited Hagrid today.
2. Harry visited Hagrid or Dumbledore today, but not both.
3. Harry visited Dumbledore today.

Based on these three sentences, we can answer the question “did it rain today?”, even though none of the individual sentences tells us anything about whether it is raining today. Here is how we can go about it: looking at sentence 3, we know that Harry visited Dumbledore. Looking at sentence 2, we know that Harry visited either Dumbledore or Hagrid, and thus we can conclude

4. Harry did not visit Hagrid.

Now, looking at sentence 1, we understand that if it didn’t rain, Harry would have visited Hagrid. However, knowing sentence 4, we know that this is not the case. Therefore, we can conclude

5. It rained today.

To come to this conclusion, we used logic based on existing information.

Propositional Symbols & Logic

Propositional symbols are most often letters (P, Q, R) that are used to represent a proposition.

Not (¬) inverses the truth value of the proposition. So, for example, if P: “It is raining,” then ¬P: “It is not raining”.

And (∧) connects two different propositions. When these two proposition, P and Q, are connected by ∧, the resulting proposition P ∧ Q is true only in the case that both P and Q are true.

Or (∨) is true as as long as either of its arguments is true. This means that for P ∨ Q to be true, at least one of P or Q has to be true.

Implication (→) represents a structure of “if P then Q.” For example, if P: “It is raining” and Q: “I’m indoors”, then P → Q means “If it is raining, then I’m indoors.” In the case of P implies Q (P → Q), P is called the antecedent and Q is called the consequent.

Biconditional (↔) is an implication that goes both directions. You can read it as “if and only if.” P↔Q is the same as P → Q and Q → P taken together. For example, if P: “It is raining.” and Q: “I’m indoors,” then P↔Q means that “If it is raining, then I’m indoors,” and “if I’m indoors, then it is raining.” This means that we can infer more than we could with a simple implication. If P is false, then Q is also false; if it is not raining, we know that I’m also not indoors.

By chaining these propositional logic sequences together they can be assigned to a knowledge base. We can create this truthy form of logic to provide the AI to make inferences about the given world. Additionally, we can use a technique called entailment which is a relation that means that if all the information is true for one source, then the rest of the information from the other side must be true too.

α ⊨ β (α entails β)

For example, if α: “It is a seashell in the ocean” and β: “In the ocean,” then we know that α ⊨ β. If it is true that it is a shell in the ocean, we also know that it is a ocean, and not a river. Entailment is a relation that means that if all the information in α is true, then all the information in β is true.

Inference

Extracting new sentences from existing ones is called inference. In the Harry Potter examples A.) Harry did not visit Hagrid. B.) It rained today. The existing sentences did not explicitly state such remarks; however, based on the information available we can find ways to infer new knowledge.

Model checking is not always the most efficient algorithm since it considers every possible model before giving the answer. Inference Rules allow the user to generate new information based on existing knowledge without considering every possibility.

Knowledge Engineering

How can we figure out how to represent propositions and logic in AI?

In the board game Clue, a crime was committed by a person, by means of a tool in a location. We can create a knowledge base by adding the rules of the game, and tag on additional information in forms of boolean values for each representation as we make our way to the game.

As the game progresses we can add revealed cards to the Knowledge Base. Once we have enough information the model checking algorithm will be tapped out and provide the solution to our problem.

[1]: Brian Yu, David J. Malan; Harvard University CS50's Introduction to Artificial Intelligence with Python

[2]: Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani, Jonathan Taylor; An Introduction to Statistical Learning with Applications in Python