dc.contributor.advisor 
Zilles, Sandra 

dc.contributor.author 
Fan, Gaojian 

dc.date.accessioned 
20121113T20:33:15Z 

dc.date.available 
20121113T20:33:15Z 

dc.date.issued 
201207 

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 graphtheoretic 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 oneinclusion graph; In this graph the vertices are concepts and there is an edge between two concepts if they disagree on exactly one instance. Oneinclusion 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 oneinclusion 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 oneinclusion graph. Furthermore, we prove that for concepts in shortestpathclosed classes, the lower bounds are always attained.
We then prove that the average case teaching complexity of any shortestpathclosed class is linearly upperbounded by the VapnikChervonenkis (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 shortestpathclosed 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
shortestpathclosure in terms of minimum teaching sets and the oneinclusion graph.
As the oneinclusion 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 oneinclusion graph, the vertex degrees in the minimal Hamming graph provide nontrivial 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 shortestpathclosed classes. We prove that the minimal Hamming graphs of such classes are trianglefree and K2;3free. Some interesting sufficient conditions for local orthogonality are also studied.
We show that the graphtheoretic results on teachability are useful for studying sample compression schemes. A universal sample compression schemethe peeling sample compression scheme is presented. This compression scheme generalizes some
stateoftheart compression schemes. In addition, we show that the size of this compression scheme is related to teaching complexity if certain graphtheoretic 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 
ConceptsStudy and teaching 

dc.subject.lcsh 
Computational learning theory 

dc.subject.lcsh 
Teaching 

dc.subject.lcsh 
Graphic methods 

dc.title 
A GraphTheoretic 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 
