Knowledge Representation  (a) Logical representations (b) Production rule representations

(c) Semantic networks (d) Frame representations

(a) Logical representation  The logical representations are mostly concerned with truth of
statements regarding the world. These statements are most generally represented using
statements like TRUE or FALSE.
1. Propositional logic : These are restricted kinds that make use of propositions (sentences
that are either true or false but not both) which can be either true or false. Proposition logic is
also known as propositional calculus, sentential calculus or boolean algebra
2. First Order Predicate Logic : These are much more expressive and make use of variables,
constants, predicates, functions and quantifiers along with the connectives explained already
in previous section.
3. Higher Order PredicateLogic : Higher order predicate logic is distinguished from first order
predicate logic by using additional quantifiers and stronger semantics.
4. Fuzzy Logic : These indicate the existence of in between TRUE and FALSE or fuzziness in
all logics.
5. Other Logic : These include multiple valued logic, modal logics and temporal logics.
(b) Production rule representation One of the widest used methods to represent knowledge
is to use production rules, it is also known as IF-THEN rules.
(c) Semantic networks  These represent knowledge in the form of graphical networks, since
graphs are easy to be stored inside programs as they are concisely represented by nodes
and edges.  A semantic network basically comprises of nodes that are named and represent
concepts, and labelled links representing relations between concepts. Nodes represent both
types and tokens.  For example, the semantic network in o Tom is a cat. o Tom caught a fish.
(d) Frame representation  This concept was introduced by Marvin Minsky in 1975. They are
mostly used when the task becomes quite complex and needs more structured
representation. More structured the system becomes more would be the requirement of using
frames which would prove beneficial. Generally frames are record like structures that
consists of a collection of slots or attributes and the corresponding slot values.  Slots can be
of any size and type. The slots have names and values (subfields) called as facets
Propositional Logic(PL) is simple but powerful for some artificial intelligence problems.
You have learnt simple mathematical logic in which uses atomic formulas are used. (Atomic
formula is a formula that has no strict sub-formulas). Atomic logic formulas are called
propositions.  In case of artificial intelligence propositional logic is not categorized as the
study of truth values, but it is based on relativity of truth values. (i.e. The relationship
between the truth value of one statement to that of the truth value of other statement)
Simulated annealing is a variation of hill climbing. Simulated annealing technique can be
explained by an analogy to annealing in solids. In the annealing process in case of solids, a
solid is heated past melting point and then cooled.  With the changing rate of cooling, the
solid changes its properties. If the liquid is cooled slowly, it gets transformed in steady frozen
state and forms crystals. While, if it is cooled quickly, the crystal formation will not get
enough time and it produces imperfect crystals.  The aim of physical annealing process is to
produce a minimal energy final state after raising the substance to high energy level. Hence
in simulated annealing we are actually going downhill and the heuristic function is a minimal
heuristic. The final state is the one with minimum value, and rather than climbing up in this
case we are descending the valley The idea is to use simulated annealing to search for
feasible solutions and converge to an optimal solution. In order to achieve that, at the
beginning of the process, some downhill moves may be made. These downhill moves are
made purposely, to do enough exploration of the whole space early on, so that the final
solution is relatively insensitive to the starting state. It reduces the chances of getting caught
at a local maximum, or plateau, or a ridge.
Algorithm 1. Evaluate the initial state. 2. Loop until a solution is found or there are no new
operators left to be applied : Set T according to an annealing schedule Select and apply a new
operator Evaluate the new state : goal quit E = Val(current state) Val(new state) E < 0 
new current state else new current state with probability e-E/kT
Genetic Algorithms (GAs) are adaptive heuristic search algorithms that belong to the larger
part of evolutionary algorithms. They are based on the ideas of natural selection and
genetics. These are intelligent exploitation of random searches provided with historical data
to direct the search into the region of better performance in solution space. commonly used
to generate high-quality solutions for optimization problems and search problems. They
simulate the process of natural selection which means those species that can adapt to
changes in their environment can survive and reproduce and go to the next generation.
“survival of the fittest”. Each generation consists of a population of individuals and each
individual represents a point in search space and possible solution. Each individual is
represented as a string of character/integer/float/bits. This string is analogous to the
Chromosome.
Genetic Algorithm 1. [Start] Generate random population of n chromosomes (suitable
solutions for the problem) 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the
population 3. [New population] Create a new population by repeating following steps until the
new population is complete 4. [Selection] Select two parent chromosomes from a population
according to their fitness (the better fitness, the bigger chance to be selected) 5. [Crossover]
With a crossover probability cross over the parents to form a new offspring (children). If no
crossover was performed, offspring is an exact copy of parents. 6. [Mutation] With a mutation
probability mutate new offspring at each locus (position in chromosome). 7. [Accepting]
Place new offspring in a new population 8. [Replace] Use new generated population for a
further run of algorithm 9. [Test] If the end condition is satisfied, stop, and return the best
solution in current population 10. [Loop] Go to step 2

Hill Climbing Algorithm 1. Evaluate the initial state. If it is a goal state, then return and quit;
otherwise make it a current state and go to Step 2. 2. Loop until a solution is found or there
are no new operators left to be applied (i.e. no new children nodes left to be explored). a.
Select and apply a new operator (i.e. generate new child node) b. Evaluate the new state : (i) If
it is a goal state, then return and quit. (ii) If it is better than current state then make it a new
current state. (iii) If it is not better than the current state then continue the loop, go to Step 2
Local maxima , plateau and ridge
Resolution is a valid inference rule. Resolution produces a new clause which is implied by
two clauses containing complementary literals. This resolution rule was discovered by Alan
Robinson in the mid 1960's.  We have seen that a literal is an atomic symbol or a negation of
the atomic symbol (i.e.A, ¬A).  Resolution is the only interference rule you need, in order to
build a sound (soundness means that every sentence produced by a procedure will be “true”)
and complete (completeness means every “true” sentence can be produced by a procedure)
theorem proof maker. 
Take an example where we are given that :
o A clause X containing the literal : Z
o A clause Y containing the literal : ¬Z
Based on resolution and the information given above we can conclude : (X – {Z}) U (Y – {¬Z})

Take a generalized version of the above problem : Given:  A clause X containing the literal: Z
 A clause Y containing the literal: ¬Y  A most general unifier G of Z and ¬Y We can conclude
that :((X – {Z}) U (Y – {¬Y}))
The Resolution Procedure  Let knowledge base be a set of true sentences which do not have
any contradictions, and Z be a sentence that we want to prove.  The Idea is based on the
proof by negation. So, we should assume ¬Z and then try to find a contradiction (You must
have followed such methods while solving geometry proofs). Then based on the Intuition
that, if all the knowledge base sentences are true, and assuming ¬Z creates a contradiction
then Z must be inferred from knowledge base. Then we need to convert knowledge base U
{¬Z} to clause form.  If there is a contradiction in knowledge base, that means Z is proved.
Terminate the process after that.  Otherwise select two clauses and add their resolvents to
the current knowledge base. If we do not find any resolvable clauses then the procedure fails
and then we terminate. Else, we have to start finding if there is a contradiction in knowledge
base, and so on
Steps in nlp lexical, syntax, semantic, discourse, pragmatic
Stages in nlp tokenization, stemming, lamitization, postags, name entity recognition,
chunking
 Supervised Learning Unsupervised Learning Reinforcement Learning
Input data is labelled. Input data is not labelled. Input data is not predefined.
Learn pattern of inputs and Divide data into classes. Find the best reward
their labels. between a start and an end
state.
Finds a mapping equation Finds similar features in input Maximizes reward by
on input data and its labels. data to classify it into classes. assessing the results of
state-action pairs
Model is built and trained Model is built and trained The model is trained and
prior to testing. prior to testing. tested simultaneously.
Deal with regression and Deals with clustering and Deals with exploration and
classification problems. associative rule mining exploitation problems.
problems.
Decision trees, linear K-means clustering, k- Q-learning, SARSA, Deep Q
regression, K-nearest medoids clustering, Network
neighbors agglomerative clustering
Image detection, Population Customer segmentation, Drive-less cars, self-
growth prediction feature elicitation, targeted navigating vacuum cleaners,
marketing, etc etc
Supervised Learning Unsupervised Learning Reinforcement Learning
Input data is labelled. Input data is not labelled. Input data is not predefined.
PAC (Probably Approximately Correct) learning is a framework in computational learning
theory that defines the ability of an algorithm to learn a target function from a given set of
examples. The key idea is that the algorithm should, with high probability, produce a
hypothesis that is approximately correct.
In PAC learning, we have:
- **Target function**: The function we want to learn.
- **Hypothesis class**: A set of functions that the learning algorithm can choose from.
- **Sample**: A set of examples drawn from the distribution over the input space.
An algorithm is said to be PAC if, for any target function within the hypothesis class and for
any distribution over the input space, the algorithm can, with high probability (at least \(1 - \
delta\)), find a hypothesis that is approximately correct (with an error less than \(\epsilon\)) in
a time polynomial in \(1/\epsilon\), \(1/\delta\), and the size of the input.
Example:
Consider the problem of learning a binary classifier that distinguishes between cats and dogs
based on images. The target function \(f\) labels each image as either a cat or a dog.
1. **Hypothesis class**: Possible classifiers the algorithm can choose from, such as linear
classifiers, decision trees, or neural networks.
2. **Sample**: A set of labeled images (examples) from the distribution of all possible cat and
dog images.
3. **PAC Learning Objective**: The learning algorithm should output a classifier (hypothesis)
that, with probability at least \(1 - \delta\), correctly classifies at least \(1 - \epsilon\) fraction of
images drawn from the same distribution.
If the algorithm can achieve this, it is said to be PAC for the given classification problem. For
instance, if we set \(\epsilon = 0.05\) and \(\delta = 0.01\), the algorithm should produce a
classifier that makes errors on at most 5% of images with at least 99% confidence.
State space representation is a fundamental concept in artificial intelligence, particularly
in the fields of problem-solving and planning. It involves modeling a problem as a set of
states and actions that transition between those states.
### Key Components:
1. **States**: Different configurations or situations in the problem space.
2. **Initial State**: The starting point of the problem.
3. **Actions**: Possible moves or operations that can change the state.
4. **Transition Model**: Describes how actions transform one state into another.
5. **Goal State(s)**: The desired final states that represent the solution to the problem.
6. **Path Cost (optional)**: A function that assigns a cost to each action or sequence of
actions, used in optimization problems.
### Example:--Consider a simple problem-solving scenario like the 8-puzzle, where the goal
is to arrange tiles in a specific order by sliding them into an empty space.
- **States**: All possible configurations of the 8 tiles and one empty space on the 3x3 grid.
- **Initial State**: A specific starting arrangement of the tiles.
- **Actions**: Moves that slide a tile into the empty space (up, down, left, right).
- **Transition Model**: Rules that define how each move changes the configuration.
- **Goal State**: The arrangement where the tiles are in the correct order.
- **Path Cost**: The number of moves or steps taken to reach the goal.
### Necessity of State Space Representation:
1. **Structured Problem Solving**: It provides a systematic way to explore possible solutions
and ensures all potential configurations are considered.
2. **Search Algorithms**: Algorithms like breadth-first search, depth-first search, A*, and
others operate on state space representations to find solutions efficiently.
3. **Optimality and Completeness**: Ensures that the search can find the best solution
(optimality) and that it can find a solution if one exists (completeness).
4. **Modularity**: It allows breaking down complex problems into manageable states and
transitions, making it easier to understand and solve.
5. **Formalization**: Provides a clear and formal way to define problems, which is essential
for automation and implementing algorithms in AI systems.
In summary, state space representation is crucial for modeling, understanding, and solving
problems systematically in artificial intelligence. It enables the application of various search
algorithms and ensures that solutions can be found efficiently and effectively.
A* algi
1. Initialize:
 Create an open list (priority queue) and add the start node.
 Create a closed list (empty set).
2. Loop:
1. If the open list is empty, return failure (no path exists).
2. Remove the node with the lowest (𝑛)f(n) from the open list (current node).
3. If the current node is the goal node, reconstruct the path and return it.
4. Add the current node to the closed list.

𝑔𝑡𝑒𝑛𝑡𝑎𝑡𝑖𝑣𝑒=(𝑐𝑢𝑟𝑟𝑒𝑛𝑡)
5. For each neighbor of the current node:
1. Calculate the tentative cost

2. If the neighbor is in the closed list and 𝑔𝑡𝑒𝑛𝑡𝑎𝑡𝑖𝑣𝑒gtentative is greater than or equal to
+𝑐𝑜𝑠𝑡(𝑐𝑢𝑟𝑟𝑒𝑛𝑡,𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟)gtentative=g(current)+cost(current,neighbor).

its recorded 𝑔g-value, skip it.

3. If the neighbor is not in the open list or 𝑔𝑡𝑒𝑛𝑡𝑎𝑡𝑖𝑣𝑒gtentative is less than its recorded
𝑔g-value:

Set ℎ(𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟)h(neighbor) (heuristic value).

 Set (𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟)=𝑔𝑡𝑒𝑛𝑡𝑎𝑡𝑖𝑣𝑒g(neighbor)=gtentative.

Set 𝑓(𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟)=𝑔(𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟)+ℎ(𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟)f(neighbor)=g(neighbor)+h(neighbor).


 Set the parent of the neighbor to the current node.
 If the neighbor is not in the open list, add it 3. Repeat the loop.
Hierarchical planning in AI is a structured approach to problem-solving where tasks are
organized into multiple levels of abstraction. The process typically involves the following
steps
1. **High-Level Planning**: At the top level, the planner defines broad, abstract goals or tasks.
These goals are often general and do not include specific details about how they will be
achieved.
2. **Task Decomposition**: High-level tasks are broken down into more specific sub-tasks.
This step may involve several layers of decomposition, where each sub-task is further divided
into even more detailed tasks until they become manageable and executable.
3. **Sub-Plan Generation**: Each sub-task is treated as a smaller, independent planning
problem. The system generates sub-plans for each of these tasks, detailing the specific
actions or steps needed to achieve them.
Benefits of Hierarchical Planning:
- **Scalability**: It allows for handling larger problems by breaking them into smaller, more
manageable parts.
- **Modularity**: Sub-plans can be reused across different problems or scenarios, enhancing
efficiency.
- **Simplified Reasoning**: By focusing on high-level goals first, the system can avoid getting
bogged down in the details prematurely.
- **Flexibility**: It can adapt to changes in the environment or goals by re-planning at different
levels of the hierarchy.
Applications of Hierarchical Planning:
- **Robotics**: Robots use hierarchical planning to navigate complex environments, where
high-level goals like "reach destination" are broken down into sub-tasks like "navigate to
waypoint" and "avoid obstacle".
- **Automated Reasoning**: In AI systems that require logical problem solving, hierarchical
planning helps in structuring the reasoning process.
- **Game AI**: Video game characters use hierarchical planning to exhibit complex behaviors,
from high-level strategies to low-level actions.
Partial order planning (POP) is a technique in artificial intelligence for planning sequences
of actions to achieve a specific goal. Unlike total order planning, which requires a fixed
sequence of actions, partial order planning allows some flexibility in the order of actions.
Here’s a detailed breakdown of partial order planning:
1. **Partial Order**: Actions are partially ordered, meaning that only some actions need to
follow others, while others can be executed in any sequence that maintains the plan's
consistency.
2. **Causal Links**: These represent dependencies between actions. A causal link from action
A to action B indicates that the effect of A is a precondition for B.
3. **Open Conditions**: These are preconditions of actions that have not yet been satisfied by
any preceding action. During the planning process, the planner must find actions that can
satisfy these open conditions.
4. **Threats**: These occur when an action can potentially interfere with the causal link
between two other actions. Resolving threats is a critical part of maintaining a consistent
plan.
### Steps ==1. **Initial State and Goal Specification**: Define the initial state of the world and
the goal state that the plan aims to achieve.
2. **Create Initial Plan**: Start with a simple plan that includes only the initial state and the
goal state with an "empty" sequence of actions in between.
3. **Identify Open Conditions**: Determine which preconditions of the actions in the current
plan are not yet satisfied.
4. **Select Actions to Satisfy Open Conditions**: For each open condition, find an action that
achieves the desired condition and insert it into the plan.
5. **Add Causal Links**: Create causal links between actions to indicate that the effect of one
action satisfies the precondition of another.
6. **Resolve Threats**: Identify and resolve any threats to the causal links. This can involve
reordering actions or introducing new actions to prevent interference. 7. **Iterate**:
Repeat the process of identifying open conditions, selecting actions, adding causal links, and
resolving threats until all open conditions are satisfied and all threats are resolved.