http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html
VISIT THIS WEB PORATL FOR ALL DETAILED INFORMATION ON NEURAL NETWORK AND THE FIGURES PRETAINING TO NEURAL NETWORK DESIGN
Sunday, September 28, 2008
NEURAL NETWORKS DETAIL
NOTE ALL THE FIGURES OF THE TOPIC STATED UNDER ARE POSTED UNDER A SEPARATE POST OF FIGURES NEUAL NETWORK
What is a Neural Network?
An Artificial Neural Network (ANN) is an information processing paradigm that is inspired by the way biological nervous systems, such as the brain, process information. The key element of this paradigm is the novel structure of the information processing system. It is composed of a large number of highly interconnected processing elements (neurones) working in unison to solve specific problems. ANNs, like people, learn by example. An ANN is configured for a specific application, such as pattern recognition or data classification, through a learning process. Learning in biological systems involves adjustments to the synaptic connections that exist between the neurones. This is true of ANNs as well.
Why use neural networks?
1Adaptive learning: An ability to learn how to do tasks based on the data given for training or initial experience.
2Self-Organisation: An ANN can create its own organisation or representation of the information it receives during learning time.
3Real Time Operation: ANN computations may be carried out in parallel, and special hardware devices are being designed and manufactured which take advantage of this capability.
4Fault Tolerance via Redundant Information Coding: Partial destruction of a network leads to the corresponding degradation of performance. However, some network capabilities may be retained even with major network damage.
4 Architecture of neural networks
4.1 Feed-forward networks
Feed-forward ANNs (figure 1) allow signals to travel one way only; from input to output. There is no feedback (loops) i.e. the output of any layer does not affect that same layer. Feed-forward ANNs tend to be straight forward networks that associate inputs with outputs. They are extensively used in pattern recognition. This type of organisation is also referred to as bottom-up or top-down.
4.2 Feedback networks
Feedback networks (figure 1) can have signals travelling in both directions by introducing loops in the network. Feedback networks are very powerful and can get extremely complicated. Feedback networks are dynamic; their 'state' is changing continuously until they reach an equilibrium point. They remain at the equilibrium point until the input changes and a new equilibrium needs to be found. Feedback architectures are also referred to as interactive or recurrent, although the latter term is often used to denote feedback connections in single-layer organisations.
Figure 4.1 An example of a simple feedforward network
(ALL FIGURES ARE PUBLISHED SEPARATELY UNDER THE SUB HEADING & SEPARATE POST OF-
"FIGURES NEURAL NETWORKS")
Figure 4.2 An example of a complicated network
4.3 Network layers
The commonest type of artificial neural network consists of three groups, or layers, of units: a layer of "input" units is connected to a layer of "hidden" units, which is connected to a layer of "output" units. (see Figure 4.1)
The activity of the input units represents the raw information that is fed into the network.
The activity of each hidden unit is determined by the activities of the input units and the weights on the connections between the input and the hidden units.
The behaviour of the output units depends on the activity of the hidden units and the weights between the hidden and output units.
This simple type of network is interesting because the hidden units are free to construct their own representations of the input. The weights between the input and hidden units determine when each hidden unit is active, and so by modifying these weights, a hidden unit can choose what it represents.
We also distinguish single-layer and multi-layer architectures. The single-layer organisation, in which all units are connected to one another, constitutes the most general case and is of more potential computational power than hierarchically structured multi-layer organisations. In multi-layer networks, units are often numbered by layer, instead of following a global numbering.
4.4 Perceptrons
The most influential work on neural nets in the 60's went under the heading of 'perceptrons' a term coined by Frank Rosenblatt. The perceptron (figure 4.4) turns out to be an MCP model ( neuron with weighted inputs ) with some additional, fixed, pre--processing. Units labelled A1, A2, Aj , Ap are called association units and their task is to extract specific, localised featured from the input images. Perceptrons mimic the basic idea behind the mammalian visual system. They were mainly used in pattern recognition even though their capabilities extended a lot more.
Figure 4.4
In 1969 Minsky and Papert wrote a book in which they described the limitations of single layer Perceptrons. The impact that the book had was tremendous and caused a lot of neural network researchers to loose their interest. The book was very well written and showed mathematically that single layer perceptrons could not do some basic pattern recognition operations like determining the parity of a shape or determining whether a shape is connected or not. What they did not realised, until the 80's, is that given the appropriate training, multilevel perceptrons can do these operations.
Applications of neural networks
Since neural networks are best at identifying patterns or trends in data, they are well suited for prediction or forecasting needs including:
1sales forecasting
2industrial process control
3customer research
4data validation
5risk management
6target marketing
7Neural networks in medicine
8Modelling and Diagnosing the Cardiovascular System
9Neural Networks in business
What is a Neural Network?
An Artificial Neural Network (ANN) is an information processing paradigm that is inspired by the way biological nervous systems, such as the brain, process information. The key element of this paradigm is the novel structure of the information processing system. It is composed of a large number of highly interconnected processing elements (neurones) working in unison to solve specific problems. ANNs, like people, learn by example. An ANN is configured for a specific application, such as pattern recognition or data classification, through a learning process. Learning in biological systems involves adjustments to the synaptic connections that exist between the neurones. This is true of ANNs as well.
Why use neural networks?
1Adaptive learning: An ability to learn how to do tasks based on the data given for training or initial experience.
2Self-Organisation: An ANN can create its own organisation or representation of the information it receives during learning time.
3Real Time Operation: ANN computations may be carried out in parallel, and special hardware devices are being designed and manufactured which take advantage of this capability.
4Fault Tolerance via Redundant Information Coding: Partial destruction of a network leads to the corresponding degradation of performance. However, some network capabilities may be retained even with major network damage.
4 Architecture of neural networks
4.1 Feed-forward networks
Feed-forward ANNs (figure 1) allow signals to travel one way only; from input to output. There is no feedback (loops) i.e. the output of any layer does not affect that same layer. Feed-forward ANNs tend to be straight forward networks that associate inputs with outputs. They are extensively used in pattern recognition. This type of organisation is also referred to as bottom-up or top-down.
4.2 Feedback networks
Feedback networks (figure 1) can have signals travelling in both directions by introducing loops in the network. Feedback networks are very powerful and can get extremely complicated. Feedback networks are dynamic; their 'state' is changing continuously until they reach an equilibrium point. They remain at the equilibrium point until the input changes and a new equilibrium needs to be found. Feedback architectures are also referred to as interactive or recurrent, although the latter term is often used to denote feedback connections in single-layer organisations.
Figure 4.1 An example of a simple feedforward network
(ALL FIGURES ARE PUBLISHED SEPARATELY UNDER THE SUB HEADING & SEPARATE POST OF-
"FIGURES NEURAL NETWORKS")
Figure 4.2 An example of a complicated network
4.3 Network layers
The commonest type of artificial neural network consists of three groups, or layers, of units: a layer of "input" units is connected to a layer of "hidden" units, which is connected to a layer of "output" units. (see Figure 4.1)
The activity of the input units represents the raw information that is fed into the network.
The activity of each hidden unit is determined by the activities of the input units and the weights on the connections between the input and the hidden units.
The behaviour of the output units depends on the activity of the hidden units and the weights between the hidden and output units.
This simple type of network is interesting because the hidden units are free to construct their own representations of the input. The weights between the input and hidden units determine when each hidden unit is active, and so by modifying these weights, a hidden unit can choose what it represents.
We also distinguish single-layer and multi-layer architectures. The single-layer organisation, in which all units are connected to one another, constitutes the most general case and is of more potential computational power than hierarchically structured multi-layer organisations. In multi-layer networks, units are often numbered by layer, instead of following a global numbering.
4.4 Perceptrons
The most influential work on neural nets in the 60's went under the heading of 'perceptrons' a term coined by Frank Rosenblatt. The perceptron (figure 4.4) turns out to be an MCP model ( neuron with weighted inputs ) with some additional, fixed, pre--processing. Units labelled A1, A2, Aj , Ap are called association units and their task is to extract specific, localised featured from the input images. Perceptrons mimic the basic idea behind the mammalian visual system. They were mainly used in pattern recognition even though their capabilities extended a lot more.
Figure 4.4
In 1969 Minsky and Papert wrote a book in which they described the limitations of single layer Perceptrons. The impact that the book had was tremendous and caused a lot of neural network researchers to loose their interest. The book was very well written and showed mathematically that single layer perceptrons could not do some basic pattern recognition operations like determining the parity of a shape or determining whether a shape is connected or not. What they did not realised, until the 80's, is that given the appropriate training, multilevel perceptrons can do these operations.
Applications of neural networks
Since neural networks are best at identifying patterns or trends in data, they are well suited for prediction or forecasting needs including:
1sales forecasting
2industrial process control
3customer research
4data validation
5risk management
6target marketing
7Neural networks in medicine
8Modelling and Diagnosing the Cardiovascular System
9Neural Networks in business
Thursday, September 25, 2008
example of fuzzy logic
Fuzzy Logic Overview
I've seen a lot of confusion in the first few articles posted to this newsgroup about what, exactly, fuzzy logic is. Since I've been working in the field for five years, I thought I'd help get things started by posting some introductory material. This article covers the question "What is Fuzzy Logic?" from a mathematical point of view. Succeeding articles will cover the questions "What is a Fuzzy Expert System?" and "What is Fuzzy Control?".
Warning: If you're not already familiar with fuzzy logic, you're going to see a lot of new terms defined in this article. I'll try to put _underscores_ around terms that are likely to be new. You may need to read it a few times, just to pick up all the terms.
What is Fuzzy Logic?
Fuzzy logic is a superset of conventional (Boolean) logic that has been extended to handle the concept of partial truth - truth values between "completely true" and "completely false". It was introduced by Dr. Lotfi Zadeh of U.C. Berkeley in the 1960's.
Fuzzy Subsets
There is a strong relationship between Boolean logic and the concept of a subset. There is a similar strong relationship between fuzzy logic and fuzzy subset theory (Note: there is no fuzzy set theory, as far as I am aware - only a fuzzy subset theory).
A subset U of a set S can be defined as a set of ordered pairs, each with a first element that is an element of the set S, and a second element that is an element of the set { 0, 1 }, with exactly one ordered pair present for each element of S. This defines a mapping between elements of S and elements of the set { 0, 1 }. The value zero is used to represent non-membership, and the value one is used to represent membership. The truth or falsity of the statement
x is in U
is determined by finding the ordered pair whose first element is x. The statement is true if the second element of the ordered pair is 1, and the statement is false if it is 0.
Similarly, a fuzzy subset F of a set S can be defined as a set of ordered pairs, each with a first element that is an element of the set S, and a second element that is a value in the interval [ 0, 1 ], with exactly one ordered pair present for each element of S. This defines a mapping between elements of the set S and values in the interval [ 0, 1 ]. The value zero is used to represent complete non-membership, the value one is used to represent complete membership, and values in between are used to represent intermediate _degrees of membership_. The set S is referred to as the _universe of discourse_ for the fuzzy subset F. Frequently, the mapping is described as a function, the _membership function_ of F. The degree to which the statement
x is in F
is true is determined by finding the ordered pair whose first element is x. The _degree of truth_ of the statement is the second element of the ordered pair.
That's a lot of mathematical baggage, so here's an example. Let's talk about people and "tallness". In this case the set S (the universe of discourse) is the set of people. Let's define a fuzzy subset TALL, which will answer the question "to what degree is person x tall?" To each person in the universe of discourse, we have to assign a degree of membership in the fuzzy subset TALL. The easiest way to do this is with a membership function based on the person's height. [erik - I hope this notation is clear]
tall(x) = { 0, if height(x) < 5 ft.,
(height(x)-5ft.)/2ft., if 5 ft. <= height (x) <= 7 ft.,
1, if height(x) > 7 ft. }
A graph of this looks like:
5.0 7.0
height, ft. ->Given this definition, here are some example values: Person Height degree of tallness
--------------------------------------
Billy 3' 2" 0.00 [I think]
Yoke 5' 5" 0.21
Drew 5' 9" 0.38
Erik 5' 10" 0.42
Mark 6' 1" 0.54
Kareem 7' 2" 1.00 [depends on who you ask]
So given this definition, we'd say that the degree of truth of the statement "Drew is TALL" is 0.38.
Note: Membership functions almost never have as simple a shape as tall(x). At minimum, they tend to be triangles pointing up, and they can be much more complex than that. Also, I've discussed membership functions as if they always are based on a single criterion, but this isn't always the case, although it is the most common case. One could, for example, want to have the membership function for TALL depend on both a person's height and their age (he's tall for his age). This is perfectly legitimate, and occasionally used in practice. It's referred to as a two-dimensional membership function. It's also possible to have even more criteria, or to have the membership function depend on elements from two completely different universes of discourse.
Logic Operations
Ok, we now know what a statement like X is LOW
means in fuzzy logic. The question now arises, how do we interpret a statement like X is LOW and Y is HIGH or (not Z is MEDIUM)
The standard definitions in fuzzy logic are: truth (not x) = 1.0 - truth (x)
truth (x and y) = minimum (truth(x), truth(y))
truth (x or y) = maximum (truth(x), truth(y))
which are simple enough. Some researchers in fuzzy logic have explored the use of other interpretations of the AND and OR operations, but the definition for the NOT operation seems to be safe. Note that if you plug just the values zero and one into these definitions, you get the same truth tables as you would expect from conventional Boolean logic.
Some examples - assume the same definition of TALL as above, and in addition, assume that we have a fuzzy subset OLD defined by the membership function:
old (x) = { 0, if age(x) < 18 yr.
(age(x)-18 yr.)/42 yr., if 18 yr. <= age(x) <= 60 yr.
1, if age(x) > 60 yr. }
And for compactness, let a = X is TALL and X is OLD
b = X is TALL or X is OLD
c = not X is TALL
Then we can compute the following values. height age X is TALL X is OLD a b c
------------------------------------------------------------------------
3' 2" 65? 0.00 1.00 0.00 1.00 1.00
5' 5" 30 0.21 0.29 0.21 0.29 0.79
5' 9" 27 0.38 0.21 0.21 0.38 0.62
5' 10" 32 0.42 0.33 0.33 0.42 0.58
6' 1" 31 0.54 0.31 0.31 0.54 0.46
7' 2" 45? 1.00 0.64 0.64 1.00 0.00
3' 4" 4 0.00 0.00 0.00 0.00 1.00
Where is Fuzzy Logic Used?
Directly, very few places. The only pure fuzzy logic application I know of is the Sony PalmTop, which apparently used a fuzzy logic decision tree algorithm to perform handwritten (well, computer lightpen) Kanji character recognition
I've seen a lot of confusion in the first few articles posted to this newsgroup about what, exactly, fuzzy logic is. Since I've been working in the field for five years, I thought I'd help get things started by posting some introductory material. This article covers the question "What is Fuzzy Logic?" from a mathematical point of view. Succeeding articles will cover the questions "What is a Fuzzy Expert System?" and "What is Fuzzy Control?".
Warning: If you're not already familiar with fuzzy logic, you're going to see a lot of new terms defined in this article. I'll try to put _underscores_ around terms that are likely to be new. You may need to read it a few times, just to pick up all the terms.
What is Fuzzy Logic?
Fuzzy logic is a superset of conventional (Boolean) logic that has been extended to handle the concept of partial truth - truth values between "completely true" and "completely false". It was introduced by Dr. Lotfi Zadeh of U.C. Berkeley in the 1960's.
Fuzzy Subsets
There is a strong relationship between Boolean logic and the concept of a subset. There is a similar strong relationship between fuzzy logic and fuzzy subset theory (Note: there is no fuzzy set theory, as far as I am aware - only a fuzzy subset theory).
A subset U of a set S can be defined as a set of ordered pairs, each with a first element that is an element of the set S, and a second element that is an element of the set { 0, 1 }, with exactly one ordered pair present for each element of S. This defines a mapping between elements of S and elements of the set { 0, 1 }. The value zero is used to represent non-membership, and the value one is used to represent membership. The truth or falsity of the statement
x is in U
is determined by finding the ordered pair whose first element is x. The statement is true if the second element of the ordered pair is 1, and the statement is false if it is 0.
Similarly, a fuzzy subset F of a set S can be defined as a set of ordered pairs, each with a first element that is an element of the set S, and a second element that is a value in the interval [ 0, 1 ], with exactly one ordered pair present for each element of S. This defines a mapping between elements of the set S and values in the interval [ 0, 1 ]. The value zero is used to represent complete non-membership, the value one is used to represent complete membership, and values in between are used to represent intermediate _degrees of membership_. The set S is referred to as the _universe of discourse_ for the fuzzy subset F. Frequently, the mapping is described as a function, the _membership function_ of F. The degree to which the statement
x is in F
is true is determined by finding the ordered pair whose first element is x. The _degree of truth_ of the statement is the second element of the ordered pair.
That's a lot of mathematical baggage, so here's an example. Let's talk about people and "tallness". In this case the set S (the universe of discourse) is the set of people. Let's define a fuzzy subset TALL, which will answer the question "to what degree is person x tall?" To each person in the universe of discourse, we have to assign a degree of membership in the fuzzy subset TALL. The easiest way to do this is with a membership function based on the person's height. [erik - I hope this notation is clear]
tall(x) = { 0, if height(x) < 5 ft.,
(height(x)-5ft.)/2ft., if 5 ft. <= height (x) <= 7 ft.,
1, if height(x) > 7 ft. }
A graph of this looks like:
5.0 7.0
height, ft. ->Given this definition, here are some example values: Person Height degree of tallness
--------------------------------------
Billy 3' 2" 0.00 [I think]
Yoke 5' 5" 0.21
Drew 5' 9" 0.38
Erik 5' 10" 0.42
Mark 6' 1" 0.54
Kareem 7' 2" 1.00 [depends on who you ask]
So given this definition, we'd say that the degree of truth of the statement "Drew is TALL" is 0.38.
Note: Membership functions almost never have as simple a shape as tall(x). At minimum, they tend to be triangles pointing up, and they can be much more complex than that. Also, I've discussed membership functions as if they always are based on a single criterion, but this isn't always the case, although it is the most common case. One could, for example, want to have the membership function for TALL depend on both a person's height and their age (he's tall for his age). This is perfectly legitimate, and occasionally used in practice. It's referred to as a two-dimensional membership function. It's also possible to have even more criteria, or to have the membership function depend on elements from two completely different universes of discourse.
Logic Operations
Ok, we now know what a statement like X is LOW
means in fuzzy logic. The question now arises, how do we interpret a statement like X is LOW and Y is HIGH or (not Z is MEDIUM)
The standard definitions in fuzzy logic are: truth (not x) = 1.0 - truth (x)
truth (x and y) = minimum (truth(x), truth(y))
truth (x or y) = maximum (truth(x), truth(y))
which are simple enough. Some researchers in fuzzy logic have explored the use of other interpretations of the AND and OR operations, but the definition for the NOT operation seems to be safe. Note that if you plug just the values zero and one into these definitions, you get the same truth tables as you would expect from conventional Boolean logic.
Some examples - assume the same definition of TALL as above, and in addition, assume that we have a fuzzy subset OLD defined by the membership function:
old (x) = { 0, if age(x) < 18 yr.
(age(x)-18 yr.)/42 yr., if 18 yr. <= age(x) <= 60 yr.
1, if age(x) > 60 yr. }
And for compactness, let a = X is TALL and X is OLD
b = X is TALL or X is OLD
c = not X is TALL
Then we can compute the following values. height age X is TALL X is OLD a b c
------------------------------------------------------------------------
3' 2" 65? 0.00 1.00 0.00 1.00 1.00
5' 5" 30 0.21 0.29 0.21 0.29 0.79
5' 9" 27 0.38 0.21 0.21 0.38 0.62
5' 10" 32 0.42 0.33 0.33 0.42 0.58
6' 1" 31 0.54 0.31 0.31 0.54 0.46
7' 2" 45? 1.00 0.64 0.64 1.00 0.00
3' 4" 4 0.00 0.00 0.00 0.00 1.00
Where is Fuzzy Logic Used?
Directly, very few places. The only pure fuzzy logic application I know of is the Sony PalmTop, which apparently used a fuzzy logic decision tree algorithm to perform handwritten (well, computer lightpen) Kanji character recognition
Wednesday, September 24, 2008
First-Order Logic (FOL or FOPC) Syntax
User defines these primitives:
Constant symbols (i.e., the "individuals" in the world) E.g., Mary, 3
Function symbols (mapping individuals to individuals) E.g., father-of(Mary) = John, color-of(Sky) = Blue
Predicate symbols (mapping from individuals to truth values) E.g., greater(5,3), green(Grass), color(Grass, Green)
FOL supplies these primitives:
Variable symbols. E.g., x, y
Connectives. Same as in PL: not (~), and (^), or (v), implies (=>), if and only if (<=>)
Quantifiers: Universal (A) and Existential (E)
Universal quantification corresponds to conjunction ("and") in that (Ax)P(x) means that P holds for all values of x in the domain associated with that variable. E.g., (Ax) dolphin(x) => mammal(x)
Existential quantification corresponds to disjunction ("or") in that (Ex)P(x) means that P holds for some value of x in the domain associated with that variable. E.g., (Ex) mammal(x) ^ lays-eggs(x)
Universal quantifiers usually used with "implies" to form "if-then rules." E.g., (Ax) cs540-student(x) => smart(x) means "All cs540 students are smart." You rarely use universal quantification to make blanket statements about every individual in the world: (Ax)cs540-student(x) ^ smart(x) meaning that everyone in the world is a cs540 student and is smart.
Existential quantifiers usually used with "and" to specify a list of properties or facts about an individual. E.g., (Ex) cs540-student(x) ^ smart(x) means "there is a cs540 student who is smart." A common mistake is to represent this English sentence as the FOL sentence: (Ex) cs540-student(x) => smart(x) But consider what happens when there is a person who is NOT a cs540-student.
Switching the order of universal quantifiers does not change the meaning: (Ax)(Ay)P(x,y) is logically equivalent to (Ay)(Ax)P(x,y). Similarly, you can switch the order of existential quantifiers.
Switching the order of universals and existentials does change meaning:
Everyone likes someone: (Ax)(Ey)likes(x,y)
Someone is liked by everyone: (Ey)(Ax)likes(x,y)
Sentences are built up from terms and atoms:
A term (denoting a real-world individual) is a constant symbol, a variable symbol, or an n-place function of n terms. For example, x and f(x1, ..., xn) are terms, where each xi is a term.
An atom (which has value true or false) is either an n-place predicate of n terms, or, if P and Q are atoms, then ~P, P V Q, P ^ Q, P => Q, P <=> Q are atoms
A sentence is an atom, or, if P is a sentence and x is a variable, then (Ax)P and (Ex)P are sentences
A well-formed formula (wff) is a sentence containing no "free" variables. I.e., all variables are "bound" by universal or existential quantifiers. E.g., (Ax)P(x,y) has x bound as a universally quantified variable, but y is free.
Translating English to FOL
Every gardener likes the sun.(Ax) gardener(x) => likes(x,Sun)
You can fool some of the people all of the time.(Ex) (person(x) ^ (At)(time(t) => can-fool(x,t)))
You can fool all of the people some of the time.(Ax) (person(x) => (Et) (time(t) ^ can-fool(x,t)))
All purple mushrooms are poisonous.(Ax) (mushroom(x) ^ purple(x)) => poisonous(x)
No purple mushroom is poisonous.~(Ex) purple(x) ^ mushroom(x) ^ poisonous(x) or, equivalently,(Ax) (mushroom(x) ^ purple(x)) => ~poisonous(x)
There are exactly two purple mushrooms.(Ex)(Ey) mushroom(x) ^ purple(x) ^ mushroom(y) ^ purple(y) ^ ~(x=y) ^ (Az) (mushroom(z) ^ purple(z)) => ((x=z) v (y=z))
Deb is not tall.~tall(Deb)
X is above Y if X is on directly on top of Y or else there is a pile of one or more other objects directly on top of one another starting with X and ending with Y.(Ax)(Ay) above(x,y) <=> (on(x,y) v (Ez) (on(x,z) ^ above(z,y)))
Inference Rules for FOL
Inference rules for PL apply to FOL as well. For example, Modus Ponens, And-Introduction, And-Elimination, etc.
New (sound) inference rules for use with quantifiers:
Universal EliminationIf (Ax)P(x) is true, then P(c) is true, where c is a constant in the domain of x. For example, from (Ax)eats(Ziggy, x) we can infer eats(Ziggy, IceCream). The variable symbol can be replaced by any ground term, i.e., any constant symbol or function symbol applied to ground terms only.
Existential IntroductionIf P(c) is true, then (Ex)P(x) is inferred. For example, from eats(Ziggy, IceCream) we can infer (Ex)eats(Ziggy, x). All instances of the given constant symbol are replaced by the new variable symbol. Note that the variable symbol cannot already exist anywhere in the expression.
Existential EliminationFrom (Ex)P(x) infer P(c). For example, from (Ex)eats(Ziggy, x) infer eats(Ziggy, Cheese). Note that the variable is replaced by a brand new constant that does not occur in this or any other sentence in the Knowledge Base. In other words, we don't want to accidentally draw other inferences about it by introducing the constant. All we know is there must be some constant that makes this true, so we can introduce a brand new one to stand in for that (unknown) constant.
Paramodulation
Given two sentences (P1 v ... v PN) and (t=s v Q1 v ... v QM) where each Pi and Qi is a literal (see definition below) and Pj contains a term t, derive new sentence (P1 v ... v Pj-1 v Pj[s] v Pj+1 v ... v PN v Q1 v ... v QM) where Pj[s] means a single occurrence of the term t is replaced by the term s in Pj
Example: From P(a) and a=b derive P(b)
Generalized Modus Ponens (GMP)
Combines And-Introduction, Universal-Elimination, and Modus Ponens
Example: from P(c), Q(c), and (Ax)(P(x) ^ Q(x)) => R(x), derive R(c)
In general, given atomic sentences P1, P2, ..., PN, and implication sentence (Q1 ^ Q2 ^ ... ^ QN) => R, where Q1, ..., QN and R are atomic sentences, and subst(Theta, Pi) = subst(Theta, Qi) for i=1,...,N, derive new sentence: subst(Theta, R)
subst(Theta, alpha) denotes the result of applying a set of substitutions defined by Theta to the sentence alpha
A substitution list Theta = {v1/t1, v2/t2, ..., vn/tn} means to replace all occurrences of variable symbol vi by term ti. Substitutions are made in left-to-right order in the list. Example: subst({x/IceCream, y/Ziggy}, eats(y,x)) = eats(Ziggy, IceCream)
Subscribe to:
Posts (Atom)
