This thesis is concerned with the problem of learning comprehensible theories from structured data and covers primarily classification and regression learning. The basic knowledge representation language is set around a polymorphically-typed, higher-order logic. The general setup is closely related to the learning from propositionalized knowledge and learning from interpretations settings in Inductive Logic Programming. Individuals (also called instances) are represented as terms in the logic. A grammar-like construct called a predicate rewrite system is used to define features in the form of predicates that individuals may or may not satisfy. For learning, decision-tree algorithms of various kinds are adopted.¶ The scope of the thesis spans both theory and practice. On the theoretical side, I study in this thesis¶ 1. the representational power of different function classes and relationships between them;¶ 2. the sample complexity of some commonly-used predicate classes, particularly those involving sets and multisets;¶ 3. the computational complexity of various optimization problems associated with learning and algorithms for solving them; and¶ 4. the (efficient) learnability of different function classes in the PAC and agnostic PAC models.¶ On the practical side, the usefulness of the learning system developed is demontrated with applications in two important domains: bioinformatics and intelligent agents. Specifically, the following are covered in this thesis:¶ 1. a solution to a benchmark multiple-instance learning problem and some useful lessons that can be drawn from it;¶ 2. a successful attempt on a knowledge discovery problem in predictive toxicology, one that can serve as another proof-of-concept that real chemical knowledge can be obtained using symbolic learning;¶ 3. a reworking of an exercise in relational reinforcement learning and some new insights and techniques we learned for this interesting problem; and¶ 4. a general approach for personalizing user agents that takes full advantage of symbolic learning.