Content deleted Content added
Sunthestar (talk | contribs) |
CE |
||
| (29 intermediate revisions by 20 users not shown) | |||
Line 1:
{{Short description|Machine learning algorithm}}
'''Coupled Pattern Learner''' (CPL) is a [[machine learning]] algorithm which couples the [[semi-supervised learning]] of categories and relations to forestall the problem of semantic drift associated with boot-strap learning methods.
== Coupled Pattern Learner == ▼
[[Semi-supervised learning]] approaches using a small number of labeled examples with many unlabeled examples are usually unreliable as they produce an internally consistent, but incorrect set of extractions. CPL solves this problem by simultaneously learning classifiers for many different categories and relations in the presence of an [[ontology]] defining constraints that couple the training of these classifiers. It was introduced by Andrew Carlson, Justin Betteridge, Estevam R. Hruschka Jr. and Tom M. Mitchell in 2009. <ref name=cbl2009>{{cite journal|last=Carlson|first=Andrew|coauthors=Justin Betteridge; Estevam R. Hruschka Jr.; Tom M. Mitchell|date=2009|title=Coupling semi-supervised learning of categories and relations|journal=Proceedings of the NAACL HLT 2009 Workshop on Semi-Supervised Learning for Natural Language Processing |publisher=Association for Computational Linguistics|___location=Colorado, USA|pages=1–9|url=http://dl.acm.org/citation.cfm?id=1621829.1621830}} </ref> <ref name=cpl2010>{{cite journal|last=Carlson|first=Andrew|coauthors=Justin Betteridge;Richard C. Wang; Estevam R. Hruschka Jr.; Tom M. Mitchell|date=2010|title=Coupled semi-supervised learning for information extraction|journal=Proceedings of the third ACM international conference on Web search and data mining |publisher=ACM|___location=NY, USA|pages=101–110|url=http://dl.acm.org/citation.cfm?doid=1718487.1718501}}</ref>▼
== CPL Overview==▼
▲[[Semi-supervised learning]] approaches using a small number of labeled examples with many unlabeled examples are usually unreliable as they produce an internally consistent, but incorrect set of extractions. CPL solves this problem by simultaneously learning
CPL is an approach to [[semi-supervised learning]] that yields more accurate results by coupling the training of many information extractors. Basic idea behind CPL is that semi-supervised training of a single type of extractor such as ‘coach’ is much more difficult than simultaneously training many extractors that cover a variety of inter-related entity and relation types. Using prior knowledge about the relationships between these different entities and relations CPL makes unlabeled data as a useful constraint during training. For e.g., ‘coach(x)’ implies ‘person(x)’ and ‘not sport(x)’.▼
== CPL
▲CPL is an approach to [[semi-supervised learning]] that yields more accurate results by coupling the training of many information extractors. Basic idea behind CPL is that semi-supervised training of a single type of extractor such as ‘coach’ is much more
=== Coupling of
CPL primarily relies on the notion of coupling the [[learning]] of multiple functions so as to constrain the semi-supervised learning problem. CPL constrains the learned function in two ways.
# Sharing among same-arity predicates according to logical relations
Line 14 ⟶ 15:
=== Sharing among same-arity predicates ===
Each predicate P in the ontology has a list of other same-arity predicates with which P is mutually exclusive. If A is [[mutually exclusive]] with predicate B, A’s positive instances and patterns become negative instances and negative patterns for B. For example, if ‘city’, having an instance ‘Boston’ and a pattern ‘mayor of arg1’, is mutually exclusive with ‘scientist’, then ‘Boston’ and ‘mayor of arg1’ will become a negative instance and a negative pattern respectively for ‘scientist.’ Further, Some categories are declared to be a subset of another category. For e.g., ‘athlete’ is a subset of ‘person’.
=== Relation argument type-checking ===
This is a type checking information used to couple the learning of relations and categories. For example, the arguments of the ‘ceoOf’ relation are declared to be of the categories ‘person’ and ‘company’. CPL does not promote a pair of noun phrases as an instance of a relation unless the two noun phrases are
=== Algorithm
Following is a quick summary of the CPL algorithm.<ref name=cpl2010 />
Line 25 ⟶ 26:
Output: Trusted instances/patterns for each predicate
'''for''' i=1,2,...,∞ '''do'''
'''foreach''' predicate p in O '''do'''
EXTRACT candidate instances/contextual patterns using recently promoted patterns/instances;
FILTER candidates that violate coupling;
RANK candidate instances/patterns;
PROMOTE top candidates;
'''end'''
'''end'''
==== Inputs ====
A large [[Text corpus|corpus]] of Part-Of-Speech tagged sentences and an initial ontology with
==== Candidate extraction ====
CPL
* Category Instances
* Category Patterns
Line 43 ⟶ 44:
* Relation Patterns
==== Candidate
Candidate instances and patterns are
==== Candidate
CPL ranks candidate instances using the number of promoted patterns that they co-occur with so that candidates that occur with more patterns are ranked higher. Patterns are ranked using an estimate of the precision of each pattern.
==== Candidate
CPL ranks the candidates according to their assessment scores and promotes at most 100 instances and 5 patterns for each predicate. Instances and patterns
== Meta-Bootstrap Learner ==
Meta-Bootstrap Learner (MBL) was also proposed by the authors of CPL
'''Input''': An ontology O, a set of extractors ε
'''Output''': Trusted instances for each predicate
'''for''' i=1,2,...,∞ '''do'''
'''foreach''' predicate p in O '''do'''
'''foreach''' extractor e in ε '''do'''
Extract new candidates for p using e with recently promoted instances;
'''end'''
FILTER candidates that violate mutual-exclusion or type-checking constraints;
PROMOTE candidates that were extracted by all extractors;
'''end'''
'''end'''
Subordinate algorithms used with MBL do not promote any instance on their own, they report
== Applications ==
In their paper <ref name=cbl2009 /> authors have presented results showing the potential of CPL to contribute new facts to existing repository of semantic knowledge, Freebase <ref>{{cite journal|
== See also ==
Line 76 ⟶ 77:
* [[Never-Ending Language Learning]]
==
{{reflist}}
==References==
* {{cite journal|last=Liu|first=Qiuhua |
* {{cite journal|last=Shinyama|first=Yusuke|
* {{cite journal|last=Chang|first=Ming-Wei|author2=Lev-Arie Ratinov |author3=Dan Roth |year=2007|title=Guiding semi-supervision with constraint driven learning|journal=ACL}}
* {{cite journal|last=
* {{cite book|last=Blum|first=Avrim|author2=Tom Mitchell|title=Proceedings of the eleventh annual conference on Computational learning theory |chapter=Combining labeled and unlabeled data with co-training |year=1998|pages=92–100|doi=10.1145/279943.279962|isbn=1581130570|s2cid=207228399 }}
*
* {{cite journal|last=Rosenfeld|first=Benjamin|
* {{cite journal|last=
▲* {{cite journal|last=Rosenfeld|first=Benjamin|coauthors=Ronen Feldman|date=2007|title=Using corpus statistics on entities to improve semi-supervised relation extraction from the web|journal=ACL}}
[[Category:Machine learning]]
| |||