Never Ending Learning Tom M Mitchell Justin Betteridge Jamie Callan Andy Carlson William Cohen Estevam Hruschka Bryan Kisiel Mahaveer Jain Jayant Krishnamurthy Edith Law Thahir Mohamed Mehdi Samadi Burr Settles Richard Wang Derry Wijaya Machine Learning Department Carnegie Mellon University March 2011 Humans learn many things for years and become better learners over time Why not machines 1 Never Ending Learning Task acquire a growing competence without asymptote over years multiple functions where learning one thing improves ability to learn the next acquiring data from humans environment Many candidate domains Robots Softbots Game players Tweeters NELL Never Ending Language Learner Inputs initial ontology handful of examples of each predicate in ontology the web occasional interaction with human trainers The task run 24x7 forever each day 1 extract more facts from the web to populate the initial ontology 2 learn to read perform 1 better than yesterday 2 NELL Never Ending Language Learner Goal run 24x7 forever each day 1 extract more facts from the web to populate given ontology 2 learn to read better than yesterday Today Running 24x7 since January 12 2010 Input ontology defining 500 categories and relations 10 20 seed examples of each 500 million web pages ClueWeb Jamie Callan Result continuously growing KB with 525 000 extracted beliefs NELL Today http rtw ml cmu edu eg Disney Mets IBM Pittsburgh 3 Semi Supervised Bootstrap Learning it s underconstrained Extract cities San Francisco Austin denial Paris Pittsburgh Seattle Cupertino mayor of arg1 live in arg1 anxiety selfishness Berlin arg1 is home of traits such as arg1 Key Idea 1 Coupled semi supervised training of many functions person NP hard underconstrained semi supervised learning problem much easier more constrained semi supervised learning problem 4 Type 1 Coupling Co Training Multi View Learning person Blum Mitchell 98 Dasgupta et al 01 Ganchev et al 08 Sridharan Kakade 08 Wang Zhou ICML10 NP Type 1 Coupling Co Training Multi View Learning person Blum Mitchell 98 Dasgupta et al 01 Ganchev et al 08 Sridharan Kakade 08 Wang Zhou ICML10 NP 5 Type 1 Coupling Co Training Multi View Learning Blum Mitchell 98 Dasgupta et al 01 Ganchev et al 08 Sridharan Kakade 08 Wang Zhou ICML10 person NP Type 2 Coupling Multi task Structured Outputs person athlete Daume 2008 Bakhir et al eds 2007 Roth et al 2008 Taskar et al 2009 Carlson et al 2009 sport coach team athlete NP person NP NP athlete NP NOT sport NP NOT athlete NP sport NP 6 Multi view Multi Task Coupling person athlete sport coach team NP NP text context distribution NP NP HTML morphology contexts Learning Relations between NP s playsSport a s playsForTeam a t NP1 teamPlaysSport t s coachesTeam c t NP2 7 playsSport a s playsForTeam a t person teamPlaysSport t s sport athlete coachesTeam c t person sport athlete coach team team coach NP1 NP2 Type 3 Coupling Argument Types playsSport NP1 NP2 athlete NP1 sport NP2 playsSport a s playsForTeam a t person teamPlaysSport t s sport athlete coachesTeam c t person sport athlete coach NP1 team coach NP2 team 1200 coupled functions in NELL 8 Pure EM Approach to Coupled Training E estimate labels for each function of each unlabeled example M retrain all functions using these probabilistic labels Scaling problem E step 20M NP s 1014 NP pairs to label M step 50M text contexts to consider for each function 1010 parameters to retrain even more URL HTML contexts NELL s Approximation to EM E step Consider only a growing subset of the latent variable assignments category variables up to 250 new NP s per category per iteration relation variables add only if confident and args of correct type this set of explicit latent assignments IS the knowledge base M step Each view based learner retrains itself from the updated KB context methods create growing subsets of contexts 9 NELL Architecture Knowledge Base latent variables Beliefs Evidence Integrator Candidate Beliefs Text Context patterns CPL HTML URL context patterns SEAL Morphology classifier CML Learning and Function Execution Modules Never Ending Language Learning arg1 was playing arg2 arg2 megastar arg1 arg2 icons arg1 arg2 player named arg1 arg2 prodigy arg1 arg1 is the tiger woods of arg2 arg2 career of arg1 arg2 greats as arg1 arg1 plays arg2 arg2 player is arg1 arg2 legends arg1 arg1 announced his retirement from arg2 arg2 operations chief arg1 arg2 player like arg1 arg2 and golfing personalities including arg1 arg2 players like arg1 arg2 greats like arg1 arg2 players are steffi graf and arg1 arg2 great arg1 arg2 champ arg1 arg2 greats such as arg1 arg2 professionals such as arg1 arg2 hit by arg1 arg2 greats arg1 arg2 icon arg1 arg2 stars like arg1 arg2 pros like arg1 arg1 retires from arg2 arg2 phenom arg1 arg2 lesson from arg1 arg2 architects robert trent jones and arg1 arg2 sensation arg1 arg2 pros arg1 arg2 stars venus and arg1 arg2 hall of famer arg1 arg2 superstar arg1 arg2 legend arg1 arg2 legends such as arg1 arg2 players is arg1 arg2 pro arg1 arg2 player was arg1 arg2 god arg1 arg2 idol arg1 arg1 was born to play arg2 arg2 star arg1 arg2 hero arg1 arg2 players are arg1 arg1 retired from professional arg2 arg2 legends as arg1 arg2 autographed by arg1 arg2 champion arg1 10 text HTML Coupled Coupled Training Helps Carlson et al WSDM 2010 Using only two views Text HTML contexts Text uncpl HTML uncpl Coupled Categories 41 59 90 Relations 69 91 95 PRECISION 10 iterations 200 M web pages 44 categories 27 relations 199 extractions per category If coupled learning is the key idea how can we get new coupling constraints 11 Key Idea 2 Discover New Coupling Constraints first order probabilistic horn clause constraints 0 93 athletePlaysSport x y athletePlaysForTeam x z teamPlaysSport z y connects previously uncoupled relation predicates infers new beliefs for KB Discover New Coupling Constraints For each relation seek probabilistic first order Horn Clauses Positive examples extracted beliefs in the KB Negative examples Ontology to the rescue numberOfValues teamPlaysSport 1 numberOfValues competesWith any can infer negative examples from positive for this but not for this 12 Example Learned Horn Clauses 0 95 athletePlaysSport x basketball athleteInLeague x NBA 0 93 athletePlaysSport x y athletePlaysForTeam x z teamPlaysSport z y 0 91 teamPlaysInLeague x NHL teamWonTrophy x Stanley Cup 0 90 athleteInLeague x y athletePlaysForTeam x z teamPlaysInLeague z y 0 88 cityInState x y cityCapitalOfState
View Full Document
Unlocking...