Teaching with Examples in A Real Environment

Teaching is challenging in a real environment. One problem is that not all examples may be available to teach. We show how to teach several important concept classes namely conjunction, disjunction and linear threshold functions under different characterizations of the domain of available examples. We show that a monotone linear threshold function is teachable using a polynomial number of examples when the accessible domain is defined by the intersection of multiple monotone linear threshold functions. Also, a teacher may not be smart enough to know the target concept exactly but he may be able to provide better examples from available examples. We show how to teach without knowing the target concept exactly and using only available examples. Our experiments on the benchmark data sets of text categorization and movie review classification show that the algorithm Partial Instance Feedback (PIF) results in 8-11% error reduction over active learning and 16-18% error reduction over random sampling.unpublishednot peer reviewe