Brainmaker

Nanos gigantium humeris insidentes!
You are currently browsing the FOL category

Prolog for natural language processing

  • July 11, 2010 2:29 pm

Chapter 3: The Linguistic Background

3.6 Functional Grammar and unification

This section is a good introduction to the functional structures research, and the last paragraph serves as a brief survey on this field.

Brief Summary

  • July 10, 2010 1:05 pm

Paper to read
Toward the expressive power of natural language  in  Principles of Semantic Networks
Topic on expressive power
Automatic Labeling of Semantic Roles
A good paper on semantic labeling
一阶逻辑的不足
Mentioned of FOL being not able to express some mathematical problem
Semantic Structure — Jackendoff’s conceptual semantics
It’s a deep research and kinda complete.
Graph-based knowledge representation [electronic resource] : computational foundations of conceptual
Online, 2009, new idea
Knowledge Representation and Predicate Calculus
Let’s say it’s a simple survey on NLP
Natural Language, Knowledge Representation, and Logical Form
has a discussion on expressive power

Idea:
Simple English -> FOC base
English expressive power reduction -> FOL
Statistic NLP:一个子问题,由当前概率确定;如果联系上下文,则为在给定事件下,当前事件的概率
prolog reasons with every possible rule, but here, we attach probability to each rule, when reasoning, we apply with probability.Aquist, Hoepelman, and Rohrer 1980
Simple English -> Common Logic Controlled English
Statistics on Semantic role parser
Apply relation checking and statistics in semantic role parsing for disambugulity
conceptual semantics by jackendoff

Summary One:
The books are too old to give you a new idea, you should use books as foundation and read the magazine

Knowledge Representation and Predicate Calculus

  • July 8, 2010 10:17 pm

http://herselfsai.com/2007/02/knowledge-representation-and-predicate-calculus.html

One of the trickier parts of designing artificial intelligence is how to represent information to something that can not understand language. Knowledge representation is defined by its syntax and its facts (semantics) which together along with the rules for deducing new sentences make up the logic. Entailment is the relationship between current sentences and new sentences derived from the current sentences. A good knowledge representation language will combine the ease of spoken and written languages, like English, with the conciseness of a computer language, like C.

Propositional (boolean) Logic This consists of a syntax, the semantics and rules for deducing new sentences. Symbols are used to represent facts which may or may not be true. W may 72 represent the fact it is windy outside. The symbols are combined with boolean logic to generate new sentences. Facts can be true or false only. The program may know a statement is true or false or be uncertain as to its truth or falsity. The syntax consists of , v, => (if x then y), (equal), and (not). Backus-Naur Form (bnf) is the grammar used to put sentences together. The semantics are just the interpretation of a statement about a proposition. Truth tables are used to define the semantics of sentences or test validity of statements.

Truth table for AND

T and T = T

T and F = F

F and F = F

F and T = F

A model is a world in which a sentence is true under a particular interpreta tion. There can be several models at once that have the same interpretations. An inference rule is a rule that is derived from a pattern that is true all the time for specific cases.

First Order Logic (first-order predicate calculus)
This consists of objects, predicates on objects, connectives and quantifiers. Predicates are the relations between objects, or properties of the objects. Connectives and quantifiers allow for universal sentences. Relations between objects can be true or false as well as the objects themselves. The program may not know whether something is true or false or give it a probability of truth or falseness.

Procedural Representation
This method of knowledge representation encodes facts along with the sequence of operations for manipulation and processing of the facts. This is what expert systems are based on. Knowledge engineers question experts in a given field and code this information into a computer program. It works best when experts follow set procedures for problem solving, i.e. a doctor making a diagnoses.

The most popular of the Procedural Representations is the Declarative. In the Declarative Representation the user states facts, rules, and relationships. These represent pure knowledge. This is processed with hard coded procedures.

Relational Representation
Collections of knowledge are stored in table form. This is the method used for most commercial databases, Relational Databases. The information is manipulated with relational calculus using a language like SQL. This is a flexible way to store information but not good for storing complex relationships. Problems arise when more than one subject area is attempted. A new knowledge base from scratch has to be built for each area of expertise.

Hierarchical Representation
This is based on inherited knowledge and the relationships and shared attributes between objects. This good for abstracting or granulating knowledge. Java and C++ are based on this.

