Que1: what are normal form?
Ans1: sentences written in PL& FOPL are connected into some standards forms for further processing. These forms are called as Normal forms. Further processing of sentences is done with the help of inference methods like unification or resolution which take these sentences as input but in normal forms.
Two type of normal form in PL& FOPL are :
Conjunctive normal form (CNF): given wff’s F1,F2,……….Fn, each possibly containing the disjunction of literals only, we say F1&F2….&Fn is in CNF
Disjunctive normal form(DNF): given wff F!,F2……….Fn each possibly containing the conjunction of literals only. We say F1 V F2 V………V Fn. Is in DNF.
Que2: wht is the system predicate CUT? Discus the operational behaviour and imp use of CUT.
Ans2: the system predicate CUT, also called as CUT operator allows you to tell prolog which previous choices it need not consider again when it back tracks through the choice of satisfied goals. CUT operator is already defined in prolog and is represented with the help of the symbol ‘!’ in prolog program. By using CUT, ur prog will operate faster coz it would nt waste time attempting to satisfy gaols that u can tell before hand will never contribute to a solution. Your program will occupy less of comp. memory space by using CUT because more economical use of memory can be made if backtracking points don’t have to record for later examination.
Operationl behaviour and importance use of CUT :
confirming choice of a rule: first use of CUT isin places where we want to tell prolog system that it has found a right rule for a particular goal. It means CUT says if you get this for you have picked the correct rule for this goal. This rule of CUT can be explained with help of following example:
sum(N,S) is used to store sum of first N natural numbers in S. it can be defined as:
sum(1,1):-! %rule 1
sum(N,S) :-N>1, N1 is N-1, sum (N1,S1),, s is S1+N %rule 2
here rule 1 is used for boundary condition. Here, we have used CUT! So that if value of N is 1, prolog system checks first rule & display answer 1 and if failure, second rule is checked for N=1 and it will indefinitely go for recursive calls without any boundary condition to stop recursive calls. This ! in the definition is to say that in case of N=1, we just have to check rule 1
the “CUT-fail” combination: the second use of CUT is the place where we want to tell prolog system to fail a particular goal immediately without trying for alternative solutions. Here, CUT is used conjunction with the “fail” predicate to say “if you get to here, you should stop trying to satisfy the goal.” “fail” predicate is to built-in predicate having no argument , fail is defined in such a way that as a goal it always fails and causes backtracking to take place, following examples shows the use of CUT.
Taxpayer (X) :- foreigner (X), !,fail.
Taxpayer (X) :- female(X) , income(X,I),
I<85000, !, fail.
Taxpayer (X) :- male(X),income (X, I),
I<150000, !, fail.
Here if in rule 1 , foreigner (X) predicate is true, taxpayer(X) predicate will fail and ! is used to tell that we do not need to check any other rule if this rule does not satisfy goal taxpayer.
terminate general & test sequence: this use of CUT is in the places where we want to terminate the generation of alternative solutions through backtracking. Here, CUT means if you get to here, you have found only solution to the problem and there is no point in ever looking for alternatives. In prolog program, there is a sequence of goals that can succeed in many ways and which generates many possible solutions on backtracking. After this there are goals fail, backtracking will lead to another solution being proposed. This will be tested for appropriates and so on. This process will be found (failure). We can call the goal that are yielding all the alternative the “generator” and those that check whether a solution is acceptable the”tester”. For example
program to implement integer division using addition and multiplication
divide(N1,N2, result) :-
is integer (result),
product 1 is result*N2
product 2 I (result+1) * N2
product 1 = <> N1, !
integer is used as generator to generate result of dividing N1 by N2. rest of goals are tester! is placed at the nd to say that if we ever successfully generate a result that passes the test for being result of division. We need never try any more.
Que 3: short note on normal forms
Ans 3: sentences written in first order predicate logic or propositional logic are converted into some standard form for their further processing. These standard form are called as normal forms. Sentences in FOL and propositional logic are just giving us some information or knowledge about a particular thing. In order to infer new knowledge from these sentences, we need to process these sentences by using inference methods. Almost all the inference methods take these sentences as input but in normal forms.
Following are types of normal forms used in FOL and prepositional logic:
Conjunctive normal form (CNF)
Gives wff’s F1,F2,F3……Fn each possibly consisting of disjunction of literals only, we say F1, & F2&………….Fn is in conjunctive normal form. In these words, we can say each Fi, where i= 1,2,3………n consists only of the disjunction of literals but Fi are connected together with conjunctions.
Disjunctive Normal Form (DNF)
Given wff’s F1,F2,…………Fn, each possibly consisting of the conjunction of literals only, we say F1V F2 V F3…………. V Fn is in disjunction form. In other words if each Fi, i= 1,2,3…………n consists only of the conjunction of literals, we say F1 V F2………. , Fn is in disjunctive normal form.
For example the sentences
(P(x) & Q(y) & R) V P(x) V (M (x,y) & R) is in disjunctive normal form.
Que 4: define the term recursion
Ans 4: recursion is the process a procedure goes through when one of the steps of the procedure involves rerunning the same procedure. A procedure that goes through recursion is said to be recursive.
Wednesday, November 19, 2008
Thursday, November 13, 2008
EXPECTED QUESTIONS
Important questions from MST & Final Examination point of Vew
1.Diffefentiate between Logic & logic Programming ?
2.what is the need for quantifiers?
3.What do you mean by first order logic?
4What are Horn Clauses?
5Discuss the advantages of Prolog & differentiate between Syntax & Semantics?
6.What is Structural Induction ?
7.How do we represent Structured data in prolog?
8.Explain the concept of SLD trees?
9.What is Resolution? What role does it play in propositional logic?
10.Explain the concept of recursion in prolog?
11.Discuss the interpretation of nondeclarative features of prolog ?
12.What are normal forms. Explain in detail?
13.Discuss the logical limitation of prolog?
14. Write a program in prolog to compute Fibonacci term using recursion in prolog.
15.What is system predicate CUT?Discuss the operational behavior & important uses of CUT?
16.Explain Well formed formula in detail ?
17Discuss the concept of fail predicate in prolog with help of a example?
18Explain the non declarative features of prolog
1.Diffefentiate between Logic & logic Programming ?
2.what is the need for quantifiers?
3.What do you mean by first order logic?
4What are Horn Clauses?
5Discuss the advantages of Prolog & differentiate between Syntax & Semantics?
6.What is Structural Induction ?
7.How do we represent Structured data in prolog?
8.Explain the concept of SLD trees?
9.What is Resolution? What role does it play in propositional logic?
10.Explain the concept of recursion in prolog?
11.Discuss the interpretation of nondeclarative features of prolog ?
12.What are normal forms. Explain in detail?
13.Discuss the logical limitation of prolog?
14. Write a program in prolog to compute Fibonacci term using recursion in prolog.
15.What is system predicate CUT?Discuss the operational behavior & important uses of CUT?
16.Explain Well formed formula in detail ?
17Discuss the concept of fail predicate in prolog with help of a example?
18Explain the non declarative features of prolog
Important questions from MST & Final Examination point of Vew
1.Diffefentiate between Logic & logic Programming ?
2.what is the need for quantifiers?
3.What do you mean by first order logic?
4What are Horn Clauses?
5Discuss the advantages of Prolog & differentiate between Syntax & Semantics?
6.What is Structural Induction ?
7.How do we represent Structured data in prolog?
8.Explain the concept of SLD trees?
9.What is Resolution? What role does it play in propositional logic?
10.Explain the concept of recursion in prolog?
11.Discuss the interpretation of nondeclarative features of prolog ?
12.What are normal forms. Explain in detail?
13.Discuss the logical limitation of prolog?
14. Write a program in prolog to compute Fibonacci term using recursion in prolog.
15.What is system predicate CUT?Discuss the operational behavior & important uses of CUT?
16.Explain Well formed formula in detail ?
17Discuss the concept of fail predicate in prolog with help of a example?
18Explain the non declarative features of prolog
1.Diffefentiate between Logic & logic Programming ?
2.what is the need for quantifiers?
3.What do you mean by first order logic?
4What are Horn Clauses?
5Discuss the advantages of Prolog & differentiate between Syntax & Semantics?
6.What is Structural Induction ?
7.How do we represent Structured data in prolog?
8.Explain the concept of SLD trees?
9.What is Resolution? What role does it play in propositional logic?
10.Explain the concept of recursion in prolog?
11.Discuss the interpretation of nondeclarative features of prolog ?
12.What are normal forms. Explain in detail?
13.Discuss the logical limitation of prolog?
14. Write a program in prolog to compute Fibonacci term using recursion in prolog.
15.What is system predicate CUT?Discuss the operational behavior & important uses of CUT?
16.Explain Well formed formula in detail ?
17Discuss the concept of fail predicate in prolog with help of a example?
18Explain the non declarative features of prolog
Monday, October 20, 2008
SOME IMPORTANT QUESTIONS /OLD QUESTION PAPERS
Some Important questions
1.WHAT IS LOGIC PROGRAMMING ?2.DEFINE FACT AND RULES?
3.Define the term expert system?
4.differentiate between Var & Nonvar?
5.Diferentiate between atom and atomic ?
6.explain the term built in predicate trace?
7.Differenciate between between Assert & Assertz predicate?
8.What is Structural induction?
9. What is the purpose of arg predicate?
10.Define translation from natural language to sumbolic language ?
11.Define heuristics?Give one example?
12.what is WFFS ?
13Differentiate between Syntax and symantics?
14 Explain linear resolution?
15.what is skolemization ?
16.what is inferencing?
17.What are representations & mappings?
18./Differnciate between forward reasoning and bacward reasoning?
19. what is mapping?
20. name the various AI languages?
21.Explain CNF & DNF?
22.write short notes on
a)bottom up parsing
b)modus ponens
c)unification
23 explain the concept of backtracking?
24.What is Conflict Resolution?
25.Explain Breadth first search?
26.define predictive retract?
27.what is resolution principle ?
28Explain the chain rule ?
29. what are the various quantifiers ?explain
30 define functor?
31 Differentiate between procedural knowledge and declatrative language?
32.explain the predicates which are used in making the things equal?
33what is SPY used for?
34what is difference between get & get0 ?
35.Explain in detail the concepts of Horn clauses ?
36
Wednesday, October 15, 2008
ABOUT HORN CLAUSE
Definition: A Horn clause is a clause with at most one positive literal.
Any Horn clause therefore belongs to one of four categories:
A rule: 1 positive literal, at least 1 negative literal. A rule has the form "~P1 V ~P2 V ... V ~Pk V Q". This is logically equivalent to "[P1^P2^ ... ^Pk] => Q"; thus, an if-then implication with any number of conditions but one conclusion. Examples: "~man(X) V mortal(X)" (All men are mortal); "~parent(X,Y) V ~ancestor(Y,Z) V ancestor(X,Z)" (If X is a parent of Y and Y is an ancestor of Z then X is an ancestor of Z.)
A fact or unit: 1 positive literal, 0 negative literals. Examples: "man(socrates)", "parent(elizabeth,charles)", "ancestor(X,X)" (Everyone is an ancestor of themselves (in the trivial sense).)
A negated goal : 0 positive literals, at least 1 negative literal. In virtually all implementations of Horn clause logic, the negated goal is the negation of the statement to be proved; the knowledge base consists entirely of facts and goals. The statement to be proven, therefore, called the goal, is therefore a single unit or the conjuction of units; an existentially quantified variable in the goal turns into a free variable in the negated goal. E.g. If the goal to be proven is "exists (X) male(X) ^ ancestor(elizabeth,X)" (show that there exists a male descendent of Elizabeth) the negated goal will be "~male(X) V ~ancestor(elizabeth,X)".
The null clause: 0 positive and 0 negative literals. Appears only as the end of a resolution proof
OR
A Horn clause is a clause with at most one expression on the left of the arrow. The expression on the left of the arrow (if there is one) is called the head of the clause. The expression(s) to the right of the arrow (if there are any) make up the body of the clause. The four possible types of Horn clause are conventionally named as follows.
1.Facts
Clauses of the form A¬ . (Facts have a head but no body.)
2.Rules
Clauses of the form A¬ B1,...,Bn. (Rules have both a head and a body.)
3Goals
Clauses of the form ¬ B1,...,Bn . (Goals have a body, but no head.)
4.Empty Clause
The clause \Box, with no head and no body.
Any Horn clause therefore belongs to one of four categories:
A rule: 1 positive literal, at least 1 negative literal. A rule has the form "~P1 V ~P2 V ... V ~Pk V Q". This is logically equivalent to "[P1^P2^ ... ^Pk] => Q"; thus, an if-then implication with any number of conditions but one conclusion. Examples: "~man(X) V mortal(X)" (All men are mortal); "~parent(X,Y) V ~ancestor(Y,Z) V ancestor(X,Z)" (If X is a parent of Y and Y is an ancestor of Z then X is an ancestor of Z.)
A fact or unit: 1 positive literal, 0 negative literals. Examples: "man(socrates)", "parent(elizabeth,charles)", "ancestor(X,X)" (Everyone is an ancestor of themselves (in the trivial sense).)
A negated goal : 0 positive literals, at least 1 negative literal. In virtually all implementations of Horn clause logic, the negated goal is the negation of the statement to be proved; the knowledge base consists entirely of facts and goals. The statement to be proven, therefore, called the goal, is therefore a single unit or the conjuction of units; an existentially quantified variable in the goal turns into a free variable in the negated goal. E.g. If the goal to be proven is "exists (X) male(X) ^ ancestor(elizabeth,X)" (show that there exists a male descendent of Elizabeth) the negated goal will be "~male(X) V ~ancestor(elizabeth,X)".
The null clause: 0 positive and 0 negative literals. Appears only as the end of a resolution proof
OR
A Horn clause is a clause with at most one expression on the left of the arrow. The expression on the left of the arrow (if there is one) is called the head of the clause. The expression(s) to the right of the arrow (if there are any) make up the body of the clause. The four possible types of Horn clause are conventionally named as follows.
1.Facts
Clauses of the form A¬ . (Facts have a head but no body.)
2.Rules
Clauses of the form A¬ B1,...,Bn. (Rules have both a head and a body.)
3Goals
Clauses of the form ¬ B1,...,Bn . (Goals have a body, but no head.)
4.Empty Clause
The clause \Box, with no head and no body.
Monday, October 6, 2008
converting FOL to Clause Form
Converting FOL Sentences to Clause Form
Every FOL sentence can be converted to a logically equivalent sentence that is in a "normal form" called clause form
Steps to convert a sentence to clause form:
1.Eliminate all <=> connectives by replacing each instance of the form (P <=> Q) by the equivalent expression ((P => Q) ^ (Q => P))
2Eliminate all => connectives by replacing each instance of the form (P => Q) by (~P v Q)
3Reduce the scope of each negation symbol to a single predicate by applying equivalences such as converting ~~P to P; ~(P v Q) to ~P ^ ~Q; ~(P ^ Q) to ~P v ~Q; ~(Ax)P to (Ex)~P, and ~(Ex)P to (Ax)~P
4.Standardize variables: rename all variables so that each quantifier has its own unique variable name. For example, convert (Ax)P(x) to (Ay)P(y) if there is another place where variable x is already used.
5Eliminate existential quantification by introducing Skolem functions. For example, convert (Ex)P(x) to P(c) where c is a brand new constant symbol that is not used in any other sentence. c is called a Skolem constant. More generally, if the existential quantifier is within the scope of a universal quantified variable, then introduce a Skolem function that depend on the universally quantified variable. For example, (Ax)(Ey)P(x,y) is converted to (Ax)P(x, f(x)). f is called a Skolem function, and must be a brand new function name that does not occur in any other sentence in the entire KB.
Example: (Ax)(Ey)loves(x,y) is converted to (Ax)loves(x,f(x)) where in this case f(x) specifies the person that x loves. (If we knew that everyone loved their mother, then f could stand for the mother-of function.
Remove universal quantification symbols by first moving them all to the left end and making the scope of each the entire sentence, and then just dropping the "prefix" part. For example, convert (Ax)P(x) to P(x).
Distribute "and" over "or" to get a conjunction of disjunctions called conjunctive normal form. Convert (P ^ Q) v R to (P v R) ^ (Q v R), and convert (P v Q) v R to (P v Q v R).
Split each conjunct into a separate clause, which is just a disjunction ("or") of negated and un-negated predicates, called literals.
Standardize variables apart again so that each clause contains variable names that do not occur in any other clause.
Example
Convert the sentence (Ax)(P(x) => ((Ay)(P(y) => P(f(x,y))) ^ ~(Ay)(Q(x,y) => P(y))))
Eliminate <=>Nothing to do here.
Eliminate =>(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ ~(Ay)(~Q(x,y) v P(y))))
Reduce scope of negation(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ (Ey)(Q(x,y) ^ ~P(y))))
Standardize variables(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ (Ez)(Q(x,z) ^ ~P(z))))
Eliminate existential quantification(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ (Q(x,g(x)) ^ ~P(g(x)))))
Drop universal quantification symbols(~P(x) v ((~P(y) v P(f(x,y))) ^ (Q(x,g(x)) ^ ~P(g(x)))))
Convert to conjunction of disjunctions(~P(x) v ~P(y) v P(f(x,y))) ^ (~P(x) v Q(x,g(x))) ^ (~P(x) v ~P(g(x)))
Create separate clauses
~P(x) v ~P(y) v P(f(x,y))
~P(x) v Q(x,g(x))
~P(x) v ~P(g(x))
Standardize variables
~P(x) v ~P(y) v P(f(x,y))
~P(z) v Q(z,g(z))
~P(w) v ~P(g(w))
Every FOL sentence can be converted to a logically equivalent sentence that is in a "normal form" called clause form
Steps to convert a sentence to clause form:
1.Eliminate all <=> connectives by replacing each instance of the form (P <=> Q) by the equivalent expression ((P => Q) ^ (Q => P))
2Eliminate all => connectives by replacing each instance of the form (P => Q) by (~P v Q)
3Reduce the scope of each negation symbol to a single predicate by applying equivalences such as converting ~~P to P; ~(P v Q) to ~P ^ ~Q; ~(P ^ Q) to ~P v ~Q; ~(Ax)P to (Ex)~P, and ~(Ex)P to (Ax)~P
4.Standardize variables: rename all variables so that each quantifier has its own unique variable name. For example, convert (Ax)P(x) to (Ay)P(y) if there is another place where variable x is already used.
5Eliminate existential quantification by introducing Skolem functions. For example, convert (Ex)P(x) to P(c) where c is a brand new constant symbol that is not used in any other sentence. c is called a Skolem constant. More generally, if the existential quantifier is within the scope of a universal quantified variable, then introduce a Skolem function that depend on the universally quantified variable. For example, (Ax)(Ey)P(x,y) is converted to (Ax)P(x, f(x)). f is called a Skolem function, and must be a brand new function name that does not occur in any other sentence in the entire KB.
Example: (Ax)(Ey)loves(x,y) is converted to (Ax)loves(x,f(x)) where in this case f(x) specifies the person that x loves. (If we knew that everyone loved their mother, then f could stand for the mother-of function.
Remove universal quantification symbols by first moving them all to the left end and making the scope of each the entire sentence, and then just dropping the "prefix" part. For example, convert (Ax)P(x) to P(x).
Distribute "and" over "or" to get a conjunction of disjunctions called conjunctive normal form. Convert (P ^ Q) v R to (P v R) ^ (Q v R), and convert (P v Q) v R to (P v Q v R).
Split each conjunct into a separate clause, which is just a disjunction ("or") of negated and un-negated predicates, called literals.
Standardize variables apart again so that each clause contains variable names that do not occur in any other clause.
Example
Convert the sentence (Ax)(P(x) => ((Ay)(P(y) => P(f(x,y))) ^ ~(Ay)(Q(x,y) => P(y))))
Eliminate <=>Nothing to do here.
Eliminate =>(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ ~(Ay)(~Q(x,y) v P(y))))
Reduce scope of negation(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ (Ey)(Q(x,y) ^ ~P(y))))
Standardize variables(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ (Ez)(Q(x,z) ^ ~P(z))))
Eliminate existential quantification(Ax)(~P(x) v ((Ay)(~P(y) v P(f(x,y))) ^ (Q(x,g(x)) ^ ~P(g(x)))))
Drop universal quantification symbols(~P(x) v ((~P(y) v P(f(x,y))) ^ (Q(x,g(x)) ^ ~P(g(x)))))
Convert to conjunction of disjunctions(~P(x) v ~P(y) v P(f(x,y))) ^ (~P(x) v Q(x,g(x))) ^ (~P(x) v ~P(g(x)))
Create separate clauses
~P(x) v ~P(y) v P(f(x,y))
~P(x) v Q(x,g(x))
~P(x) v ~P(g(x))
Standardize variables
~P(x) v ~P(y) v P(f(x,y))
~P(z) v Q(z,g(z))
~P(w) v ~P(g(w))
Sunday, September 28, 2008
FIGURE NEURAL NETWEORK
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
VISIT THIS WEB PORATL FOR ALL DETAILED INFORMATION ON NEURAL NETWORK AND THE FIGURES PRETAINING TO NEURAL NETWORK DESIGN
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)
