Browse Prior Art Database

# Optimal L-Split in a Multiclass Problem Based On a Degenerate Concave Function

IP.com Disclosure Number: IPCOM000101020D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 59K

IBM

## Related People

Kanevsky, D: AUTHOR [+4]

## Abstract

We give the polynomial (in m) algorithm for finding the optimal l-split of a finite measurement space of m elements in a n-class problem. The optimality criterion for this split is provided by a weighted sum of degenerate concave functions. The notation and statement of problem (Image Omitted)

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

Optimal L-Split in a Multiclass Problem Based On a Degenerate Concave Function

We give the polynomial (in m) algorithm for finding the
optimal l-split of a finite measurement space of m elements in a
n-class problem.  The optimality criterion for this split is provided
by a weighted sum of degenerate concave functions.
The notation and statement of problem

(Image Omitted)

Let X = {1,2,...,m}, Y = {1,2...,n} Let (X,Y) be a random
variable, X e X, Y e Y and let Pij = Prob(X = i,Y =
j).  Let S = {S1, S2,...,S1} be a l-split of X i.e.    Si = X,
Si Sj is empty if i * j.  Let P = [pij] be the m
v n matrix.  Let r(p1,p2,...,pk) = min(p1,p2 ...,pk). l Let finally,
E(S) = S Prob(Si)r(pi) where i=1 pi = (Prob(Y = 1¯X e Si),..,Prob(Y =
n¯X e Si).  The problem is to find the S that minimizes the
expression E(S).

In (1,2) polynomial in m algorithms for finding l-way best or
near best questions in a two-class problem are given.  But no fast
algorithm is known for a multi-class problem, that is the case of
primary interest in Speech Recognition applications.  The total
search through all possibilities would require the exponential in m
algorithm. In this invention we provide a polynomial in m algorithm
for special case of the objective function E(S) that is given in
notation.  From random sampling and theoretical studying of some
special matrices it was observed that a l-split provided b...