NDLI: Active Learning from Relative Comparisons

Content Provider	IEEE Xplore Digital Library
Author	Sicheng Xiong Yuanli Pei Rosales, R. Fern, X.Z.
Copyright Year	1989
Abstract	This work focuses on active learning from relative comparison information. A relative comparison specifies, for a data triplet (x_i, x_j, x_k), that instance xi is more similar to x_j than to x_k. Such constraints, when available, have been shown to be useful toward learning tasks such as defining appropriate distance metrics or finding good clustering solutions. In real-world applications, acquiring constraints often involves considerable human effort, as it requires the user to manually inspect the instances. This motivates us to study how to select and query the most useful relative comparisons to achieve effective learning with minimum user effort. Given an underlying class concept that is employed by the user to provide such constraints, we present an information-theoretic criterion that selects the triplet whose answer leads to the highest expected information gain about the classes of a set of examples. Directly applying the proposed criterion requires examining O(n³) triplets with n instances, which is prohibitive even for datasets of moderate size. We show that a randomized selection strategy can be used to reduce the selection pool from O(n³) to O(n) with minimal loss in efficiency, allowing us to scale up to considerably larger problems. Experiments show that the proposed method consistently outperforms baseline policies.
Sponsorship	IEEE IEEE Comput. Soc. Tech. Committee on Data Eng IEEE Computer Society
Starting Page	3166
Ending Page	3175
Page Count	10
File Size	547999
File Format	PDF
ISSN	10414347
Volume Number	27
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Measurement Uncertainty Learning systems Complexity theory Clustering algorithms Relative Comparisons Active Learning relative comparisons Active learning
Content Type	Text
Resource Type	Article
Subject	Information Systems Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Active Learning of Constraints for Semi-Supervised Clustering

Semisupervised Clustering with Metric Learning using Relative Comparisons

Active Trace Clustering for Improved Process Discovery

Dynamic Dissimilarity Measure for Support-Based Clustering

Reducing the Loss of Information through Annealing Text Distortion

Cluster-Based Boosting

Clustering Large Probabilistic Graphs

Successive Group Selection for Microaggregation

Redefining clustering for high-dimensional applications

Active Learning from Relative Comparisons

Similar Documents

Active Learning of Constraints for Semi-Supervised Clustering

Semisupervised Clustering with Metric Learning using Relative Comparisons

Active Trace Clustering for Improved Process Discovery

Dynamic Dissimilarity Measure for Support-Based Clustering

Reducing the Loss of Information through Annealing Text Distortion

Cluster-Based Boosting

Clustering Large Probabilistic Graphs

Successive Group Selection for Microaggregation

Redefining clustering for high-dimensional applications

Active Learning from Relative Comparisons