Semantic Net
A data graph structure is used and concrete and abstract knowledge is represented about a class of problems. Each one is designed to handle a specific problem. The nodes are the concepts features or processes. The edges are the relationships (is a, has a, begins, ends, duration, etc). The edges are bidirectional, backward edges are called ‘Hyper Types’ or ‘Back Links’. This allows backward and forward walking through the net. The reasoning part of the nets includes: expert systems; blackboard architecture; and a semantic net description of the problem. These are used for natural language parsing and databases. Predicate Logic and propositional Most of the logic done with AI is predicate logic. It used to represent objects, functions and relationships. Predicate logic allows representation of complex facts about things and the world. (If A then B). A ‘knowledge base’ is a set of facts about the world called ’sentences’. These are put in a form of ‘knowledge representation language’. The program will ‘ASK’ to get information from the knowledge base and ‘TELL’ to put information into the knowledge base. Using objects, relations between them, and their attributes almost all knowledge can be represented. It does not do well deriving new knowledge. The knowledge representation must take perceptions and turn them into sentences for the program to be able to use them, and it must take queries and put them into a form the program can understand.

Resolution and unification
Resolution: prove A true by proving A Not is false. Unification: take two predicate logic sentences and using substitutions make them the same. Unification is the single operation that can be done on data structures (expression trees) in Prolog. These are the techniques used to process predicate logic knowledge and the are the basis for Lisp and Prolog.

Frames
Each frame has a name and a set of attribute-value pairs called slots. The frame is a node in a semantic network. Hybrid frame systems are meant to over come serious limitations in current setups. They work much like an object oriented language. A frame contains an object, its attributes, relationships and its inherited attributes. This is much like Java classes. We have a main class and sub classes that have attributes, relationships, and methods for use.

A logic has a language, inference rules, and semantics. Two logical languages are propositional calculus and predicate calculus.

Propositional Calculus which is a descendant of boolean algebra is a language that can express constraints among objects, values of objects, and inferences about objects and values of objects.

The elements of propositonal calculus are:
Atoms: the smallest elements
Connectives: or, and, implies, not
Sentences: aka ‘well-formed formula’s, wffs

The legal wwfs
disjunction: or
conjunction: and
implication: implies
negation: not

