{{Short description|Machine learning algorithm}} '''Co-training''' is a machine learning algorithm used when there are only small amounts of labeled data and large amounts of unlabeled data. One of its uses is in text mining for search engines. It was introduced by Avrim Blum and Tom Mitchell in 1998.
==Algorithm design== Co-training is a semi-supervised learning technique that requires two ''views'' of the data. It assumes that each example is described using two different sets of features that provide complementary information about the instance. Ideally, the two views are conditionally independent (i.e., the two feature sets of each instance are conditionally independent given the class) and each view is sufficient (i.e., the class of an instance can be accurately predicted from each view alone). Co-training first learns a separate classifier for each view using any labeled examples. The most confident predictions of each classifier on the unlabeled data are then used to iteratively construct additional labeled training data.<ref>Blum, A., Mitchell, T. [http://repository.cmu.edu/cgi/viewcontent.cgi?article=1181&context=compsci&sei-redir=1&referer=http%3A%2F%2Fscholar.google.com%2Fscholar%3Fq%3DCombining%2Blabeled%2Band%2Bunlabeled%2Bdata%2Bwith%2Bco-training%26hl%3Den%26as_sdt%3D0%26as_vis%3D1%26oi%3Dscholart%26sa%3DX%26ei%3D_NlxT7nlHNSA8gPKgqVK%26ved%3D0CBoQgQMwAA#search=%22Combining%20labeled%20unlabeled%20data%20co-training%22 Combining labeled and unlabeled data with co-training]. ''COLT: Proceedings of the Workshop on Computational Learning Theory'', Morgan Kaufmann, 1998, p. 92-100.</ref>
The original co-training paper described experiments using co-training to classify web pages into "academic course home page" or not; the classifier correctly categorized 95% of 788 web pages with only 12 labeled web pages as examples.<ref name=reflections/> The paper has been cited over 1000 times, and received the 10 years Best Paper Award at the 25th International Conference on Machine Learning (ICML 2008), a renowned computer science conference.<ref>{{cite web|url=http://videolectures.net/icml08_mccallum_papers/|title=Best Papers Awards|last=McCallum|first=Andrew|year=2008|work=ICML Awards|accessdate=2009-05-03}}</ref><ref>{{cite web|url=http://videolectures.net/icml08_shavlik_clud/|title=10 Year Best Paper: Combining labeled and unlabled data with co-training|last=Shavik|first=Jude|year=2008|work=ICML Awards|accessdate=2009-05-03}}</ref>
Krogel and Scheffer showed in 2004 that co-training is only beneficial if the data sets are independent; that is, if one of the classifiers correctly labels a data point that the other classifier previously misclassified. If the classifiers agree on all unlabeled data, i.e. they are dependent, labeling the data does not create new information. In an experiment where dependence of the classifiers was greater than 60%, results worsened.<ref>{{cite journal|last=Krogel|first=Marc-A|author2=Tobias Scheffer|year=2004|title=Multi-Relational Learning, Text Mining, and Semi-Supervised Learning for Functional Genomics|journal=Machine Learning|volume=57|pages=61–81|url=https://www.cs.uni-potsdam.de/ml/publications/mlj2004.pdf|doi=10.1023/B:MACH.0000035472.73496.0c|doi-access=free}}</ref>
==Uses== Co-training has been used to classify web pages using the text on the page as one view and the anchor text of hyperlinks on other pages that point to the page as the other view. Simply put, the text in a hyperlink on one page can give information about the page it links to.<ref name=reflections>{{cite book|last=Committee on the Fundamentals of Computer Science: Challenges and Opportunities, National Research Council |title=Computer Science: Reflections on the Field, Reflections from the Field|publisher=The National Academies Press|year=2004|chapter=6: Achieving Intelligence|isbn=978-0-309-09301-9|chapter-url=http://books.nap.edu/openbook.php?isbn=0309093015&page=101}}</ref> Co-training can work on "unlabeled" text that has not already been classified or tagged, which is typical for the text appearing on web pages and in emails. According to Tom Mitchell, "The features that describe a page are the words on the page and the links that point to that page. The co-training models utilize both classifiers to determine the likelihood that a page will contain data relevant to the search criteria." Text on websites can judge the relevance of link classifiers, hence the term "co-training". Mitchell claims that other search algorithms are 86% accurate, whereas co-training is 96% accurate.<ref name=techreview>{{cite news|url=https://www.technologyreview.com/web/12353/|title=Search Engines Ready to Learn|last=Aquino|first=Stephen|date=24 April 2001|work=Technology Review|accessdate=2009-05-03}}</ref>
Co-training was used on FlipDog.com, a job search site, and by the U.S. Department of Labor, for a directory of continuing and distance education.<ref name=techreview/> It has been used in many other applications, including statistical parsing and visual detection.<ref>{{cite journal|last=Xu|first=Qian|author2=Derek Hao Hu |author3=Hong Xue |author4=Weichuan Yu |author5=Qiang Yang |title=Semi-supervised protein subcellular localization|journal=BMC Bioinformatics|volume=10|pages=S47|issn=1471-2105|doi=10.1186/1471-2105-10-S1-S47|pmid=19208149|year=2009|issue=Suppl 1 |pmc=2648770 |doi-access=free }}</ref>
== References == {{reflist|30em}} ;Notes *{{cite book|last=Chakrabarti |first=Soumen|title=Mining the Web: Discovering Knowledge from Hypertext Data|publisher=Morgan-Kaufmann Publishers|year=2002|pages=352|isbn=978-1-55860-754-5|url=https://www.cse.iitb.ac.in/~soumen/mining-the-web/}} *{{cite journal|last=Nigam|first=Kamal|author2=Rayid Ghani|year=2000|title=Analyzing the Effectiveness and Applicability of Co-training|journal=Proceedings of the Ninth International Conference on Information and Knowledge Management |publisher=ACM|location=NY, USA|pages=86–93|citeseerx=10.1.1.37.4669}} *{{cite book|last=Abney|first=Steven|title=Semisupervised Learning for Computational Linguistics|publisher=Chapman & Hall|year=2007|series=CRC Computer Science & Data Analysis|pages=308|isbn=978-1-58488-559-7|url=http://www.crcpress.com/product/isbn/9781584885597}} *{{cite book|last=Wang|first=William Yang|author2=Kapil Thadani |author3=Kathleen McKeown |title=Identifying Event Descriptions using Co-training with Online News Summaries|publisher=AFNLP & ACL|year=2011|series=the 5th International Joint Conference on Natural Language Processing (IJCNLP 2011)|url=https://www.cs.cmu.edu/~yww/papers/ijcnlp2011.pdf}}
==External links== *[http://videolectures.net/mlas06_mitchell_sla/ Lecture by Tom Mitchell introducing co-training and other semi-supervised machine learning for use on unlabeled data] *[http://videolectures.net/wehys08_blum_ssll/ Lecture by Avrim Blum on semi-supervised learning, including co-training] *[https://web.archive.org/web/20080511210927/http://www.learnlab.org/clusters/co-training/index.php Co-Training group at Pittsburgh Science of Learning Center]
Category:Classification algorithms