Using Algebraic Datatypes as Uniform Representation for Structured Data

Abstract: The question of how to uniformly encode structured data for the purpose of machine learning seems to have been rather neglected so far by researchers in comparison to the abundance of approaches how knowledge could be inferred from certain representations. We therefore propose a well-understood concept from the formal semantics of programming languages as vehicle for the uniform representation of discrete data, namely algebraic datatypes. It will be demonstrated in theory and practice that current encodings severely limit the power of widespread machine learning techniques especially what concerns handling of structured information, how algebraic datatypes elegantly extend expressiveness to evade these limitations and that this concept can guide the way to new learning algorithms. As an example, it will be shown how ordinary decision tree learning can be efficiently generalized to this data representation and that the latter provides for an interesting solution both to the missing value problem and to the representation of structured multi-attribute goals. Tight theoretical relations to logic yield valuable insights into complexity and expressiveness.

• Introduction
• Intuitive example: Algebraic datatypes make tasty meals
  • Cooking indistinguishable food can make meals uneatable
  • Spicing meals with algebraic datatypes
  • Unbounded customer satisfaction with inductively defined data structures
  • Partial knowledge of tastes
• Generalizing Decision Tree Learning to Algebraic Datatypes
  • Description of the generalized algorithm by example
  • Entropy measures and choosing input variables for partitioning the dataset
  • Computing the most likely value
  • Assessing accuracy
  • Model factorization
  • Handling products of products
  • Efficiency of generalized decision tree learning
• Practical aspects
  • Novel solution to the missing value problem
  • Expert systems
  • Natural language processing
• Theoretical aspects
• Future work
  • Polymorphic recipes
  • Exotic meals made from abstract cooking techniques
  • Recursive functions
• References

This document was translated from L^AT_EX by H^EV^EA.