Rules of inference are used to produce other wwfs
modus ponens: ( x AND ( x implies y) ) implies y
AND introduction: x, y implies ( x AND y )
AND commutativity: x AND y implies x
OR introduction: x, y implies ( x OR y )
NOT elimination: NOT ( NOT x ) implies x
resolution: combining rules of inference into one rule:
{ example: (x OR y) AND ( NOT y OR z ) = x OR z
Horn clauses: a clause having one TRUE literal, there are three types: a single atom (q); an implication or rule ( p AND q = r ); a set of negative literals ( p OR q => ) . These have linear time algorithms.

Definitions:
Semantics:
associations of elements of a language with the elements of the domain

Propositions:
a statement about an atom, example: The car is running. Car is the atom, ‘is running’ is the proposition.

interpretation:
is the association of the proposition with the atom

denotation:
in a given interpretation the proposition associated with the atom is the denotation

value:
TRUE, FALSE, given to an atom

knowledge base:
a collection of propositional calculus statements that are true in the domain

truth table:
a tablular format for representing states

satisfies:
a true statement under a given interpretation

model:
an interpretation that satisfies each statement in a set of statements.

validity:
a statement that is TRUE under all interpretations

equivalence:
statements are equivalent if their truth values are identical under all interpretations.

Examples:
DeMorgan’s Laws:
NOT (x OR y ) = ( NOT x ) AND ( NOT y )
NOT ( x AND y ) = ( Not x ) OR ( NOT y )

Contrapositive:
( x implies y ) = ( NOT x implies NOT y )
if ( x = y ) then ( x implies y ) = ( y implies x )

Propositional satisfiability, aka PSAT
a model formula that comprises the conjunction of all the statements in the set.

Predicate Calculus takes propositional calculus further by allowing statements about propositions as well as about objects. This is first order predicate calculus.
Contains:
object constants, term: strings of characters, xyz, linda, paris
relation constants: divided by, distance to/from, larger than
function constants: small, big, blue
functional expression: examples: distance(here, there); xyz;
worlds: can have infinite objects, functions on objects, relations over objects
interpretations: maps object constants into objects in the world
quantifiers: can be universal or for a selected object or group of objects

Predicate Calculus is used to express mathematical theories. It consists of sentences, inference rules and symbols. First-order predicate calculus symbols consist of variables about which a statement can be made, logic symbols (and, or, not, for all, there exists, implies) and punctuation ( ‘(‘, ‘)’ ).

If we have a set S in which all of the statements are true then S is a model. If S implies U then U is true for all models of S and NOT U is false for all models of S. If we make a set S’ which has all of the statements of S and the statement NOT U it is not a model. All statements in a model must be true. S’ is unsatisfiable since there is no way for the statements of S and the statement NOT U, both of which are in S’ to be true at the same time. This is used to prove formulas in theorem proving. To show S implies U is is sufficient to show S’= S, NOT U is unsatisfiable.

Resolution and unification

Resolution: prove A true by proving A Not is false.

Unification: take two predicate logic sentences and using substitutions make them the same. Unification is the single operation that can be done on data structures (expression trees) in Prolog. These are the techniques used to process predicate logic knowledge and the are the basis for Lisp and Prolog.

Resolution is one way to prove unsatisfiability.

More information:
First Order Predicate Calculus
Syntax of Predicate Calculus (pdf)
Knowledge Representation and Predicate Calculus (pdf)
Predicate Calculus (pdf)

一阶逻辑的不足

  • July 7, 2010 9:21 pm

http://zh.wikipedia.org/zh-tw/%E4%B8%80%E9%98%B6%E9%80%BB%E8%BE%91#.E8.BD.AC.E6.8D.A2.E8.87.AA.E7.84.B6.E8.AF.AD.E8.A8.80.E5.88.B0.E4.B8.80.E9.98.B6.E9.80.BB.E8.BE.91

转换自然语言到一阶逻辑

用自然语言表达的概念必须在一阶逻辑(FOL)可以为为其效力之前必须被转换到FOL,而在这种转换中可能有一些潜在的缺陷。在FOL中,意 味着「要么p要么q要么二者」,就是说它是「包容性」的。在英语中,单词「or」有时是包容性的(比如,「加牛奶或糖?」),有时是排斥性的(比如,「喝 咖啡或茶?」,通常意味着取其中一个或另一个但非二者)。类似的,英语单词「some」可以意味着「至少一个,可能全部」,有时意味着「不是全部,可能没 有」。英语单词「and」有时要按「or」转换(比如,「男人和女人可以申请」)。 [2]

[编辑一阶逻辑的限制

所有数学概念都有它的强项和弱点;下面列出一阶逻辑的一些问题。

[编辑难于表达if-then-else

太奇怪了,(如典型定义的)带有等式的FOL不包含或允许定义if-then-else谓词或函数if(c,a,b),这里的c是表达为公式的条 件,而ab是要么都是项要么都是公式,并且它的结果是a如果c为真,或者b如果它为假。问题在于FOL中,谓词和函数二者只接受(「非布尔类型」)项作 为参数,而条件的明确表达是(「布尔类型」)公式。这是不幸的,因为很多数学函数是依据if-then-else而方便的表达的,而if-then- else是描述大多数计算机程序的基础。

在数学上,有可能重定义匹配公式算子的新函数的完备集合,但是这是非常笨拙的。[3] 谓词if(c,a,b)如果重写为就 可以在FOL中表达,但是如果条件c是复杂的这就是笨拙的。很多人扩展FOL增加特殊情况谓词叫做「if(条件,a, b)」(这里ab是公式)和/或函数「ite(条件,a, b)」(这里的ab是项),它们都接受一个公式作为条件,并且等于a如果条件为真,或b如果条件为假。这些扩展使FOL易于用于某些问题,并使某类自动 定理证明更容易。[4] 其他人进一步扩展FOL使得函数和谓词可以在任何位置接受项和公式二者。

[编辑类型(种类)

除了在公式(「布尔类型」)和项(「非布尔类型」)之间的区别之外,FOL不包括类型(种类)到自身的概念中。 某些人争辩说缺乏类型是巨大优点 [5],而很多其他人发觉了定义和使用类型(种类)的优点,比如帮助拒绝某些错误或不想要的规定 [6]。 想要指示类型的那些人必须使用在FOL中可获得的符号来提供这种信息。这么做使得这种表达更加复杂,并也容易导致错误。

单一参数谓词可以用来在合适的地方实现类型的概念。例如:

谓词Man(x)可以被认为是一类「类型断言」(就是说,x必须是男人)。 谓词还可以同指示类型的「存在」量词一起使用,但这通常应当转而与逻辑合取算子一起来做,比如:

(「存在既是男人又是人类的事物」)

容易写成,但这将等价与 (「存在不是男人的事物或者存在是人类的事物」),这通常不是想要的。类似的,可以做一个类型是另一个类型的子类型的断言,比如:

(「对于所有x,如果x是男人,则x是哺乳动物)

[编辑难于刻画有限性或可数性

主条目:二阶逻辑

Löwenheim–Skolem定理得出在一阶逻辑中不可能刻画有限性或可数性。例如,在一阶逻辑中你不能断言实数的集合的上确界性质,它声称实数的所有有界的、非空集合都有上确界;这就需要二阶逻辑了。

[编辑图可及性不能表达

很多情况可以被建模为节点和有向连接(边)的。 例如,效验很多系统要求展示不能从「好」状态触及到「坏」状态,而状态的相互连接经常可以建模为图。但是,可以证明这种可及性不能用谓词逻辑完全表达。换 句话说,没有谓词逻辑公式f,带有uv作为它的唯一自由变数,而R作为它唯一的(2元)谓词符号,使得f在一个有向图中成立,如果在这个图中存在从关联 于u的节点到关联于v的节点的路径。[7

FOL

  • July 7, 2010 3:37 pm

Whereas propositional logic assumes the world contains facts,
first-order logic (like natural language) assumes the world contains

  • Objects: people, houses, numbers, colors, baseball games, wars, …
  • Relations: red, round, prime, brother of, bigger than, part of, comes between, …
  • Functions: father of, best friend, one more than, plus, …

Syntax of FOL

•Constants  KingJohn, 2, NUS,…
•Predicates  Brother, >,…
•Functions  Sqrt, LeftLegOf,…
•Variables  x, y, a, b,…
•Connectives  Ø, Þ, Ù, Ú, Û
•Equality  =
Quantifiers    “, $

Atomic sentence =  predicate (term1,…,termn)   or term1 = term2

Term              =  function (term1,…,termn)   or constant or variable

•E.g., Brother(KingJohn,RichardTheLionheart) > (Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))

生成规则

  • July 4, 2010 10:29 pm
  • 规则1:一个VB对应一个prediate;但是predicate数量可能多于VB数量
  • 规则2:predicate所带两个参数,在原句子中,一个位于谓词前(在parse tree的上层),一个位于谓词后面(下层)
  • 规则3:定义--VBZ(且为are is)带NP是定义标志之一
  • 规则4: VBP 直接带PP,如果PP下第一个是IN,那么 VBP IN 能合成一个predicate
  • 规则5:名词性从句、定语从句、或同位语、定语,本身都是一个fact,起到修饰先前主语用,和主要的fact的关系为and关系,用来限定; 同位语,定语的predicate就是那个介词
  • 规则6: 状语从句,都可用prolog的:-来表示,或者是lisp的implies

Rules for NL to FOL

  • July 4, 2010 8:56 pm
  • 规则1:一个VB对应一个prediate;但是predicate数量可能多于VB数量
  • 规则2:predicate所带两个参数,在原句子中,一个位于谓词前(在parse tree的上层),一个位于谓词后面(下层)
  • 规则3:定义--VBZ(且为are is)带NP是定义标志之一
  • 规则4: VBP 直接带PP,如果PP下第一个是IN,那么 VBP IN 能合成一个predicate
  • 规则5:名词性从句、定语从句、或同位语、定语,本身都是一个fact,起到修饰先前主语用,和主要的fact的关系为and关系,用来限定; 同位语,定语的predicate就是那个介词
  • 规则6: 状语从句,都可用prolog的:-来表示,或者是lisp的implies

自然语言向一阶逻辑转换

  • July 4, 2010 3:52 pm

简单句:一个fact

名词性从句、定语从句:reference link,指代作用

状语从句:一个rule

Common Logic Controlled English

  • July 4, 2010 1:51 am

http://www.jfsowa.com/clce/specs.htm

Common Logic Controlled English

by sowa

想法

  • July 4, 2010 1:23 am
  • 先将基本句型转换出对应的一阶逻辑
    • http://www.24en.com/grammar/
  • 然后从parsing tree上找出模型
    Page 1 of 212