Browse Prior Art Database

The Most Informative N-Split

IP.com Disclosure Number: IPCOM000102672D
Original Publication Date: 1990-Dec-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 1 page(s) / 48K

Publishing Venue

IBM

Related People

Kanevsky, D: AUTHOR [+3]

Abstract

Described is an algorithm for finding the most informative n - way questions (or equivalently - the most informative n - split of a finite measurement space) in a two-class problem. The search through all possible cases would require consideration of nm subsets of the measurement space, where m is the number of elements in the measurement space. Our method requires to consider only possibilities. find the S that minimizes the expression E(S).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 83% of the total text.

The Most Informative N-Split

       Described is an algorithm for finding the most
informative n - way questions (or equivalently - the most informative
n - split of a finite measurement space) in a two-class problem. The
search through all possible cases would require consideration of nm
subsets of the measurement space, where m is the number of elements
in the measurement space.  Our method requires to consider only
possibilities. find the S that minimizes the expression E(S).

      The BFOS algorithm (1) provides a fast way for finding two best
informative questions in a two-class problem.  This algorithm is used
to find two suboptimal questions in general classification problem
(2).  In particular to find n questions in a two-class problem a set
of binary question usually constructed (to form a binary tree) in
this search. It is possible to give examples showing that
approximation of m questions by a set of binary questions leads to
the loss of information and generates an inadequate questions tree.
In this invention we give the comparatively fast method for finding
the best n questions.

      Without loss of generality we can assume that pij's are all
different, not equal to zero and n & m.  Let us order these
quantities:  Pi1l & Pi2l & ... & Piml .  This sequence gives us the
tuple of numbers(i1, i2, ..., im).  Now, n subsets Si that provide
the most informative split of X can be found among the following
subsets:

      References
(1)  L. B...