Jeff Jackson's Research Interests

Much of my research has been involved one way or another with questions about automatically learning DNF expressions from examples. A DNF expression is an OR of AND's of boolean expressions (DNF stands for "Disjunctive Normal Form"). Expressed in English, a DNF looks something like the condition of the following if-then:

 if
     it is raining 
   OR 
     the forecast calls for rain
       AND 
     you trust weather forecasts
   OR
     you like to always be prepared
       AND
     you are taking a briefcase
       AND
     your briefcase is not full
then 
   take an umbrella when you go out.

DNF expressions are particularly interesting to machine learning researchers because DNF is a natural means of representing many "expert" rules, like the one above. Furthermore, in very practical areas such as digital circuit design and implementation DNF expressions are used extensively, typically under a different name such as sum-of-products notation. So improving our understanding of DNF expressions themselves as well as methods for acquiring them from data in an automated fashion seems a potentially valuable enterprise.

My major result to date is an algorithm for efficiently learning DNF expressions in a specific (interesting) learning model. On the flip side, I also contributed to a paper that shows that DNF is probably not learnable in a more realistic model of learning. While this work has not fully resolved the DNF learnability questions, it has taken us well beyond where we were prior to this work.

In addition to this theoretical research, I have also been involved in developing and testing new applied machine learning algorithms. My approach has been to take what seem to be especially insightful ideas from theory and look for ways to incorporate them in practice. This also feeds back new questions for theoretical consideration.

I have also taken several side trips that have produced some interesting results. I developed--and with a Nasa researcher tested with human subjects--an automated gesture recognition system. I also contributed to a nice comparative study of the impact that object-oriented software design has on development productivity. Even my eight years spent as a software engineer and manager led to the publication of a "lessons-learned" paper. A more-or-less complete list of my conference and journal publications can be found below; several are on-line, and I can email copies of most others on request.

One other major "research" side trip involved writing my textbook, Web Technologies: A Computer Science Perspective. While this book is not related to my scientific research publications list below, it did involve a tremendous amount of time spent researching (in the college term paper sense) web references.

Some links to other information about me and some of what I'm involved in:

• My official Duquesne home page, which includes links to my courses
• Duquesne University's Department of Mathematics and Computer Science
• Duquesne University's Computational Mathematics Program
• Work by some of my students:
  • Wenzhu Bi (MS thesis)
    
  • Miao Chen (MS thesis)
    
  • Livia Overand (undergraduate research)
  • Marisa Smith (MS thesis)
    

Papers

• Jackson, J. C., Uniform-Distribution Learnability of Noisy Linear Threshold Functions with Restricted Focus of Attention, Proceedings of 19th Annual Conference on Learning Theory, 2006.
• Jackson, J. C., and Servedio, R. A., On Learning Random DNF Formulas Under the Uniform Distribution, Theory of Computing 2, 2006.  Preliminary version in Proceedings of 9th International Workshop on Randomization and Computation, RANDOM 2005.
• Jackson, J. C., and Servedio, R. A., Learning Random log-depth Decision Trees under the Uniform Distribution, SIAM Journal on Computing 34/5, 2005.  Preliminary version in Proceedings of the 16th Annual Workshop on Computational Learning Theory, 2003.
• Bshouty, N. H., Jackson, J. C., and Tamon, C., Exploring Learnability Between Exact and PAC, Journal of Computer and System Sciences 70/4 (Special Issue on COLT 2002, invited), 2005.  Preliminary version in Proceedings of the 15th Annual Workshop on Computational Learning Theory, 2002.
  
