Browse Prior Art Database

MEASURING UNCERTAINTY WITHOUT A NORM

IP.com Disclosure Number: IPCOM000148187D
Original Publication Date: 1982-Nov-30
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Werschulz, Arthur G.: AUTHOR [+2]

Abstract

Division of Science and Mathematics

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 28% of the total text.

Page 1 of 14

$EASURING UNCERTAINTY WITHOUT A NORM

by

Arthur G. Werschulz

Division of Science and Mathematics

Fordham University/College at Lincoln Center
New York, N.Y. 10023
and

Department of Computer Science
Columbia University

New Y o r k , N.Y. 10027

November, 1982

This research was su2ported in part by the ~ational

Foundation under Grant MCS-8203271.

Science

d

[This page contains 1 picture or other non-text object]

Page 2 of 14

-

Abstract

Traub, Wasilkowski, and ~oiniakowski
have shown hew un-

certainty can be defined and analyzed withcut a norm or metric.
Thier theory is based on two natural and non-restrictive axioms.
we show that
these axioms induce a family of pseudometrics, and that

balls of radius E, are (roughly) the E-approximations to the
solution. In addition, we show that a family of pseudometrics is
necessary, even for the problem of computing x such that (f(x)

1 ( 5 ,

where f is a real function.

[This page contains 1 picture or other non-text object]

Page 3 of 14

    In two recent monographs ([31,[41), Traub and his colleagues
have studied the optimal solution of problems which are solved approximately, that is, where there is uncertainty in the answer. In [ 4 ] , uncertainty was measured by a norm. For some problems, this is not an appropriate or natural assumption. Therefore, in [ 3 ] it is shown how uncertainty can be introduced via two natural and non-restrictive axioms.

    In a private communication, Trauf:) asked about the strength of
these axioms. That is, do the axioms generate any interesting structures? In Section 2 of this paper, we show that these axioms induce a family of pseudometrics. Moreover, we show that the balls of radius E generated by this family of pseudornetrics are (roughly
speaking) the E-approximations to the solution.

    Is a family of pseudometrics necessary? We give an affirmative answer in Section 3, using the problem of computing x such that
M(x)

1 ( 5 , where f is a real functi-on.

[This page contains 1 picture or other non-text object]

Page 4 of 14

We first recall the definition of a solution operator from [ 3 ] .

Let F and G be sets, and let 2G denote the power set of G,
i. e. , the class of all subsets of G. Let IR* denote the non- I

negative real numbers. If S : F x IR

-

                                   2G is an operator such
that 1

(2.1)

and

( 2 . 2 ) V f 6 F, v ElrE2 EIR' with El -

< €2, S ( f r ~ ~ )

5 S(fr~~)t

then S is said to be a solution operator, and S (f, e) is said to
be the set of E-approximations to the (exact) solution S (f,O) .

Note that S(f,e) is a set. This formulation allows the exact 1

solution S(f,O) to be a set, i.e., a problem may have multiple I

solutions. In addition, S(f,g) a set means that we are willing
to accept any element of S(f,€) as an =-approximation. These
axioms are very natural: the first says that every problem has a

solution, while the second says that increasing the uncertainty
cannot...