Learning Rules and Relations from Web Text
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
summer project pal
Active In SP

Posts: 308
Joined: Jan 2011
29-01-2011, 06:57 PM

Learning Rules and Relations from Web Text
A Seminar Report
Jayarajan J N
Department of Computer Science & Engineering
College of Engineering Trivandrum
Kerala - 695016

As a step towards semantic based searching over the web, we must be able to understand the
relationships among di erent entities that are seen in typical web page content. We must be
able to group di erent entities as groups or classes. Once the entities or objects are classi ed
we can then try to nd the relationships among them. Once we know the relationships, we
can derive inference rules from those relations. These inference rules can be used to process
semantic based queries in future.
This seminar and presentation will concentrate on the part where the inference rules are derived, based on
the paper titled \Learning First Order Horn Clauses from Web Text". This paper investigates
the problem of learning inference rules from Web text in an unsupervised, domain-independent
manner. SHERLOCK - the machine learning system, described here is a rst-order learner that
acquires over 30,000 Horn clauses from Web text. SHERLOCK embodies several innovations,
including a novel rule scoring function based on Statistical Relevance (Salmon et al., 1971)
which is e ective on ambiguous, noisy and incomplete Web extractions. Their experiments
show that inference over the learned rules discovers three times as many facts (at precision 0.8)
as the TEXTRUNNER system which merely extracts facts explicitly stated in Web text.

.pdf   Learning Rules and Relations from.pdf (Size: 337.22 KB / Downloads: 36)

