Fall 2010

**Class times:** TR 12:00-1:20 pm, COMP 321

**Instructor:** Vladik Kreinovich, office COMP 215, email
vladik@utep.edu, phone 747-6951

**Office hours:** TR 8:30-9 am, TR 10:30-11 am, TR 11:30-12
pm, TR 1:30-2 pm, or by appointment

**Prerequisites:**

- for graduate students: no special pre-requisites; graduate level standing is sufficient
- for undergraduate students: Statistics and Numerical Methods; some of these pre-requisites can be waived on an individual basis.

**Main objective:** to learn theoretical and applied aspects of
interval computations.

**Course description** An overview of interval computations that
take into account how input uncertainties influence the computation
result. A review of the main ideas behind interval computations,
main interval techniques, and applications to practical problems
such as robotics, computer graphics, control, and bioinformatics.

**What are interval computations?**

**Need for indirect measurements.** In many practical situations,
we are interested in the value of the quantity *y* that is
difficult or even impossible to measure directly. To estimate the
value of *y*, we:

- measure the values of all
easier-to-measure quantities
*x*, ...,_{1}*x*which are related to_{n}*y*by a known dependence*y = f(x*, and then_{1},...,x_{n}) - use the measured values
*X*of these quantities to compute the estimate_{i}*Y = f(X*for the desired quantity_{1},...,X_{n})*y*.

**Problem: measurements are never 100% exact.** The problem is
that measurements are never 100% exact. For example, a person is not
exactly 5 feet 7 inches or 170 pounds, the actual height or weight
are slightly different. because of the difference *d _{i}
= X_{i} - x_{i}
=/= 0* between measured value

Traditionally, computers simply return a number *Y* without
specifying how accurate is this number, i.e., how big the inaccuracy
*d = Y - y* can be. From the practical viewpoint, however, it
is important to know this accuracy. For example, in geophysical
applications, if we estimated the amount of oil in a field as 100
million ton, then if it is 100 +- 10, this is good news, we should
start exploiting this area; however, if it is 100 +- 200, then maybe
there is no oil at all, so it would be better to perform additional
measurements before investing into this area.

**Traditional approach assumes that we know probabilities.**
Traditional engineering approach to this uncertainty (the one that
students learn, e.g., in engineering labs) assumes that we know the
probabilities of different values of measurement error *d _{i}*.
Usually, it is assumed that there errors are independent and
normally distributed.

**In practice, sometimes, we do not know these probabilities.**
In many practical situations, we only know the upper bounds
*D _{i}* on the measurement errors:

This means that after we measure the value as *X _{i}*, the actual
value of the measured quantity can be anywhere within the interval

For example, if a thermometer shows 86 F, and its accuracy is half a degree, it does not mean that the temperature is exactly 86.000: it could be anywhere between 85.5 and 86.5.

For a single measurement result, this inaccuracy is easy to handle. However, when we process thousands of data points, these inaccuracies add up.

**Main problem of interval computations**. When the only thing we
know about each input *x _{i}* is the interval

**Where are interval computations used?** They started with the
Department of Defense trying to make sure that the intercontinental
missiles fall within the desired range. They continued with NASA
designing a trajectory which is guaranteed to hit the Moon.

Nowadays, they are used everywhere: in manufacturing, in robotics, in geoinformatics (processing geophysical data), in bioinformatics (processing bioinformatics data), in economics, in computer graphics, in computer security and privacy (where intervals are introduced on purpose, to avoid disclosing exact values).

**Why study interval techniques now.** On March 18-20, 2011,
one of the major international conferences on fuzzy techniques,
an annual conference organized by the North American Fuzzy
Information Processing Society, will be held in El Paso. This
conference is usually sponsored by IEEE, as a result of which
Proceedings of this conference become part of the widely
used IEEE IExplore publications database. This is an excellent
opportunity to present our results. This conference usually
has a strong interval-related section.

We expect that many students taking this class will not only learn the new material, they will also participate in ongoing research projects -- and several of these projects will eventually hopefully lead to co-authorship of papers published in the proceedings of this conference. The plan is that graduate students who are already working in these directions will lead groups of interested students from the class who volunteer to help with their projects.

**Non-CS students.** Due to the inter-disciplinary character of
potential applications, we welcome not only CS students, but
also students from geosciences, environmental sciences,
computational sciences, and from other disciplines
in which fuzzy techniques can be (and are) useful such as
bioinformatics, engineering (especially control), etc. The presence
of such students will help application problems.

We realize that some non-CS students may not be as good in programming different fuzzy-related algorithms as our own CS students. With this in mind, we plan to tailor homeworks and other assignments to such students, so that these tailored assignments are more focused on applications and somewhat less on programming.

**What will be in the course**

- Formulation of the main problem.
- General (software) methods of solving this problem. In
general, the problem of finding the range
*[y]*is NP-hard (intractable), and therefore, we can expect only estimates for*Y*. For each estimation method, we will describe the requited computation time, the possibility of parallelization, etc. - A brief survey of applications.

