# Weighted order statistic classifiers with large rank-order margin. Page: 3 of 9

This
**article**
is part of the collection entitled:
Office of Scientific & Technical Information Technical Reports and
was provided to Digital Library
by the UNT Libraries Government Documents Department.

#### Extracted Text

The following text was automatically extracted from the image on this page using optical character recognition software:

2. Background

2.1 Threshold Decomposition

Threshold decomposition is a useful tool for

understanding a large family of non-linear functions

(Fitch, Coyle et al. 1984). _We describe threshold

decomposition for D inputs: X =[XI, X2,..., XD],

where each input takes on values from a finite set of

2M +1 quantization levels:

X e Q_{-M,...-1,0,1,2,...,M}. The concept is

readily extended to real-valued inputs (L.Yin and Neuvo

1994), (Arce 1998). We define a threshold function as:

1, if X r (7)

T -(X) 0, if X <m rn)

Threshold decomposition of X produces a set of 2M

binary vectors [-M+1',, O,. . where

x' = T'"(X). To clarify our notation, the i' element of

Xm is =in(X). The original inputs can be exactly

recovered from this decomposition by:

M

Xi =-M + I x' (2)

m=-M+1

2.2 Stack Filters

If we define a binary function f: {0,1}D -> {0,1}

operating on each binary input vector x'", then the

function:

_ M

Sf(X)= E f(x') (3)

m=-M+1

defines a stack filter when f (z'") possesses the stacking

property. The stacking property requires

f(x"') f(x ) whenever x' S xi' for all i. A

necessary and sufficient condition for f (") to possess

the stacking property, is that, it is a Positive Boolean

Function (PBF) (Wendt, Coyle et al. 1986). PBFs are the

subset of Boolean functions that can be expressed without

complements of the input variables. Figure 1 illustrates

the stack filter architecture, and corresponding PBF for a

three input median function.

2.3 Weighted Order Statistics

If we restrict f(") within the stack filter architecture (3)

to a linearly separable PBF, the sub-class of Weighted

Order Statistics (WOS) is defined. A linearly separable

PBF can be expressed as:f(x,,...,xD)=To YWixi -R

i=1(4)

where W , R e R, W, R 0 and x, e {0,1} for all i.

We will refer to this model as a Positive weighted Binary

Perceptron (PBP). This class has an equivalent integer

domain interpretation:

Wosf(X )= R'hlargest{WOX1,W20X2,.. .WDOXD}(5)

W," t imes

where W OX = X,, X,,..., Xi . By choosing weights

W and threshold R , median, weighted median, order

statistic and the weighted order statistic function classes

can be implemented (Yli-Harja, Astola et al. 1991).

Pseudo-code for calculating a real-valued WOS can be

found in (Arce 1998). In figure 1, the PBP for a 3 input

median function has VW. =1 and R =1.5.

X, X2 X)

220 i 222 M -+ 221 1 1 2222

Threshold at 1,2 and 3 P . X '"x "' Add binary outputs

OO0000 1000-. PBF - 0OOOOOOOO

2 110o01111 .- BF- 110001111

1 1 101 1 1 111 PB X 11 1 11 111 1

Figure 1. Threshold decomposition architecture for a 3-input

median filter.

2.4 Mean Absolute Error

Stack filter optimization can be posed as a linear program

for Mean Absolute Error (MAE) loss functions (E.J.Coyle

1988). Consider the stack filter (3) with input X E QD

and desired output Y e Q :

LMAE(Sf)= E[Y-Sf(X)] (6)

where E[ }is the expected value over the joint

distribution X X Y.

LMAE(Sf)=E L (yn -f(i'")) (7)

m=-M +1

LMAE (Sf )= EL y"' -P f (z"' (8)

m=-A9+1

Equation (7) follows from the application of threshold

decomposition. By the stacking property, all nonzero

errors within the sum of (7) are the same sign leading to

(8). An intuitive interpretation of the optimization

problem was presented by Coyle (E.J.Coyle 1988): At

each level m, the function f (") observes a binary input

## Upcoming Pages

Here’s what’s next.

## Search Inside

This article can be searched. **Note: **Results may vary based on the legibility of text within the document.

## Tools / Downloads

Get a copy of this page or view the extracted text.

## Citing and Sharing

Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.

### Reference the current page of this Article.

Porter, R. B. (Reid B.); Hush, D. R. (Donald R.); Theiler, J. P. (James P.) & Gokhale, M. (Maya). Weighted order statistic classifiers with large rank-order margin., article, January 1, 2003; United States. (https://digital.library.unt.edu/ark:/67531/metadc928443/m1/3/: accessed May 20, 2019), University of North Texas Libraries, Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.