Automatically finding linear functions that make evaluations and recognize patterns

Abstract

This semitutorial paper presents some new material by the author and some well-known material. A linear evaluation function is a function of the form CY where Y is a feature vector and where C is a coefficient (weight) vector. The author calls the following important problem the m,n-evaluation problem. Given a set { is preferred to Y ₁} of m preferences in n-space, find a coefficient vector C such that, for as many preferences as possible,. This problem is important because a subject may be either unable or unwilling to divulge his evaluation function but may supply preferences, either implicitly by his behavior or explicitly. Finding an evaluation function may be applied to utility theory, automatic extracting, game playing, international relations, purchasing and selling, and the evaluation of personnel and computer programs

The m, (n–1)-pattem problem consists of finding a hyperplane in (n–1)-space which approximately separates m pattern sample instances into two pattern classes. Once found, a linear function that makes evaluations or recognizes patterns may be used for various purposes. Notably, a computer program may use the function to approximate the function used by a particular individual or consensus of experts. By finding a function which approximates the function used by an expert (or experts), the program may be said to learn. The author defines the m, n-half-space problem and proves that every m, n-evaluation problem and every m, (n – 1)-pattern problem can be transformed into an m, n-half-space problem. Eight procedures are presented that attempt to find a good C for the m, n-half-space problem. When an error-free C exists, the relaxation procedure will find such a C. When n is two the gain-loss procedure is practical for finding an optimal C even when m is large.