1 Introduction
Todays Web search engines locate pages that match keyword queries. Even sophisticated Web-
based Q/A systems merely locate pages that contain an explicit answer to a question. These
systems are helpless if the answer has to be inferred from multiple sentences, possibly on
di erent pages. To solve this problem, Schoenmackers et al.(2008) introduced the HOLMES
system, which infers answers from tuples extracted from text.
HOLMES's distinction is that it is domain independent and that its inference time is linear in
the size of its input corpus, which enables it to scale to the Web. However, HOLMES's Achilles
heel is that it requires hand-coded, rst-order, Horn clauses as input. Thus, while HOLMES's
inference run time is highly scalable, it requires substantial labor and expertise to hand-craft
the appropriate set of Horn clauses for each new domain.
Is it possible to learn e ective rst-order Horn clauses automatically from Web text in a
domain-independent and scalable manner? The paper refers to the set of ground facts derived
from Web text as open-domain theories. Learning Horn clauses has been studied extensively in
the Inductive Logic Programming (ILP) literature (Quinlan, 1990; Muggleton, 1995). However,
learning Horn clauses from open domain theories is particularly challenging for several reasons.
First, the theories denote instances of an unbounded and unknown set of relations. Second,
the ground facts in the theories are noisy, and incomplete. Negative examples are mostly
absent, and certainly the system cannot make the closed-world assumption typically made by
ILP systems. Finally, the names used to denote both entities and relations are rife with both
synonyms and polysymes making their referents ambiguous and resulting in a particularly noisy
and ambiguous set of ground facts.
This paper presents a new ILP method, which is optimized to operate on open-domain
theories derived from massive and diverse corpora such as theWeb, and experimentally con rms
both its e ectiveness and superiority over traditional ILP algorithms in this context. Figure 1
shows some example rules that were learned by SHERLOCK.
Figure 1: Example rules learned by SHERLOCK fromWeb extractions. Note that the italicized
rules are unsound.
The work on SHERLOCK makes the following contributions:
1. The paper describe the design and implementation of SHERLOCK system, which utilizes
a novel, unsupervised ILP method to learn rst-order Horn clauses from open-domain
Web text.
2. It derives an innovative scoring function that is particularly well-suited to unsupervised
learning from noisy text. For Web text, the scoring function yields more accurate rules
than several functions from the ILP literature.
3. It demonstrate the utility of SHERLOCK's automatically learned inference rules. Infer-
ence using SHERLOCK's learned rules identi es three times as many high quality facts
(e.g., precision  0:8) as were originally extracted from the Web text corpus.
The remainder of the paper is organized as follows. It start by describing previous work.
Section 3 introduces SHERLOCK rule learning system, with Section 3.4 describing how it
estimates rule quality. After that the conclusion comes.
2 Previous Work
SHERLOCK is one of the rst systems to learn rst-order Horn clauses from open-domain Web
extractions. The learning method in SHERLOCK belongs to the Inductive logic programming
(ILP) sub eld of machine learning (Lavrac and Dzeroski, 2001).
Classical ILP systems (e.g., FOIL (Quinlan, 1990) and Progol (Muggleton, 1995)) make strong
assumptions that are inappropriate for open domains.
Progol is an implementation of Inductive Logic Programming used in computer science that
combines \Inverse Entailment" with \general-to-speci c search" through a re nement graph.
\Inverse Entailment" is used with mode declarations to derive the most-speci c clause within
the mode language which entails a given example. This clause is used to guide a re nement-
graph search.
First, ILP systems assume high-quality, hand-labeled training examples for each relation
of interest. Second, ILP systems assume that constants uniquely denote individuals; however,
in Web text strings such as \dad" or \John Smith" are highly ambiguous. Third, ILP system
typically assume complete, largely noise-free data whereas tuples extracted from Web text are
both noisy and radically incomplete. Finally, ILP systems typically utilize negative examples,
which are not available when learning from open-domain facts. One system that does not require
negative examples is LIME (Mc- Creath and Sharma, 1997) Most prior ILP and Markov logic
structure learning systems (e.g., (Kok and Domingos, 2005)) are not designed to handle the
noise and incompleteness of open-domain, extracted facts.
2.2 NELL
The research goal of NELL(Never-Ending Language Learner)(Carlson et al., 2010) is to build a
never-ending machine learning system that acquires the ability to extract structured information
from unstructured web pages. If successful, this will result in a knowledge base (i.e., a relational
database) of structured information that mirrors the content of the Web. NELL performs
coupled semi-supervised learning to extract a large knowledge base of instances, relations, and
inference rules, bootstrapping from a few seed examples of each class and relation of interest and
a few constraints among them. In contrast, SHERLOCK focuses mainly on learning inference
rules, but does so without any manually speci ed seeds or constraints.
Craven et al.(1998) also used ILP to help information extraction on the Web, but required
training examples and focused on a single domain.
Two other notable systems that learn inference rules from text are DIRT (Lin and Pantel,
2001) and RESOLVER (Yates and Etzioni, 2007). However, both DIRT and RESOLVER learn
only a limited set of rules capturing synonyms, paraphrases, and simple entailments, not more
expressive multi-part Horn clauses. For example, these systems may learn the rule X acquired
Y ) X bought Y , which captures di erent ways of describing a purchase. Applications of
these rules often depend on context (e.g., if a person acquires a skill, that does not mean they
bought the skill). To add the necessary context, ISP (Pantel et al., 2007) learned selectional
preferences (Resnik, 1997) for DIRTs rules. The selectional preferences act as type restrictions
Figure 2: The rules learned by NELL which are automatically posted over Twitter
on the arguments, and attempt to lter out incorrect inferences. While these approaches are
useful, they are strictly more limited than the rules learned by SHERLOCK.
The Recognizing Textual Entailment (RTE) task (Dagan et al., 2005) is to determine whether
one sentence entails another. Approaches to RTE include those of Tatu and Moldovan (2007),
which generates inference rules from WordNet lexical chains and a set of axiom templates,
and Pennacchiotti and Zanzotto (2007), which learns inference rules based on similarity across
entailment pairs. In contrast with this work, RTE systems reason over full sentences, but
bene t by being given the sentences and training data. SHERLOCK operates over simpler
Web extractions, but is not given guidance about which facts may interact.
3 System Description
SHERLOCK takes a large set of open domain facts as input, and returns a set of weighted
Horn-clause inference rules. Other systems (e.g., HOLMES) use the rules to answer questions,
infer additional facts, etc.
SHERLOCKs basic architecture is depicted in Figure 2. To learn inference rules, SHER-
LOCK performs the following steps:
1. Identify classes and instances
2. Discover relations between classes
3. Learn inference rules and evaluate the con dence.
Figure 3: Architecture of SHERLOCK. SHERLOCK learns inference rules oine and provides
them to the HOLMES inference engine, which uses the rules to answer queries.
SHERLOCK reads extracted facts from TEXTRUNNER of the form (R; a; b) and utilizes
HOLMES as it's inference engine.
3.1 Identifying Classes and Instances
SHERLOCK rst searches for a set of well-de ned classes and class instances. Instances of the
same class tend to behave similarly, so identifying a good set of instances will make it easier to
discover the general properties of the entire class.
Hearst is used to identify interesting classes. It includes a set of textual patterns which
indicate hyponymy (e.g., `Class such as Instance'). The pairs extracted using these patterns
is cleaned using dropping modi ers.
SHERLOCK focus on the less ambiguous classes by eliminating any class not appearing as
a descendant of physical entity, social group, physical condition, or event in WordNet. Beyond
this ltering It makes no use of a type hierarchy and treat classes independently.
3.2 Discovering Relations between Classes
For every pair of classes (C1;C2), It nd a set of typed, candidate relations from the 100 most
frequent relations in the corpus where the rst argument is an instance of C1 and the second
argument is an instance of C2. For extraction terms with multiple senses (e.g., New York), It
splits their weight based on how frequently they appear with each class in the Hearst patterns.
Relations that are rare and meaningless and whose point-wise mutual information falls below
a threshold are discarded.
PMI(R(C1;C2)) = p(R;C1;C2)
where p(R; ; ) is the probability a random extraction has relation R; p(;C1; ) is the prob-
ability a random extraction has an instance of C1 as its rst argument, p(; ;C2) is similar for
the second argument, and p(R;C1;C2) is the probability that a random extraction has relation
R and instances of C1 and C2 as its rst and second arguments, respectively. A low PMI
indicates the relation occurred by random chance, which is typically due to ambiguous terms
or extraction errors.
3.3 Learning Inference Rules
SHERLOCK attempts to learn inference rules for each typed relation in turn. SHERLOCK
receives a target relation, R, a set of observed examples of the relation, E+, a maximum
clause length k, a minimum support, s, and an acceptance threshold, t, as input. SHERLOCK
generates all rst-order, de nite clauses up to length k, where R appears as the head of the
clause. It retains each clause that:
1. Contains no unbound variables
2. Infers at least s examples from E+
3. Scores at least t according to the score function
3.4 Evaluating Rules
Statistical relevance tries to infer the simplest set of factors which explain an observation. It can
be viewed as searching for the simplest propositional Horn-clause which increases the likelihood
of a goal proposition g. The two key ideas in determining statistical relevance are discovering
factors which substantially increase the likelihood of g (even if the probabilities are small in an
absolute sense), and dismissing irrelevant factors.
Statistical relevance appears useful in the opendomain context, since all the necessary prob-
abilities can be estimated from only positive examples. Furthermore, approximating relative
probabilities in the presence of missing data is much more reliable than determining absolute
For the Horn-clause Head(v1; :::; vn) :- Body(v1; :::; vm) (where Body(v1; :::; vm) is a conjunc-
tion of function-free, non-negated, rst-order relations, and vi 2 V is the set of typed variables
used in the rule), It says the body helps explain the head if:
1. Observing an instance of the body substantially increases the probability of observing the
2. The body contains no irrelevant (conditionally independent) terms.
De nition 1 A rst-order Horn-clause Head(::Smile :- Body(::Smile is statistically relevant if
p(Head(::SmilejBody(::Smile)  p(Head(::Smile) and if there is no clause body B0(::Smile  Body(::Smile such
that p(Head(::SmilejBody(::Smile)  p(Head(::SmilejB0(::Smile)
4 Functional Features of SHERLOCK
There are many distingushable improvements brought up in SHERLOCK compared to similar
systems. SHERLOCK di ers in the way it infers the facts, weight calculation, and the way it
handles Open domain nature and the absence of the negetive examples.
4.1 Inference
As input HOLMES requires a target atom H(::Smile, an evidence set E and weighted rule set R
as input. It performs a form of knowledge based model construction (Wellman et al., 1992),
rst nding facts using logical inference, then estimating the con dence of each using a Markov
Logic Network (Richardson and Domingos, 2006).
Since the rules and inferences are based on a set of noisy and incomplete extractions, the algo-
rithms used for both weight learning and inference should capture the following characteristics
of the concerned problem:
1. Any arbitrary unknown fact is highly unlikely to be true.
2. The more frequently a fact is extracted from the Web, the more likely it is to be true.
However, facts in E should have a con dence bounded by a threshold pmax < 1. E
contains systematic extraction errors, so they want uncertainty even in the most frequently
extracted facts.
3. An inference that combines uncertain facts should be less likely than each fact it uses.
4.2 Weight Learning
The weight is a count of true groundings for each rule. Since the web extractions are noisy It
will be an over estimate. Therefore It computes the number of true groundings for a rule i as
ni(E) =
1. ni(E) is the number of true groundings for the rule i, where E is the evidence.
2. p(B(::Smile) is an approximated value which ranges from 0 to 0.75.
3. Bodyijk is the body of the kth grounding rule of the jth head of the ith rule.
Longer rules have higher weight as they are more likely to be inferred wrongly. Otherwise,
each rule will receive a high weight as it has no negative examples.
4.3 Probabilistic Inference
After learning the weights, It adds the following two rules to the rule set:
1. H(::Smile with negative weight wprior
2. H(::Smile :- ExtractedF rom(H(::Smile; sentencei) with weight 1
HOLMES attempts to infer the truth value of each ground atom H(::Smile in turn by treating all
other extractions E in the corpus as evidence. Inference also requires computing ni(E) which
is done according to Equation 1 as in weight learning.
5 Conclusion
Here we have discussed about the di erent ILPs for knowledge building and about the project and implimentation
\Open Information Extraction" which includes RESOLVER, TEXTRUNNER, HOLMES and
SHERLOCK. We have seen that SHERLOCK works in the open domain and learns rst-order
rules without supervision based on the papers published in connection with the above said
project and implimentation.
SHERLOCK uses an optimistic approach towards the learned rules and brings the fact, that
the learned rule could be wrong, into account and its modi ed weight learning and probabilistic
inference together makes it possible to run in unsupervised mode.
This system may help us to build accurate knowledge bases which can be used to build high
performance AI based systems and expert systems.
[1] Daniel S. Weld Jesse Davis Stefan Schoenmackers, Oren Etzioni. \Learning rst-order horn
clauses fromweb text". In EMNLP2010 International Conference, 2010.
[2] Oren Etzioni Thomas Lin, Mausam. \Identifying functional relations in web text". In
EMNLP2010 International Conference, 2010.
[3] O. Etzioni A. Yates. \Unsupervised methods for determining object and relation synonyms
on the web". International Journal on Arti cial Intelligence Research, 2009.

Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  web spoofing full report computer science technology 13 9,013 20-05-2016, 11:59 AM
Last Post: Dhanabhagya
  web image re-ranking using query-specific semantic signatures ppt jaseelati 0 262 02-03-2015, 01:23 PM
Last Post: jaseelati
  web operating system seminar jaseelati 0 322 17-02-2015, 02:20 PM
Last Post: jaseelati
  web enabled automated manufacturing system jaseelati 0 226 13-01-2015, 02:34 PM
Last Post: jaseelati
  web based claim processing system pdf jaseelati 0 379 10-01-2015, 02:34 PM
Last Post: jaseelati
  A Character Segmentation Algorithm for Printed Kannada Text Document uploader 1 1,508 10-01-2015, 12:52 PM
Last Post: zcfqmbrtb
  embedded web technology ppt jaseelati 0 514 16-12-2014, 04:34 PM
Last Post: jaseelati
  Calling a Web Service from an ASP.NET Web Page ppt study tips 1 543 19-10-2014, 11:24 PM
Last Post: LICjKYTCf
Last Post: seminar project topic
  Web Browser full report seminar paper 3 2,358 26-09-2013, 09:42 AM
Last Post: seminar projects maker