-------------------------------------------------------------------------------
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			 P H D   D E F E N S E
                                       
			  Friday June 23, 1995
                                       
				 2:00pm
                                       
			 Seminar Room / MCS 135

		    Major Advisor: Prof. Steve Homer

-------------------------------------------------------------------------------

	  Computational Learning Algorithms For Geometric and
			   Algebraic Objects

			     Zhixiang Chen

  The goal of this thesis is to study the efficient learnability of basic
  geometric and algebraic objects in on-line learning models.
  Computational learning algorithms for rectangles and unions of
  rectangles over the domain $\{0, \ldots, n-1\}^{d}$ are designed and
  analyzed.  We develop a bounded version of the powerful and dominant
  design technique in recursion theory, the finite injury priority method,
  and use it to construct several concrete algorithms for learning unions
  of rectangles.  We design an algorithm for properly learning rectangles
  over the domain $[0, n-1]^{d}$ with $O(d^{2}\log n)$ equivalence
  queries.  For the problem of learning unions of two rectangles, we
  design three efficient algorithms.  The first algorithm learns unions of
  two disjoint rectangles over the domain $[0, n-1]^{d}$ with equivalence
  queries and uses unions of two rectangles as hypotheses.  The second
  algorithm properly learns unions of two rectangles over the domain $[0,
  n-1]^{2}$ with $O(\log^{2} n)$ equivalence queries.  The third algorithm
  properly learns unions of two rectangles over the domain $[0, n-1]^{d}$
  with both equivalence and membership queries.  The query complexity of
  this algorithm is optimal.  We also design an efficient algorithm for
  learning unions of rectangles whose projections on some unknown
  dimension are pairwise disjoint.  When $d$ is a constant, we show that
  unions of rectangles over the domain $[0, n-1]^{d}$ are efficiently
  learnable with equivalence queries.
  
  Next we study the problem of learning DNF formulas with equivalence
  queries and incomplete membership queries.  We show that there is a
  subclass of $k$-term DNF formulas for nonconstant $k$ such that one can
  learn any formula in this class with high probability.
  
  Finally we study the problem of learning disjunctions of counting
  functions with modulus $q$ over the domain $Z^{n}_{q}$.  We show that
  for any prime $q$, one can learn disjunctions of counting functions over
  the domain $Z^{n}_{q}$ with at most $n+1$ queries.  We prove that the
  problem of learning disjunctions of negated counting functions is in
  general harder than learning DNF formulas.  However, we also show that
  efficient algorithms exist for this problem when the modulus is a
  constant prime, or when the modulus is a prime and the number of negated
  functions is bounded.

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------