clarke@csri.toronto.edu (Jim Clarke) (03/23/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
(WB = Wallberg Building, 184 College Street)
SUMMARY:
NUMERICAL ANALYSIS SEMINAR, Tuesday, March 29, 10 am, WB242 -- Y.S. Wong:
"Large Matrix Computations on a Vector Computer"
COLLOQUIUM, Tuesday, March 29, 11 am, SF1105 -- Sue Whitesides:
"Geometric Motion Planning"
A.I. SEMINAR, Tuesday, March 29, 2 pm, SF1105 -- Eduard Hovy:
"Planning Coherent Multisentential Text"
A.I. SEMINAR, Thursday, March 31, 11 am, SF1101 -- Richard Szeliski:
"Bayesian Modelling Of Uncertainty in Early Vision"
A.I. SEMINAR, Thursday, March 31, 2 pm, GB304 -- Jim Delgrande:
"A Semantic Basis for Explicit Belief"
THEORY SEMINAR, Thursday, March 31, 3 pm, GB244 -- Mark Goldberg:
"Constructing a Maximal Independent Set in Parallel"
---------------
NUMERICAL ANALYSIS SEMINAR, Tuesday, March 29, 10 am, WB242
Dr. Y.S. Wong
University of Alberta
"Large Matrix Computations on a Vector Computer"
COLLOQUIUM, Tuesday, March 29, 11 am, SF1105
Professor Sue Whitesides
McGill University
"Geometric Motion Planning"
This talk will survey several algorithmic strategies and complexity results
for "mover's problems". These problems take the following general form:
An object positioned in an environment cluttered with obstacles is to be
moved in a collision-avoiding way to some specified new position. A com-
plete description of the environment is assumed known.
A.I. SEMINAR, Tuesday, March 29, 2 pm, SF1105
Dr. Eduard Hovy
University of Southern California
"Planning Coherent Multisentential Text"
Generating multisentential text is hard. Though most text generators are
capable of simply stringing together more than one sentence, they cannot
determine coherent order. Very few programs attempt to plan out the struc-
ture of multisentential paragraphs.
Clearly, the key notion is coherence. The reason some paragraphs are
coherent is that the information in successive sentences follows some pat-
tern of inference or of knowledge with which the hearer is familiar, so
that the hearer is able to relate each part to the whole. To signal such
inferences, people usually link successive blocks of text in one of a fixed
set of ways. The inferential nature of such linkage was noted by Hobbs in
1978. In 1982, McKeown built schemas (scripts) for constructing some para-
graphs with stereotypical structure. Around the same time, after a wide-
ranging linguistic study, Mann proposed a relatively small number of inter-
sentential relations that suffice to bind together coherently most of the
things people tend to speak about.
The talk will describe a prototype text structurer that is based on the
inferential ideas of Hobbs, uses Mann's relations, and is more general than
the schema applier built by McKeown. The structurer takes the form of a
standard hierarchical expansion planner, in which the relations act as
plans and their constraints on relation fillers (represented in a formalism
similar to Cohen and Levesque's work) as subgoals in the expansion. The
structurer is conceived as part of a general text planner, but currently
functions on its own. It is being tested in two domains: database output
and expert system explanantion.
A.I. SEMINAR, Thursday, March 31, 11 am, SF1101
Mr. Richard Szeliski
Carnegie Mellon University
"Bayesian Modelling Of Uncertainty in Early Vision"
Many of the problems in early vision, such as stereo, motion, shape from
shading and surface interpolation, have recently been formalized using
variational calculus, regularization and Markov Random Fields. These tech-
niques result in well defined computational problems and lead to algo-
rithms that can incorporate sparse or noisy data from a variety of sensors.
The focus to date has been on finding algorithms that yield single
optimal estimates, without considering the resulting uncertainty in
these estimates. The work in my thesis starts by interpreting
the smoothness constraints used in regularization as defining a pro-
babilistic prior model. This allows us to compute the uncertainty in the
posterior estimate, and to model probability distributions over dense
fields (such as depth maps) in a succinct fashion. The uncertainty
can be used directly in applications such as robot navigation. The
estimate thus obtained can also be combined with new measurements
to yield an improved estimate whose uncertainty is reduced over time.
This approach, which is an extension of the Kalman filter to two-
dimensional depth maps, has been used to design an incremental
(on-line) depth-from-motion algorithm. Our results show that this incre-
mental algorithm performs as well as wide-baseline stereo, and is simpler
to implement.
A.I. SEMINAR, Thursday, March 31, 2 pm, GB304
Professor Jim Delgrande
Simon Fraser University
"A Semantic Basis for Explicit Belief"
A general framework for the investigation of logical systems of belief that
are both tractable and semantically well-motivated is presented. The
approach extends standard possible worlds semantics in two ways. First,
partial possible worlds, or situations, are employed. Second, the set of
situations used to determine the truth of an explicit belief, B alpha, at a
situation depends in part on the proposition expressed by alpha. It is
argued that the approach is provides a uniform semantics from which systems
may be constructed, contrasted, and compared. Proofs of soundness and com-
pleteness are given directly in terms of this semantics and not, as is the
case with previous work, by appealing to similar results in relevance
logic. Thus the formal results also provide a connection between the
semantic theory of possible worlds and that of relevance logic.
Given this framework, we propose a specific system, BRPK, as a "preferred"
model of explicit belief. This system arguably retains a strong intuitive
basis, while avoiding the (perceived) pitfalls of earlier systems. More-
over it is tractable and permits iterated modalities.
THEORY SEMINAR, Thursday, March 31, 3 pm, GB244
Professor Mark Goldberg
Rensselaer Polytechnic Institute
"Constructing a Maximal Independent Set in Parallel"
The problem of constructing in parallel a maximal independent set of a
given graph is considered. A new deterministic NC-algorithm for the
problem is presented; it runs in O((log n)**3) time on a EREW PRAM
with a linear number of processors. This improves by a factor of log n
the running time of the previously fastest deterministic algorithm which
solves the problem using a linear number of processors.
Several open problems are discussed.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke