Faculty of Computer ‫كلية الحاسبات والمعلومات‬

and Information Sciences ‫جامعة عين شمس‬

Ain Shams University

Computational Cognitive Science

Code: AIT 311

Instructor

[Link]. Abeer M. Mahmoud

Professor of Computer science-faculty of Computer and Information Sciences-
Ain Shams University
[Link]@[Link]
 Lecture( 3): Introduction

The course slides includes some selected contents from the MIT course on computational cognitive science and with update of the contents
according to the instructor vision and directions
[Link]
 Foundation of Learning

Deductive Learning versus Inductive Learning

3
  Deductive Learning
 Knowledge is deduced from existing knowledge by mean of truth-
preserving transformation (this is nothing more than reformulation
of existing knowledge ).
 If the premises is true the conclusion must be true
 Conclusion follows with certainty.
 Validity depends only on syntax (form).

 Example

4
  Inductive Learning :Generalization from examples
 Inductive learning: system tries to induce a “general rule” from a set of
observed instances.
 Process of reasoning in which the premises of an argument are believed
to support the conclusion but do not ensure it.
 Conclusion follows with more or less probability.
 Probability depends on semantics (meaning).
 Argument evaluation is subjective, depends on other knowledge
available.

5
Inductive Learning

 Prior analytics: How can we reliably infer new truths from

known truths?
 A theory: Symbolic logic.
 A schema for induction:

6
Computational approaches to induction

Two main ingredients:

Knowledge representation Statistics:

how to capture the how to capture the
structure of the world structure of the world.

7
Inductive learning
 Simplest form: learn a function from examples

f is the target function

An example is a pair (x, f(x))

Problem: find a hypothesis h

such that h ≈ f
given a training set of examples

8
 Inductive learning method
 Construct/adjust h to agree with f on training set
 (h is consistent if it agrees with f on all examples)
 E.g., curve fitting:

9
 Inductive learning as search
Marr’s three levels
 Level 1: Computational theory
– What is the goal of the computation, and what is the logic by which it is
carried out?
 Level 2: Representation and algorithm
– How is information represented and processed to achieve the computational
goal?
 Level 3: Hardware implementation
– How is the computation realized in physical or biological hardware?

10
 Level 1: Computational theory

 What is a concept?
A rule that divides the objects into two sets: positive instances and
negative instances.

 What does it mean to learn a concept successfully?

Given N randomly chosen “training” examples (objects labeled positive or negative),
and a space H of hypotheses (candidate rules), find a hypothesis h that is consistent
with the training examples
 What kinds of concepts can be learned? Under what conditions?
From how much data?
 What assumptions must be made for learning to succeed?

11
 Level 2: Representation and algorithm

 How are objects and concepts represented?

 How much memory (space) and computation (time)
 does a learning algorithm require?
 Is the algorithm online or batch (serial or parallel)?
 What kinds of concepts are learned most easily (or most
reliably) by a particular algorithm?

12
 find-S algorithm

13
 Introduction

 The find-S algorithm is a basic concept learning algorithm in

machine learning.

 The find-S algorithm finds the most specific hypothesis that fits
all the positive examples.

 We have to note here that the algorithm considers only those

positive training example.

 The find-S algorithm starts with the most specific hypothesis

and generalizes this hypothesis each time it fails to classify an
observed positive training data. Hence, the Find-S algorithm
moves from the most specific hypothesis to the most general
hypothesis.
14
Important Representation :

 ? indicates that any value is acceptable for the attribute. specify a

single required value ( e.g., Cold ) for the attribute.
 0 indicates that no value is acceptable.
 The most general hypothesis is represented by: {?, ?, ?, ?, ?, ?}
 The most specific hypothesis is represented by: {0, 0, 0, 0, 0, 0}

15
 Steps Involved In Find-S :

1. Start with the most specific hypothesis. h = {0, 0, 0, 0, 0, 0}

2. Take the next example and if it is negative, then no changes
occur to the hypothesis.
3. If the example is positive and we find that our initial hypothesis
is too specific then we update our current hypothesis to a
general condition.
4. Keep repeating the above steps till all the training examples
are complete.
5. After we have completed all the training examples we will have
the final hypothesis when can use to classify the new
examples.

16
 Algorithm :

1. Initialize h to the most specific hypothesis in H

2. For each positive training instance x
For each attribute constraint a, in h
If the constraint a, is satisfied by x
Then do nothing
Else replace a, in h by the next more general
constraint that is satisfied by x
3. Output hypothesis h

17
 Example :

Consider the following data set having the data about

which particular seeds are poisonous.

18
First, we consider the hypothesis to be a more specific. Hence, : h = {0, 0, 0, 0}

Consider example 1 :
The data in example 1 is { GREEN, HARD, NO, WRINKLED }. We see that our initial hypothesis is
more specific and we have to generalize it for this example. Hence, the hypothesis becomes
: h = { GREEN, HARD, NO, WRINKLED }

Consider example 2, and 3 :

Here we see that this example has a negative outcome. Hence we neglect this example and our
hypothesis remains the same. h = { GREEN, HARD, NO, WRINKLED }
Consider example 4 :
The data present in example 4 is { ORANGE, HARD, NO, WRINKLED }. We compare every single
attribute with initial data and if any mismatch is found we replace attribute with a general case ( ” ? ” ).
After doing the process the hypothesis becomes : h = { ?, HARD, NO, WRINKLED }

19
 h = { ?, HARD, NO, WRINKLED }

