Machine Learning

I. Knowledge Acquisition

Introduction

The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform.[Lovelace, 1961]

Definition (of learning): Learning denotes changes in the system that are adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more efficiently and more effectively the next time. (Simon, in Machine Learning An AI Approach, 1983) Note: Often humans are interested in learning not so that the same task can be done over and over, but so that we acquire the ability to perform a wide range of tasks (similar problems)

Paradigm History:

1. Neural modeling- Perceptrons [Rosenblatt, 1958; Minsky & Papert, 1969] self-organizing systems
   • Learning here consisted of incremental changes in the probabilities that neuron-like elements would transmit a signal
   • Groundwork: McCullouch and Pitts [1943] discovered the ability of symbolic logic to model nervous system activities

     (related research: simulation of evolutionary processes, that through random mutation and "natural selection" might create a system capable of some intelligent behavior.[Friedberg, 1958, 1959; Holland, 1980] )

2. Pattern Recognition (decision-theoretic techniques)
   • Learning is equated with the acquisition of linear, polynomial, or related forms of discriminant functions from a given set of training examples
   • One of best known: Samuel's checkers program [Samuel, 1959, 1963]

   1&2 acquire knowledge (learn) by adjusting pararameters in algebraic expressions. For example, perceptrons adjust weighting coefficients for threshold logic elements when learning to recognize two-dimensional patterns.
   Note: All the knowledge was contained in the definition of the parameters rather than in the associated numerical values. I.E., He (Samuel's) defined the concept of "move centrality" and the real learning was done by inventing and recognizing the importance of this parameter rather than its numeric value...so in reality, it was done by Samuel himself.
3. Symbolic Descriptions and Symbolic concept-oriented learning

   This paradigm utilized logic or graphic structure representations rather than numeric or statistical methods

   • *Samuel's again
   • *Rules: Dendral [Buchanan et al., 1971] (mass spectrometry)
   Now systems could learn symbolic descriptions representing higher level knowledge and make structural assumptions about the concepts to be acquired:
   • Meta-Dendral [Buchanan, 1978](Role: to help the chemist determine the relationship between molecular fragmentations (spectral processes) and the structural features of compounds) (used version spaces (Mitchell))
   • Winston's structural learning system [Winston, 1975]
   • Inductive learning programs[Michalski, 1972; Mitchell, 1978]
4. Knowledge Intensive Structures
   • Strong emphasis on the use of task-oriented knowledge and the constraints it provides in guiding the learning process
   • Exploration of alternative methods of learning (not just by example)

-Introduction

1. Adaptive Systems

   Most agree that a required characteristic of learning systems be that the system is adaptive, capable of improving their performance on a problem as a function of previous experience. "...changes in the system that are adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more efficiently and more effectively the next time. " One adapts by changing their knowledge and acquiring and using new knowledge (of both task and domain)

2. Knowledge Acquisition vs. Skill Refinement

   Learning covers a wide range of phenomena. At one end of the spectrum is skill refinement; at the other end is knowledge acquisition.

   What is knowledge acquisition? In Computer Science, we note different meanings (levels). "When we say that someone learned physics, we mean that this person acquired significant concepts of physics, understood their meaning, and understood their relationship to each other and the physical world. The essence of learning in this case is the acquisition of new knowledge, including descriptions and models of physical systems and their behaviors, incorporating a variety of representations - from simple intuitive mental models, examples and images, to completely tested mathematical equations and physics laws. A person is said to have learned more if his knowledge explains a broader scope of situations, is more accurate, and is better able to predict the behavior of the physical world.This form of learning is ... generally termed knowledge acquisition ... defined as learning new symbolic information coupled with the ability to apply that information in an effective way.

   A second kind of learning is the gradual improvement of motor and cognitive skills through practice, such as learning to ride a bicycle or to play the piano. Acquiring textbook knowledge on how to perform these activities represents only the initial phase in developing the requisite skills. The bulk of the learning process consists of refining the learned skills, whether mental or motor coordination, by repeated practice and by correcting deviations from desired behavior. This form of learning, often called skill refinement, differs in many ways from knowledge acquisition. Whereas the essence of knowledge acquisition may be a conscious process whose result is the creation of new symbolic knowledge structures and mental models, skill refinement occurs at a subconscious level by virtue of repeated practice.[Carbonell et al, 1983]"

   Note:intellectual endeavors favor the former, motor coordination tasks favor the latter

   * skill refinement comes closer to non-symbolic processes
   (neural nets and genetic algorithms)

   AI programs draw heavily on knowledge as their source of power. Generally, knowledge is acquired through experience.

(i.e., a taxonomy of learning strategies):

1. Rote learning & direct implanting of new knowledge:

   most basic database systems can be said to "learn" in this sense

   *learning by being programmed, constructed or modified by an external entity - requiring no effort on the part of the learner

   *learning by memorization of given facts and data with no inferences drawn from the incoming information Samuel's checkers program used rote learning (minimax search algorithm) and parameter adjustment (generalizing from its own experience) Capabilities needed:

   • *organized storage of knowledge
   • *generalization (signature tables) (page 450 Rich)
2. Learning from instruction: learning by being told (taking advice)

   (e.g., textbook, teachers) Learner is required to do some inference, but a large fraction of the burden is on the teacher, who must present and organize the knowledge in a way that incrementally augments the student's existing knowledge The ability to operationalize knowledge -- an important component in explanation-based learning

3. Learning by analogy: Acquiring new facts or skills by transforming and augmenting existing knowledge that bears strong similarity to the desired new concept or skill into a form effectively useful in the new situation SBL (compare SBL and EBL on day3) (Kodratoff, page 2)

4. Learning from example:
   Inductive Learning

   Concept acquisition Given a set of examples and counterexamples of a concept, the learner induces a general concept description that describes all the positive examples and none of the counterexamples. (alternatively said)

   Classification is the process of assigning, to a particular input, the name of a class to which it belongs. The classes to which the classification procedure can choose can be described in a variety of ways:

   • Isolate a set of features that are relevant to the task domain. Define each class by a weighted sum of values of these features...thus each class is defined by a scoring function such as c1t1 + c2t2 + c3t3 + ... where each t corresponds to a value of a relevant parameter, and each c represents the weight to be attached to the corresponding t. (efficient) (e.g. weather (Rich 458))
   • Isolate a set of features that are relevant to the task domain. Define each class as a structure composed of those features (flexible and extendable)

     (e.g. animals (Rich 458))

   Either way, not easy to construct these class definitions.

   Want a system to be able to produce a classification program that can evolve its own class definitions.

   This task of constructing class definitions is called concept learning, or induction.

   Techniques of concept learning from example: coefficient adjustment [Samuel, 1963] -- Credit assignment problem Winston's structural concept learning program [Winston, 1975] Version Spaces [Mitchell, 1977, 1978] Decision Trees [Quinlan, 1986]

5. Learning from observation and discovery:

   Inductive Learning:

   • Inductive inference attempts to derive a complete and correct description of a given phenomena from specific observations of the phenomenon or of parts of it.

   • Two major kinds of inductive learning: Learning from examples (above) and learning from observation. (below)

     (We will consider distinctions between these in the next session)

   Common terms:
   • Unsupervised learning
   • Descriptive generalization
   • Theory formation, scientific discovery
   When something is learned, what changes?

   For machine learning, knowledge structures are changed...

   rules of behavior, descriptions of objects, problem-solving heuristics, classification taxonomies, etc. How this knowledge is acquired will depend on how it is represented. How it is represented depends on the phsychological model on which it is based.

Knowledge Structures/ Psychological models

• Numeric

  parameters in algebraic expressions

  neural nets - adjust weights

• Decision Trees

  decision trees can discriminate among classes of objects

  nodes correspond to attributes; leaves are objects

  Quinlan

• Formal Grammars

  language recognition

  Context-free grammars, transformation rules

  Chomsky

• Production rules

  condition-action pair

  Rule-based systems

  Post

• Formal logic-based expressions and

  related formalisms

  propositions, predicates

  probability theory

  neat vs scruffy (Marr?)

• Graphs and Networks

  semantic nets

  Augmented Transistion Networks (ATN's)

• Frames and Schemas

  collections of labeled entities - slots

  scripts

• Computer programs

  learn for efficiency ... or reason about internal structure

• Taxonomies

  hierarchies

• Multiple representations

  Interactions (e.g., levels of abstraction)