**Project.** After learning the basic interval techniques,
students will start working on an (individual or group) project.
Ideally, a project should be related to the main topic of student
research (we can help with that) and help the student in working on
his or her dissertation, thesis, or project.

For those who have not yet selected a topic, or who are interested in making interval computations their research topic, there are many interesting open research problems in which they can help.

**Additional possibility: transforming your class project into a
research publication.** In September 2008, a major international
biannual conference on interval computations will come to El Paso,
Texas. With extra work, an interesting class project can become a
good paper to submit and present at this conference.

Several students succeeded in having their papers accepted a few years ago. We will be glad to help if you are interested in this option.

**Learning Outcomes**

1. **Knowledge and Comprehension**

a. Understand why data processing and imprecise measurements are needed in practice

b. Understand the main practical problem solved by interval computations: estimating uncertainty of the results of data processing and imprecise measurements

c. Understand the main ideas behind the statistical approach to the problem of estimating uncertainty of the results of data processing - the approach which is mainly used in science and engineering

d. Understand why in many practical situations, it is impossible to use the traditional statistical approach

e. Explain why in many practical situations in which traditional statistical methods are not applicable, we need to estimate the range of a function on given intervals

f. Know linearization techniques for range estimation; understand the limitations of such techniques; know practical problems where approximate methods such as linearization are not sufficient

g. Know calculus-based techniques for solving the problem of range estimation; understand why these techniques are not always sufficient

h. Know the formulas for interval arithmetic - estimating ranges for arithmetic operations

i. Understand the main idea behind straightforward interval computations: parsing the function and replacing each elementary operation with the corresponding operation of interval arithmetic

j. Understand how to take round-off errors into account when performing interval computations

k. Understand the drawbacks of straightforward interval computations

l. Understand the main ideas behind improved interval computations: bisection, centered form, constraint propagation techniques, generalized (affine) interval computations; understand the advantages and disadvantages of these ideas

m. Know other problems solved by interval computations techniques, such as solving systems of equations and optimization under uncertainty; understand the practical need for these problems, how they are solved now, and how interval techniques help

n. Understand how interval techniques can be parallelized

o. Understand the computational complexity of the main problem of interval computations (it is NP-hard)

p. Know applications of interval computations to practical problems, e.g., to robotics, computer graphics, control, and bioinformatics

q. Be familiar with the practical need to combine interval uncertainty with probabilistic and expert uncertainty, and have a general understanding of how this combination can be done

2. **Application and Analysis**

a. Apply calculus-based techniques to estimate ranges of simple functions

b. Parse a given function

c. Apply straightforward interval computations to estimate the range of a given function

d. Apply advanced state-of-the-art interval computation techniques to produce a better estimate for the range of a given function

e. Apply traditional techniques to other practically useful problems such as solving systems of equations and optimization

f. Apply interval techniques to other practically useful problems such as solving systems of equations and optimization

3. **Synthesis and Evaluation**

a. Derive formulas for interval arithmetic

b. Design programs which use traditional and interval techniques to solve reasonable size problems

c. Apply interval techniques to solve a practice-oriented problem (ideally related to the student's area of research): from extracting an appropriate sub-problem from the general problem to selecting the most appropriate interval techniques to actually using these techniques

**Textbook:** R. E. Moore, R. B. Kearfott, and M. J. Cloud,
Introduction to Interval Analysis, Society for Industrial and
Applied Mathematics, Philadelphia,
Pennsylvania, 2009.

**Additional source of information:** Interval computations
webpage http://www.cs.utep.edu/interval-comp
(by the way, hosted by UTEP).

**Tests and grades:** There will be two tests and one final exam.
Each topic means home assignments (mainly on the sheets of paper,
but some on the real computer). Some of them may be graded. Maximum
number of points:

- first test: 10
- second test: 25
- home assignments: 10
- final exam: 35
- project: 20

A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the test and on the homeworks. In general, up to 80 points come from tests and home assignments. So:

- to get an A, you must gain, on all the tests and home assignments, at least 90% of the possible amount of points (i.e., at least 72), and also at least 90 points overall;
- to get a B, you must gain, on all the tests and home assignments, at least 80% of the possible amount of points (i.e., at least 64), and also at least 80 points overall;
- to get a C, you must gain, on all the tests and home assignments, at least 70% of the possible amount of points (i.e., at least 56), and also at least 70 points overall.

**Standards of conduct:** Students are expected to conduct
themselves in a professional and courteous manner, as prescribed by
the Standards of Conduct. Students may discuss programming exercises
in a general way with other students, but the solutions must be done
independently. Similarly, groups may discuss project assignments
with other groups, but the solutions must be done by the group
itself. Graded work should be unmistakably your own. You may not
transcribe or copy a solution taken from another person, book, or
other source, e.g., a web page). Professors are required to - and
will - report academic dishonesty and any other violation of the
Standards of Conduct to the Dean of Students.

**Disabilities:**

If you feel you may have a disability that requires
accommodation, contact the Disabled Student Services Office at 747-5148, go
to Room 106 E. Union, or e-mail to
dss@utep.edu.