Transcript Document

AI: Basic Concepts
M.C. Juan Carlos Olivares Rojas
[email protected]
February, 2009
Outline
1.1 Basic Concepts
1.2 Applications
1.3 Intelligent Systems and Learning
1.4 Semantic Networks
1.5 Description and Match Method
Outline
1.6 Analogy Problems
1.7 Abstraction Recognition
1.8 Knowledge Interpretation
Space Oddisey 2001
• What are the principal features about Artificial
Intelligence of this movies?
• Quiz 1
• ¿What’s the name of the computer?
• ¿What are the nam of the human travelers in
the spaceshift?
• ¿When te computer was elaborated?
• ¿Whose write the movie script?
Basic Concepts
• What’s the diference bewtween Artificial
Intelligence (AI) and Human Intelligence?
• All the sucessfully AI Systems are based on
human knowledge and experience.
• Most of the AI Systems can be costructed
only when the human intelligence can be
expresed in easily form (for instance: if x then
y).
Basic Concepts
• AI Systems extend human experts, but never
can’t substituting either “taken” most of
human intlligence.
• AI Systems don’t have common sense and
generallity of human beings.
• Human Intelligence are very complex for
computing.
Basic Concepts
If a problem can not be described, then can not
be programmed
• Human Intelligence have these features:
Reasoning.
Behavior.
Use of Metaphores and Analogies.
Concepts Creating and Use.
Problem
• Make a Java Program which calculate if a
number give for the user is a Perfect Number
or not.
• What are the steps for solving this problem?
Inteligence
• Capacity to solution all clasess of problems
• Intelligence is very subjective.
• “Intelligence Distinguished man of animals”
• AI is an interdiciplinary science which
involves phylosophy, matemathics, biology,
electronics, etc,
Turing Test
• Alan M. Turing defined in 1950 one form to
check if a machine is intelligent or not.
• Turing test consist to set two human and one
machine in a dark room. The humans and the
machine are not visible between their.
• One human must act like an Interviewer
asking some questions to the other
participants.
Turing Test
• Turing Test is passed when the interviewer
can not distinguished the answer between the
human and the machine.
• The new AI systems required the perception
sense to pass the test.
AI Genesys
• Martin Minsky did cotributions to define brain
models in computers.
• ELIZA of Joseph Weizenbaum and JULIA of
Mauldin were the first AI Systems with
Intelligent Dialagues.
• The first AI Systems were development for
solving some problems like chess.
Génesis de la IA
• In 1956 John McCarthy and Claude Shanon
published “Automata Studies” where defined
the Automata Theory.
• In 1956 John McCarthy defined the AI
concept, reason why he is considered the AI
Father.
• The AI history is very old. The greeks were
the first to use logic to solve a lot of problems.
AI Genesys
• In 1965 Chomsky
Languages Theories.
defined
the
Formal
• McCulloh and Pits in 1943 define the relations
between neurons and simple computational
elements.
• In 1962 Rosenblatt defined the Perceptron
and the Neuronal Networks Teories.
Homeworks
• Delivery: 05/02/09
• Activitie 1: Make a timeline with the history of
AI. 40%
• The timeline must be doing with a special
software.
• The timeline must include antoher events
Homeworks
• Activitie 2: Research about cognitive science.
40%
• What are the cognitive science?
• What are the most important things in
cognitive science
• Remember 20% are for the work format
1.2 Applications
• Solution Search
• Expert System
• Natural
Language
Recognition
• Logic
• Games
• Neuronal Networks
• Pattern Recognition
• Genetic Algorithms
• Robotic
• Machine Learning
• Virtual Reality
Maze Problem
• Additional Homework: Study Graph Theory,
Discret Mathematics, Computing Theory
(Compilers). Arrays in some high-level
programming languages.
• How a person in a maze can be exit without
lost?
• Are there an optimal solution for the problem?
Solution Search
• The search term appliend in AI, it’s not mean
find a specific information piece in a data
reporsitory, this term implies to obtain the
best solution for a problem. For instance:
• Finding the shortest path between two cities,
or the famus “Travelling Sales Problem”
(TSP). This is a NP-Complete (Not Polinomal)
Problem.
TSP
TSP
Expert Systems
• They were the first AI comercial product
sucessfully.
• These Systems let to introduce some
information in an specific knowledge area into
a computer (knowledge database), they act
like a human expert.
• These Systems simulate human reasoning
by applicating especific knowledge and
inferences.
Natural Language Processing
• It’s a complex problem. For example (in
spanish):
• “Ideas
verdes
furiosamente”,
descoloridas
• “Ideas furiosamente
duermen”.
verdes
duermen
descoloridas
Natural Language Processing
“El banco cierra a las 3:00”
“Las almejas están listas para comer”
“Las almejas están listas para [ser] comidas
[por nosotros]”
Artificial Vision
• It’s an application of patter recognition, this
area have a lot of application such as:
•
•
•
•
•
Medical Diagnostic
Automatic Signal Processing
Automatic Industrial Product
Automatic Vigilance Systems
OCR (Optical Character Recognition)
Robotic
• This science implies the concepts of
perception, motion (spatial reasoning),
planning.
• The main problem autonomous robots are
interacting with the human-world, because
exists many obstacles unexpected events
and dinamic environments.
Learning
• This area studies the way in how computers
can obtain new knowledge to solve a
problem.
• In
this sense, learning means to make a
computer which is able to benefit for the
experience obtained.
Games
• AI is applied in games to give more realism
and complexity. Also AI gives the “Physics”.
• The n-queens problem consist in putting n
chess queens on an n×n chessboard such
that none of them is able to capture any other
using the standard chess queen's moves.
• Activitie: Obtain a Solution in a sheet of paper
for a 5x5 chessboard. First 100, Second 80,
Third 60 pts.
• It’s
Genetic Algorithms
a computational technique inspired in
biological models which are used to realize
eficient search in spatial solution highly huge
and complex.
• Genetic Algorithms are adaptative methods
which can used to implement searches and
optimization problems.
• This
has given the creation of emergence
areas such as evolutionary computation and
swarm computing algorithms that rely on
events of nature.
The Game of Life
• The Game of Life, also known simply as Life, is
a cellular automaton devised by the British
mathematician John Horton Conway in 1970. It
is the best-known example of a cellular
automaton.
• The "game" is actually a zero-player game,
meaning that its evolution is determined by its
initial state, needing no input from human
players. One interacts with the Game of Life by
creating an initial configuration and observing
how it evolves.
The Game of Life
• The universe of the Game of Life is an infinite
two-dimensional orthogonal grid of square cells,
each of which is in one of two possible states,
live or dead.
•
• Every cell interacts with its eight neighbours,
which are the cells that are directly horizontally,
vertically, or diagonally adjacent. At each step
in time, the following transitions occur:
The Game of Life
• Any live cell with fewer than two live neighbours
dies, as if by needs caused by underpopulation.
• Any live cell with more than three live
neighbours dies, as if by overcrowding.
• Any live cell with two or three live neighbours
lives, unchanged, to the next generation.
• Any dead cell with exactly three live neighbours
becomes a live cell.
The Game of Life
The Game of Life
• Find an initial solution with under 16 live cells.
The best aproximation wins 100, second 80,
third 60 points.
• Play the game at: www.bitstorm.org/gameoflife/
Virtual Reality
• It’s one of the most recent applications of AI.
It’s consist in the construction of programs
which achive to fool the human senses, make
it belive that we are floating, running or flying
in an airplane.
• This application has been used in a fligth
simulator for pilots, astronauts and drivers.
Intelligent Systems and Learning
• Most of the actual system say that they are
intelligents (“smart”).
• If an application can take autonomous
decisions in a real time in independet form,
it’s considered intelligent. The main feature of
this systems are the “adaptability” like saving
energy.
Intelligent Systems and Learning
• The most important feature of an Intelligent
System are the way to representing the
knowledge, the way in which the information
is retrived and the way in which adquire new
knowledge (learning).
• The representation ways (“explicitation”) of
knowledge are diverse and it influences in the
retrival informtion and learning ways.
Intelligent Systems and Learning
• Always that a model is developed it has two
represetation: logical and physical.
• This representations
working together.
need
“mapping”
to
• When we have a real life problem, this have
to mapping in a computer schema for working
in a computational system.
Intelligent System and Knowledge
• Tacking back to the Maze Problem ¿How can
be represent this model and the knowledge?
• It can be represented with a matrix, graph,
finite state machine, etc. Also it must rules for
play this game.
• If we don’t have the two representations we
can not understand and learn the game.
Intelligent Systems and Knowledge
• In general, knowledge s define by laws and
particular languages. Languages define rules.
• The same knowledge is structured in
diferents represtentation such as database,
semantic networks,
frames, conceptual
maps, etc., but after all it must have the same
meaning (semantics).
Homework and Activity
•
•
•
•
Homework: conceptual maps.
10% Format
10% Basic Concepts
40% Conceptual Map for a student well-know
topic
• 40% Conceptual Map for a any AI topic.
• Note: the conceptual maps must
development in a computational tool.
be
Homework and Activity
• Activity: programming the Game of Life using a
High-Level language with a 8x8 matrix.
• The program can be in text mode and the user
only can set the initial configuration. Using a
BitMap Matrix (0 and 1 values)
• Activity: programming the right-hand heuristic
for solve a maze introduced for a used.
Homework and Activity
• ExtraPoint: programming a maze generator.
The maze only have one input and one output
(It can be the same that input).
• The maze generation must be ordened by a
algorithm using a spatial solution search.
• An easy way is put the input and output,
generate one path (the correct path) and later
generate other incorrect paths, beginning of the
correct path.
Maze Generator
We must try to don´t
generate a loop
Cellular Automata
• It’s a discrete model studied in computing,
mathematics, biology and microstructure
modeling.
• It consists of a regular grid of cells, each in one
of a finite number of states. The grid can be in
any finite number of dimensions.
• Time is also discrete, and the state of a cell at
time t is a function of the states of a finite
number of cells (neighborhood) at time t − 1.
Cellular Automata
• These neighbors are a selection of cells relative
to the specified cell, and do not change (though
the cell itself may be in its neighborhood, it is
not usually considered a neighbor).
• Every cell has the same rule for updating,
based on the values in this neighbourhood.
Each time the rules are applied to the whole
grid a new generation is created.
Cellular Automata
Rule 30
Pattern 111
State
110 101
0
0
Rule 110
0
100
011
010
001
000
1
1
1
1
0
Pattern
111 11
0
101
100
011
010
001
000
State
0
1
0
1
1
1
0
1
Semantic Networks
• They are other simple form to explicity
knowledge, They are conformed by graphs
which coding knowledge in a taxonomic form.
• Nodes represent categories and Edges
represents the relations between this
categories.
• There are two types of special relatinoships:
Is-A y la Have-A.
Semantic Networks
• We can access throught of each concepts to
infer knowledge.
• The scripts are other way to represent
knowledge. They are composed by
components called slots, these are a set of
elements concept-values.
• Scripts are more easily to ntroduce than mind
maps.
Semantic Networks
Script
Script Example:
Printers
Subset_of: Office_Machine
Superset_of: {Laser_Printer, Inject_Printer}
Feed_Source: Door_Socket
Author: Juan_Perez
Date: 07_January_2008
Onthologies
• Other way to represent knowledge with a lot
of use recently is Onthology, It’s consist of
relations between distinct concepts like
definitions. Onthologies can be represented
throught languages such as XML.
• Knowledge representation has a great
importance this is the reason because
actually
we
talk
about
Knowledge
Engineering.
Semantic Networks
• Onthologies act like a dictionary. Some
elements like agents used this information to
represent and retrieve knowledge.
• Frames are structure used to represent
values, restricctions, process, relation, etc.
Frames represent with tuples one propertie of
an object. Object-Oriented Programming was
originated by Frames.
Concept Mind
Onthology
Activity
• Represent one object (one diferent per
student, e.g. Wireless Network Card,
Telephone, Cow, etc.) and all its features with
an Ontology, Script and Frame.
The Description and Match Method
• It’s used for AI problem solving and It’s one
the most basic method.
• The first step consists to identified all features
of an object.
• Later, It realice a seach in a well-define set of
objects.
• It needs two very import methods: the
extractor and evaluator of knowledge.
The Description and Match Method
• When the match process is doing, one
posibility is the object don’t be the same
pattern in the knowledge Database. This is
the reason because We need a Similarity
Function.
• For Example (In Spanish):
AMOR
Love a person or thing for over all things
Word composeb dy 4 characters: ‘A’, ‘M’, ‘O’ and
‘R’ yuxtapuestos
The Description and Match Method
• AMOR = AMOR Exact Macth
• AMOR = ROMA 0% similarity but contains for
characters
• Amor = AMOR 25% similarity, contains all
character but in uppercase
• Amor = Cariño 0% similarity but the same
meaning
• Amor = Amar 75% it’s a consequence
The Description and Match Method
Circle
Description:
Figure formed by al the points which distance are
equidistant of the center point in an angle of 0 a 360
grades.
Properties:
Center (point)
Diametrer (twice radio)
Areas
The Description and Match Method
=
=
100% Similarity
?% Have the same form but diferent size
and color
?% Have the same high but diferent
width
=
?% Have the same color
=
The Description and Match Method
• It`s used in multiples branches such as:
–
–
–
–
–
Digital Fingerprint Recognition
Voice Recognition
Natural Language Recognition
Software Requirement Validation
Etc.
• We must represent in a correct form the
knowledge if We can compare.
The Farmer, Fox, Goose and Wheat Problem
• A farmer wants to move himself, a silver fox,
a fat goose, and some tasty grain across a
river, from the west side to the east side.
Unfortunately, his boat is so small he can
take at most one of his possessions across
on any trip. Worse yet, an unattended fox will
eat a goose, and an unattended goose will
eat grain, so the farmer must not leave the
fox alone with the goose or the goose alone
with the grain. What is he to do?
The Farmer, Fox, Goose and Wheat Problem
Farmer
Fox
Goose
Wheat
Farmer
Fox
Goose
Wheat
¿Se puede utilizar el método de descripción y
pareamiento?
The Farmer, Fox, Goose and Wheat Problem
Wheat
Farmer
Fox
Goose
Farmer
Fox
Goose
Wheat
Fox
Farmer
Goose
Wheat
Fox
Wheat
Farmer
Goose
Fox
Goose
Wheat
Farmer
Goose
Wheat
Fox
Farmer
Wheat
Farmer
Fox
Goose
Farmer
Fox
Wheat
Goose
Fox
Goose
Wheat
Farmer
Farmer
Goose
Wheat
Fox
Goose
Wheat
Farmer
Fox
Farmer
Fox
Goose
Wheat
Farmer
Goose
Fox
Wheat
Farmer
Fox
Goose
Fox
Goose
Wheat
Wheat
Farmer
Farmer
Fox
Goose
Wheat
Activity
• In a Software Development Company 5
programers implement the same algorithms
obtained the follow results:
Programmer
LOC
Return
1
2
3
4
5
66
41
68
90
75
20
10
5
34
12
Function
Call
1
2
8
5
14
Activity
• The enterprise needs to know how are the best
pair (pair programing).
• For trying to solve this problem We need to
define a similarity function such as:
• s(v, w)=|p1-q1| + |p2-q2| + |p3-q3|
• Where:
• v and w are programmers represent in the form
of (p1, p2, p3)
Activity
• pi is a propertie
• We also need a criteria for similarity in this case
consider the lower punctuation as the best
solution.
• Programming the solution to obtain the best
pair.
• Programming the solution to obtain the best
pair in a specific propertie
Activity
• If We changed the criteria in where LOC are
more important 60% than the other properties,
how must be the new similarity function?
• If We need one group with the 3 best
programmer, how must be the similarity
function?
Analogy Problems
• It’s other form to problem solving tha it’s used
in AI.
• Analogy is a special type of relation that
define how are objects represented los
objetos de una categoría y como obtener sus
predecesores y antecesores inmediatos.
• Generalmente se habla de análogo cuando
se tiene el mismo tipo de relación aun cuando
sean entidades diferentes.
Problemas de Analogías
Alguna vez nos hemos preguntado ¿por qué en
la mayoría de los exámenes de admisión
generalmente son más importantes que los
de conocimientos?
Por que en la mayoría de los casos el
conocimiento de cierta forma se puede
adquirir pero la forma de aprender y razonar
es sumamente complicado. En muchos casos
son más importantes las reglas que el
Problemas de Analogías
En matemáticas y en el área de programación
se utiliza mucho la analogía para resolver
problemas.
De acuerdo con Polya, para resolver problemas
se necesita de los siguientes pasos:
1) Comprender el problema
2) Concebir un plan
3) Ejecutar el plan y,
4) Examinar la solución.
Problemas de Analogías
A
B
C
1
2
3
¿Cómo quedarían D y 5?
4
Problemas de Analogías
¿Qué problemas se presentan con la
Abstracción de la Figura D o bien de la Figura
3?
A
B
C
1
2
La resolución de problemas por analogía tiene
como base cierto conocimiento previo en
ocasiones difícil de obtener.
Reconocimiento de Abstracciones
A lo largo de esta presentación se ha podido
comprobar que prácticamente el problema
está resuelto si el problema está descrito.
El reconocimiento de abstracciones es un
concepto muy subjetivo dado que éstas son
combinaciones de estados mentales y
eventos.
Los SI se basan fundamentalmente en reglas
Reconocimiento de Abstracciones
Generalmente respondemos a estímulos
(eventos), y en base a ellos vemos cuales
son importantes para nosotros y nos
comportamos de cierta manera.
Para lo que a una persona le representa algo
para otra representa cosas totalmente
distintas.
La abstracción permite llegar a cierto tipo de
Interpretación del Conocimiento
La interpretación del conocimiento, es decir la
utilización de ese conocimiento es un factor
muy importante que aun la IA no ha podido
definir bien.
El conocimiento se puede interpretar de
muchas formas y sus áreas de aplicación son
diversas.
Existen muchas corrientes filosóficas que le
tratan de dar sentido al conocimiento:
Interpretación del Conocimiento
Se pretende que las reglas y hechos (base de
conocimientos) permitan resolver problemas
y que a su vez de la resolución de estos
problemas se obtenga nuevos conocimientos.
Homework
• Make a survey (Caracterization) about the
frecuencie of each character in Spanish Alfabet.
For example, in % how many ‘c’ appears.
• This
surve
will
aplied
Cryptoanalisys System.
on
Inteligent
• Research about cryptograph system
transposition and substitution algorithms.
by
Bibliografía
Decker, R. y Hirshfield, S. (2001). Máquina
Analítica. Introducción a las Ciencias de la
Computación con Uso de Internet, Thomson,
México. Capítulo 9 Inteligencia Artificial pp.
295-325.
Hernández, V. (2007). Mapas Conceptuales La
gestión del Conocimiento en la Didáctica.
Segunda Edición, México: Alfaomega.
Bibliografía
G. Polya, (1982), “Cómo Plantear y Resolver
Problemas”, traducción al español de “How to
Solve It”, Ed. Trillas, México, 1982, ISBN:
968-24-0064-3.
Montes, M. y Villaseñor L. (2008) Fundamentos
de Inteligencia Artificial Métodos básicos de
solución de problemas, Instituto Nacional de
Astrofísica, Óptica y Electrónica, Puebla,
México.
Bibliografía
Winston, P. (1992) Artificial Intelligence, 3ra.
Edición, Addison-Wesley.
Questions?