Consider example 5 :
The data present in example 5 is { GREEN, SOFT, YES, WRINKLED }. We compare every single
attribute with the initial data and if any mismatch is found we replace that particular attribute with a
general case ( ” ? ” ). After doing the process the hypothesis becomes :
h = { ?, ?, ?, WRINKLED }

Since we have reached a point where all the attributes in our hypothesis have the general condition,
example 6 and example 7 would result in the same hypothesizes with all general attributes.
h = { ?, ?, ?, WRINKLED }

Hence, for the given data the final hypothesis would be :

Final Hyposthesis: h = { ?, ?, ?, WRINKLED }
20 8 Red Soft No smooth ………
 Test Yourself
Q1: f1 f2 f3 f4 f5 f6 label
X1 1 1 1 0 1 0 +
X2 0 0 0 0 0 1 -
X3 1 1 0 0 1 1 +
X4 1 1 1 1 1 0 _
X5 0 1 0 1 1 1 +
x6 0 0 0 1 1 0
Q2:

21
 Test Yourself

Eyes Nose Head Fcolor Hair? Smile?

Eyes Nose Head Fcolor Hair? Smile?

Round Triangle Round Purple Yes Yes
Square Square Square Green Yes No
Square Triangle Round Yellow Yes Yes
Round Triangle Round Green No No
22 Square Square Round Yellow Yes Yes
 Test Yourself
 Define Cognitive Science
 Explain why we consider Cognitive science multi-displinary
field
 How to study cognitive science: Mention the three levels of
Description?
 Mention three ways humans learn things

23
 Test yourself

 Mention four ways of analogy association

 1-
 2-
 3-
 4-

24
 Level 3: Hardware implementation

– How is the computation realized in physical or

biological hardware?

25
 knowledge representation

Non-Logical Representations? logical representation

1. Production rules propositional calculus
2. Semantic networks predicate calculus
Conceptual graphs
Frames
Scripts

26
 Graphical Representation

27
 Graphical Representation

 Graphs easy to store in a computer

 To be of any use must impose a formalism

 Jason is 15, Bryan is 40, Arthur is 70, Jim is 74

 How old is Julia?
28
 Semantic Networks

 Because the syntax is the same

 We can guess that Julia’s age is similar to Bryan’s
 Formalism imposes restricted syntax
29
 Semantic Networks

In this scheme , knowledge is represented in terms of objects and

relationships between objects

The objects are denoted as nodes of a graph. The relationship

between two objects are denoted as a link between the
corresponding two nodes

Links indicate subset, member, relation, ...

The most common form of semantic network uses the link

between nodes to represent IS-A and HAS relationships between
objects

30
 Example of semantic network

31
 ANIMAL

MAMMAL BIRD

CARNIVORE

HAIR MILK
FEATHERS LAYS
PRODUCTION
EGGS
FLYS
FORWARD FORWARD EATS CLAWS
EYES TEETH MEAT

32 A Semantic network for animal kingdom

 c o v e re d _ b y
a n im a l
tr a v e ls _ b y s k in
fly in g
is a is a
tr a v e ls _ b y
b ir d fis h
fe a th e rs
c o v e re d _ b y s w im m in g

is a is a is a is a

o s tr ic h p e n g u in c a n a ry r o b in

tr a v e ls _ b y c o lo u r
c o lo u r

w a lk in g y e llo w
tr a v e ls _ b y

re d

Your in s ta n c e _ o f

in s ta n c e _ o f

Turn
O pus
T w e e ty

c o lo u r
33 w h ite
 Test Yourself
Create a semantic network to describe a car. Your network should include the
concepts: car, driver, engine, petrol, petrol tank, and road

34
 Example:
Birds fly.
Canaries are birds.
Penguins are birds.
Tweety is a canary.
Opus is a penguin.
Does Tweety fly?
Does Opus fly?

35
 Frames
o In this technique, knowledge is decomposed into highly
modular pieces called frames, which are generalized record
structures

o Knowledge consist of concepts, situation, attributes of

concepts , relationships between concepts , and procedure to
handle relationships

 Each concept may be represented as a separate frame

 Frame with a number of slots (age, height, ...)
 Each slot stores specific item of information
 The contents of a slot may be of any data type –numbers, strings,
functions or procedures and so on
 The frames may be linked to other frames, providing the same
kind of inheritance as that provided by a semantic network
 Inheritance of properties between frames Very similar to objects
36 in OOP
 Frames
 Basic frame design

Frame Name: Object1

Class: Object2

Properties: Property1 Value1

Property2 Value2
*** ***
*** ***

37
 Frame Representation of the “cow”

Frame Name: Cow

Class: Mammal
Properties: SKIN Cover Hair
Activity Produce Milk
tail Long tail
*** ***

38
 Your Turn

Chair frame

39
 Your Turn

A cat is a small, typically furry, carnivorous mammal. Cats can hear sounds too faint or too high .
They can see in near darkness. They have Sharp claws and soft pads. A cat's senses are superior
amongst the animal world, with exceptional sight, smell and taste.

A Horse is a mammal with hooves. They also have long tails, short hair, long thick necks and
elongated heads. Horses use speed to escape predators and they have a well-developed sense of
balance and a strong fight. They can sleep both lying down and standing up.

Dolphins live in fluid social groups called pods. Even though they live in the ocean all of the time,
dolphins are mammals, not fish. Dolphins are warm blooded. They breathe air using lungs.
Dolphins must make frequent trips to the surface of the water to catch a breath. They give birth to
live young rather than laying eggs and they feed their young with milk.
40
41
 Thanks
for your attention

42