• Blum, A., Jackson, J., Sandholm, T., and Zinkevich, M., Preference Elicitation and Query Learning, Journal of Machine Learning Research 5 (Special Topic on Learning Theory, invited), June 2004.  Preliminary version in Proceedings of the 16th Annual Workshop on Computational Learning Theory, 2003.
• Bshouty, N., Jackson, J., and Tamon, T., More Efficient PAC-learning of DNF with Membership Queries Under the Uniform Distribution, Journal of Computer and System Sciences 68, 2004.  Preliminary version in Proceedings of the 12th Annual Workshop on Computational Learning Theory, 1999.  Preliminary extended version: postscript (.ps) or portable document format (.pdf).
• Bshouty, N., Jackson, J., and Tamon, T., Uniform-Distribution Attribute Noise Learnability, Information and Computation 187(2),  December 2003.  Preliminary version in Proceedings of the 12th Annual Workshop on Computational Learning Theory, 1999. Preliminary extended version: postscript (.ps) or portable document format (.pdf).
• Jackson, J. C., Klivans, A. R., and Servedio, R. A., Learnability Beyond AC⁰, Proceedings of the Symposium on the Theory of Computing 2002. Preliminary version: postscript (.ps) or portable document format (.pdf).
• Jackson, J., On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries, Proceedings of the 13th Annual Workshop on Computational Learning Theory, 2000. Accepted for publication in Annals of Mathematics and Artificial Intelligence. Preliminary extended version: postscript (.ps) or portable document format (.pdf).
• Bshouty, N. H. and Jackson, J. C., Learning DNF over the Uniform Distribution using a Quantum Example Oracle, SIAM Journal on Computing 28(3), 1999. Preliminary version in Proceedings of the Eighth Annual Workshop on Computational Learning Theory, 1995, 118-127. Preliminary extended version: postscript (.ps) or portable document format (.pdf).
• Jackson, J., Shamir, E., and Shwartzman, C., Learning with Queries Corrupted by Classification Noise, Discrete Applied Mathematics 92(2-3), 1999. Preliminary version in Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems, IEEE Press, 1997. Preliminary extended version: postscript (.ps) or portable document format (.pdf).
• Birkendorf, A., Dichterman, E., Jackson, J., Klasner, N., and Simon, H. U., On Restricted-Focus-of-Attention Learnability of Boolean Functions, Machine Learning 30, 1998. Preliminary version in Proceedings of the Ninth Annual Workshop on Computational Learning Theory, 1996. Preliminary extended version: postscript (.ps) or portable document format (.pdf).
• Anderson, B., Jackson, J., and Sitharam, M., Descartes' Rule of Signs Revisited, American Mathematical Monthly, May 1998.
• Jackson, J., An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution, Journal of Computer and System Sciences 55(3), 1997. Preliminary version in Proceedings of the 35th Symposium on Foundations of Computer Science, 1994, 42-53. A preliminary extended version of this paper is available for download.
• Jackson, J. and Craven, M., Learning Sparse Perceptrons, Advances in Neural Information Processing Systems 8 (Conference Proceedings of NIPS*95), 1996. Postscript (.ps) or portable document format (.pdf).
• Jackson, J. The Harmonic Sieve: A Novel Application of Fourier Analysis to Machine Learning Theory and Practice, PhD Thesis, Carnegie Mellon University, 1995, technical report CMU-CS-95-183. Also available in zipped PDF format.
• Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich, S., Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis, Proceedings of the Twenty-Sixth Annual Symposium on the Theory of Computing, 1994, 253-262. (Very) preliminary version: postscript (.ps) or portable document format (.pdf).
• Blum, A., Chalasani, P., and Jackson, J., On Learning Embedded Symmetric Concepts, Proceedings of Sixth Annual Workshop on Computational Learning Theory, 1993, 337-346.
• Bruegge, B., Blythe, J., Jackson, J., and Shufelt, J., Object-Oriented System Modeling with OMT, Proceedings of Conference on Object-oriented Programming Systems, Languages, and Applications, 1992, 359-376. Proceedings published as SIGPLAN Notices, vol. 27, no. 10, October 1992.
• Jackson, J. and Tomkins, A., A Computational Model of Teaching, Proceedings of Fifth Annual Workshop on Computational Learning Theory, 1992, 319-326.
• Furst, M. L., Jackson, J. C., and Smith, S. W., Improved Learning of $AC^0$ Functions, Proceedings of Fourth Annual Workshop on Computational Learning Theory, 1991, 317-325. See also Furst, M., Jackson, J., and Smith, S., Learning $AC^0$ Functions Sampled Under Mutually Independent Distributions, technical report CMU-CS-90-183, October 1990.
• Jackson, J. C. and Roske-Hofstrand, R. J., Circling: A Method of Mouse-Based Selection without Button Presses, Proceedings of CHI, 1989 (Conference on Computer-Human Interaction), 1989, 161-166. Proceedings published as SIGCHI Bulletin, special issue, May 1989.
• Jackson, J. C., Observations on Integrating Interactive Graphics into Large Batch-Oriented Simulations, Proceedings of the Second Oklahoma Workshop on Applied Computing, March 1988, 319-326.
• Palmer, I. D., Jackson, J. C., and Hones, Jr., E. W., Entry of Solar Protons to the Plasma Sheet and Lobe of the Magnetotail at r=18R_E in the Event of April 22, 1971, Journal of Geophysical Research, Vol. 84 (1979), 2630-2640.
• Palmer, I. D., Jackson, J. C., and Hones, Jr., E. W., The Solar Proton Event of April 16, 1970. 3. Evolution of Pitch Angle Distribution as $\leq 1$-MeV Protons Propagate into the High-Latitude Magnetotail, Journal of Geophysical Research, Vol. 84 (1979), 109-119.