A Graph-Theoretic View of Teaching

Show simple item record

dc.contributor.advisor Zilles, Sandra
dc.contributor.author Fan, Gaojian
dc.date.accessioned 2012-11-13T20:33:15Z
dc.date.available 2012-11-13T20:33:15Z
dc.date.issued 2012-07
dc.identifier.uri http://hdl.handle.net/10294/3627
dc.description A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. X, 85 l. en_US
dc.description.abstract In computational learning theory, concepts are subsets of a set of instances and a concept class is a set of concepts. In many computational learning models, learning algorithms have the goal to identify the target concept in a concept class from a small number of examples, i.e., labelled instances. We study graph-theoretic representations of concept classes and their connections to a particular notion of learning complexity, namely teaching complexity. Teaching complexity is a complexity measure for the number of training examples needed in teaching models in which a helpful teacher provides examples to the learner. One type of graph that we study in this thesis is the one-inclusion graph; In this graph the vertices are concepts and there is an edge between two concepts if they disagree on exactly one instance. One-inclusion graphs have proven useful in analyzing some computational learning properties, e.g., sample compression sizes and expected mistake bounds of prediction algorithms. This thesis establishes strong connections between one-inclusion graphs and teaching complexity. We show that the teaching dimension of a concept, i.e., the minimum number of examples required for teaching that concept, is lower bounded by the degree of the corresponding vertex in the one-inclusion graph. Furthermore, we prove that for concepts in shortest-path-closed classes, the lower bounds are always attained. We then prove that the average case teaching complexity of any shortest-path-closed class is linearly upper-bounded by the Vapnik-Chervonenkis (VC) dimension of the class. As the VC dimension reflects the complexity of learning from randomly chosen examples, our theorem gives the evidence that, for the shortest-path-closed concept classes, the average difficulty of learning from a helpful teacher is not higher than that of learning from random examples. We also provide the first characteristic property of shortest-path-closure in terms of minimum teaching sets and the one-inclusion graph. As the one-inclusion graphs only provide partial distinguishing information between concepts, we introduce a new type of graph called minimal Hamming graph which provides the complete distinguishing information between concepts. In contrast to the one-inclusion graph, the vertex degrees in the minimal Hamming graph provide non-trivial upper bounds on the teaching dimension of concepts. Furthermore, we define locally orthogonal concept classes in which the teaching dimension of the concepts always meets the upper bound. We also show that locally orthogonal concept classes generalize the shortest-path-closed classes. We prove that the minimal Hamming graphs of such classes are triangle-free and K2;3-free. Some interesting sufficient conditions for local orthogonality are also studied. We show that the graph-theoretic results on teachability are useful for studying sample compression schemes. A universal sample compression scheme|the peeling sample compression scheme is presented. This compression scheme generalizes some state-of-the-art compression schemes. In addition, we show that the size of this compression scheme is related to teaching complexity if certain graph-theoretic criteria are fulfilled. en_US
dc.language.iso en en_US
dc.publisher Faculty of Graduate Studies and Research, University of Regina en_US
dc.subject.lcsh Concepts--Study and teaching
dc.subject.lcsh Computational learning theory
dc.subject.lcsh Teaching
dc.subject.lcsh Graphic methods
dc.title A Graph-Theoretic View of Teaching en_US
dc.type Thesis en
dc.description.authorstatus Student en
dc.description.peerreview yes en
thesis.degree.name Master of Science (MSc) en_US
thesis.degree.level Master's en
thesis.degree.discipline Computer Science en_US
thesis.degree.grantor University of Regina en
thesis.degree.department Department of Computer Science en_US
dc.contributor.committeemember Yang, Boting
dc.contributor.committeemember Yao, Yiyu
dc.contributor.externalexaminer Meagher, Karen
dc.identifier.tcnumber TC-SRU-3627
dc.identifier.thesisurl http://ourspace.uregina.ca/bitstream/handle/10294/3627/Fan_Gaojian_200297809_MSC_CS_Fall2012.pdf

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search oURspace


My Account