I am a Professor at the
Department of Computer Science and
Engineering of the
University of South Carolina.
Find here my Curriculum Vitae
in pdf and in postscript.
Find here an NSF-style biosketch in MS-Word format.
My Erdos number is 3. (Paul Erdos coauthored a paper with R. Daniel Mauldin,
who coauthored a paper with Donald Loveland, who coauthored a paper with me.)
Department of Computer Science and Engineering
Swearingen Engineering Center
University of South Carolina
Columbia, SC 29208
mgv@cse.sc.edu
Phone: +1 (803) 777-4641;
Fax: +1 (803) 777-3767;
Office: 3A55
Education
Laurea: Electrical Engineering, Politecnico di Milano, 1980
MA: Computer Science, Duke University, 1983
PhD: Computer Science, Duke University, 1987
Spring 2010 Courses
CSCE 190 (Computing in the Modern
World)
CSCE 390 (Professional Issues in Computer
Science and Engineering)
CSCE 531 (Compiler Construction)
Fall 2009 Courses
CSCE 580 (Artificial Intelligence)
CSCE 330 (Programming Language
Structures)
Spring 2009 Courses
CSCE 211 (Digital Logic Design)
CSCE 582 (Bayesian Networks and
Decision Graphs)
CSCE 582
(Bayesian Networks and Decision Graphs): MS-Word flyer
CSCE 582
(Bayesian Networks and Decision Graphs): announcement
Fall 2008 Courses
CSCE 580 (Artificial Intelligence)
Spring 2008 Courses
CSCE 531 (Compiler Construction)
Spring 2008 Bayesian Networks Reading Club
Bayesian Network Reading Club Information
Fall 2007 Courses
CSCE 330 (Programming Language
Structures)
Spring 2007 Courses
CSCE 531 (Compiler Construction)
Fall 2006 Courses
CSCE 330 (Programming Language Structures)
Fall 2006 Seminar on the integration of logical and probabilistic
reasoning
Seminar Information
Spring 2006 Courses
CSCE 330 (Programming Language Structures)
CSCE 582 (Bayesian Networks and Decision
Graphs)
Fall 2005 Courses
CSCE 330 (Programming Language Structures)
Spring 2005 Courses
CSCE 330 (Programming Language Structures)
CSCE 350 (Data Structures and
Algorithms)
Fall 2004 Bayesian Networks Reading Club
Bayesian Network Reading Club Information
Fall 2004 Courses
CSCE 330 (Programming Language Structures)
Spring 2004 Courses
CSCE 330 (Programming Language Structures)
CSCE 350 (Data Structures and
Algorithms)
Fall 2003 Courses
CSCE 330 (Programming Language Structures)
CSCE 582 (Bayesian Networks and Decision
Graphs)
Spring 2003 Courses
CSCE 330 (Programming Language Structures)
CSCE 580 (Artificial Intelligence)
Fall 2002 Courses
CSCE 330 (Programming Language Structures)
CSCE 582 (Bayesian Networks and Decision
Graphs)
Spring 2002 Courses
CSCE 580 (Artificial Intelligence)
CSCE 531 (Compiler Construction)
Fall 2001 Courses
CSCE 531 (Compiler Construction)
(Link to Spring 2002 edition!)
Spring 2001 Courses
CSCE 146 (Introduction to Algorithmic
Programming II)
CSCE 768 (Pattern Recognition and Classification)
Fall 2000 Courses
CSCE 330 (Programming Language Structures)
(E-mail if interested in course materials.)
CSCE 330 (Programming Language Structures)
CSCE 590 (Foundations of Bayesian Networks)
Fall 1999 and Spring 2000
During the Academic Year 1999-2000, I was on sabbatical. I spent October
1999, March 2000, and parts of May and June 2000
at the Department of Computer Science at
the University of Aalborg, as a guest of the Decision Support Systems Unit.
Notes on three lectures on data
mining
Spring 1999 Courses
CSCI 330 (Programming Language Structures)
(E-mail if interested in course materials.)
Fall 1998 Courses
CSCI 220 (Data Structures and
Algorithms)
CSCI 509 (Foundations of Bayesian Networks)
Spring 1998 Courses
CSCI 786 (Knowledge-Based Systems)
Fall 1997 Courses
CSCI 146 (Introduction to Algorithmic Design
II)
Spring 1997 Courses
CSCI 330 (Programming Language Structures)
Research Interests:
Knowledge-based systems
Evidential reasoning
Heuristics
Computational complexity
Honors
- Lilly Teaching Fellow, Academic Year 1993-94
- Advisor of the Year, College of Science and Mathematics, University of
South Carolina, 1997
Current Research Projects
Combining Facts and Expert Opinion in Analytical Models via Logical and
Probabilistic Reasoning
Marco Valtorta is project manager and co-PI; Mike Huhns is co-PI. HNC/Fair
Isaac (San Diego, California) is a subcontractor (John Byrnes, co-PI).
BALER (Bayesian And Logical Engine for Reasoning) combines facts and expert
opinion in analytical models via logical and probabilistic reasoning. It
supports the optimal management of uncertainty, inconsistency and disagreement
in collaborative intelligence analysis. BALER's strategy is to leverage the
complementary strengths of artificial intelligence techniques rooted in logic,
probability, and statistics that have heretofore remained disparate both in
theory and in practice, in order to build tools that operate robustly and
efficiently on large, noisy input from knowledge bases, partial network
constructions, and various evidence sources including unstructured data. BALER
will provide quantification of uncertainty, proper treatment of dependent and
independent sources of information, meaningful reasoning over inconsistent
information, and prioritization of new data reporting based on relevance. BALER
will support collaboration by highlighting areas of agreement and disagreement,
and evidence and assumptions that contribute to disagreement.
This work is funded by the Disruptive Technology Office Collaboration
and Analyst System Effectiveness (CASE) Program, contract FA8750-06-
C-0194 issued by Air Force Research Laboratory (AFRL). The views and
conclusions are those of the authors, not of the US Government or its agencies.
Recent Research Projects
Prior and Tacit Knowledge System for Novel Intelligence from Massive
Data
Mike Huhns and Marco Valtorta, co-PIs for the University of South Carolina
subcontractor. Other partners in the first phase (December 2002-August 2004)
were:
Global Info Tek (John Cheng and Ray Emami),
KRM, Inc (Larry Kerschberg), University of Connecticut (Gene Santos, Jr. and
Qunhua Zhao). Sponsored by ARDA. First phase: December 2002-August 2004.
OmniSeer supports intelligence analysts in the handling of massive amounts of
data, the construction of scenarios, and the management of hypotheses. OmniSeer
models analysts with dynamic user models that capture an analyst's context,
interests, and preferences, thus enabling more efficient and effective
information retrieval. OmniSeer explicitly represents the prior and tacit
knowledge of analysts, thus enabling transfer and reuse of such knowledge. Both
the user and cognitive models employ a Bayesian network fragment
representation, which supports principled probabilistic reasoning and analysis.
An independent evaluation of OmniSeer was carried out at NIST in May 2004
and will be used to guide further development.
A second phase started in August 2004 and lasted approximately two years.
The partner (prime) in the second
phase was Georgia Tech Research Institute (Bob Simpson and Betty Whitaker).
USC and SPAWAR (Charleston) cooperation for the SPAWAR Critical
Infrastructure Protection Center (CIPC)
Joe Johnson (Physics Department), PI; Marco Valtorta, co-PI.
May 2004-September 2004.
As part of this collaboration, USC delivered (1) a geographical
information system model of several critical infrastructures, and (2) a model
of the interdependency of critical infrastructure.
TargetShare: Autonomous Negotiating Teams
Mike Huhns, Project Director, Marco Valtorta, Juan Vargas, Jose Vidal,
co-PIs. Sponsored by DARPA.
Click
here for further information
on this
DARPA-sponsored project.
Dynamic Decision Support for Command, Control, and Communication in the
Context of Tactical Defense
Advances in communication and sensor technologies have brought about huge
increases in the types and amounts of information available for battle
management.
Shortcomings in the ability to integrate and arbitrate missing and conflicting
information and the current inability to correlate and reason about vast
amounts of
information in real time are an impediment to providing a coherent overview of
unfolding events. Integrating disparate information, such as voice, video
images,
and tactical displays, that has varying degrees of reliability is a first step
towards
battle management. Such integration can be accomplished through the application
and further development of Bayesian network and intelligent agent methods.
Bayesian networks provide a sound basis for a robust and potentially very
efficient
solution to the problems posed by incomplete/unreliable data and have proven
suitable to the problem of integrating disparate types of data. Other aspects
of
managing different types of data can be addressed through intelligent agents.
Click
here for further information
on this
ONR-sponsored project and on the Decision Analysis Group (DAG), which is
jointly led with
Professor John Rose.
Click
here for a picture of DAG members, taken on June 14,
2000. Standing, from
left to right, are Young-Gyun Kim, Marco Valtorta, Billy Turkett, and John
Rose; sitting, from left to right, are Miguel Barrientos, Clif Presser, and
Wayne Smith. All, except Billy, either have been or were members of the
DAG group from its inception.
Click
here and
here
for other pictures of DAG members.
Analysis of Agricultural Loan Defaults: Development of Credit/Loan Analysis
Models
I applied machine learning techniques to build Bayesian Networks to model
defaults in loans made to farmers.
This work, which is joint with Leszek Piatkiewicz of Pembroke State University,
and is connected to a larger project at S.C. State University,
is funded by the U.S. Department of Agriculture.
Conflicts in Diagnostic Bayesian Networks
I address the brittleness problem in diagnostic expert systems by automatically
constructing straw models from Bayesian Network Models for Diagnosis. The straw
models are normally less likely than the base model given a case to be
diagnosed. When one of the straw models becomes more likely than the base model,
the user is alerted of a possible misuse of the diagnostic expert system.
This work is joint with Young-Gyun Kim, a graduate student.
Algorithms for the Construction of Bayesian Networks
I am concerned with the efficient learning of Bayesian networks from data.
Jointly with Moninder Singh (a former graduate student at the University of South
Carolina, then at the University of Pennsylvania, and now at IBM T.J. Watson
Research Center), I designed and
implemented a hybrid algorithm
called CB, which has been used in various applications. The program was
reworked and extended by Mark Bloemeke (former graduate student, now at Rytek).
A study of the complexity of abstraction in qualitative diagnosis
I analyzed the complexity of a technique that uses simplified
models for the identification of malfunctions in physical systems,
such as conventional power plants.
This project was based on my longstanding interest in heuristic search, draws on
my four-year association with the ESPRIT QUIC project and is supported by grant
from CISE. This was joint work with Giorgio Tornielli of CISE and
Rita Childress, a graduate student. Edward Yu (graduate student)
and I have carried out some experimental work on model-based
diagnosis using constraint logic programming.
Refinement of Knowledge Bases
Knowledge-base refinement is concerned
with the improvement of performance of expert systems through the
modification of the knowledge-base they use. My dissertation is the
first attempt to apply algorithmic complexity analysis to rule-base
refinement, which has otherwise been approached only empirically.
Some extensions of this work have been carried out jointly with Dahai
Zang, a graduate student. I am studying refinement and validation
of belief networks as motivated by problems arising from the development
of MUNIN, a large knowledge-based system. I have formally defined
several problems and found them to be NP-Complete. This indicates
that automatic refinement and validation of belief networks from cases
is intractable, in both the Dempster-Shafer and the Bayesian schemes.
The relevance of these results for the practice of expert system
construction has been assessed. I intend to address the relation
of my complexity results to the PAC learning model and to a statistical
technique of David Spiegelhalter.
Parallel programs for the construction of Markov networks
Randy
Mechling, a graduate student, and I implemented and tested an
algorithm for the construction of Bayesian networks on a hypercube.
Computational, Knowledge Engineering, and Statistical Aspects of the Dempster-Shafer Theory of Evidence.
Shijie Wang (a graduate student)
and I rewrote a large knowledge-base of rules into a network
and are studying the associated computational and knowledge engineering
aspects.
Stephen Durham, Jeffrey Smolka (Statistics Department) and I
studied the statistical consistency of Dempster's rule in diagnostic
trees.
Prediction in physical systems using qualitative physics
One of
the tasks approached using qualitative reasoning is prediction. David
Hibler (a doctoral candidate with a substantial academic background in
Physics) proposed a thought experiment approach to prediction that
emphasizes the use of multiple simplified models of physical phenomena.
Studies in heuristics for A*
This research addressed the computation
of heuristics for a base problem from relaxed subproblems. It includes
work with Ishaq Zahid of the Citadel on the Knight's Tour Puzzle and
with Othar Hansson and Andy Mayer of UC Berkeley on the extension of
a result of mine on the computational complexity of heuristics for A*
Selected Publications
Uncertain Reasoning:
"Extending Polynomial Chaos to Include Interval Analysis"
(with Antonello Monti and Ferdinanda Ponci)
IEEE Transactions on Instrumentation and Measurement,
Vol.59, Number 1 (January 2010), pp.48-55.
(Click here for a local copy in pdf format.)
"On the Completeness of an Identifiability Algorithm for Semi-Markovian
Models" (with Yimin Huang)
Annals of Mathematics and Artificial Intelligence,
Vol. 54, Issue 4 (2009), pp.363-408.
(Click here for a preprint in pdf format.)
"Performance Evaluation of Algorithms for Soft Evidential Update in Bayesian
Networks: First Results" (with Scott Langevin)
Proceedings of the Second International Conference on Scalable Uncertainty
Management (SUM-08),
Naples, Italy, October 1-3, 2008, pp. 284-297.
(Proceedings edited by Sergio Greco and Thomas Lukasiewicz and published as
Lecture Notes in Artificial Intelligence vol. 5291 (LNAI 5291), Springer,
ISBN-13 978-30540-87992-3, 2008.)
(Click here for
a preprint in pdf format.)
"Identifiability in Causal Bayesian Networks: A Gentle Introduction" (with
Yimin Huang)
Cybernetics and Systems, 39, 4 (May 2008), pp.425-442.
(Click here for
a preprint in pdf format.)
(Click here for
galley proofs in pdf format.)
"Logical and Probabilistic Reasoning to Support Information Analysis in
Uncertain Domains" (with John Byrnes and Michael Huhns)
Proceedings of the Third Workshop on Combining Probabilty and Logic
(Progic-07),
Canterbury, England, September 5-7, 2007.
(Click here for
a preprint in pdf format.)
"Pearl's Calculus of Intervention is Complete" (with Yimin Huang)
Proceedings of the 22nd Conference on Uncertainty in Artificial
Intelligence (UAI-06), Cambridge, MA, July 13-16, 2006, pp.437-444.
This paper won
the Best Student Paper award, sharing it with Ilya Shpitser and Judea Pearl's
"Identification of Conditional Interventional Distributions."
(Click here for
the pdf version.)
"Identifiability in Causal Bayesian Networks: A Sound and Complete Algorithm"
(with Yimin Huang)
Proceedings of the Twenty-First National Conference on Artificial
Intelligence (AAAI-06) Boston, MA, July 16-20, 2006, pp. 1149-1154.
(Click here for
the pdf version.)
"Sequential and Parallel Algorithms for Causal Explanation with
Background Knowledge"
(with Bhaskara Reddy Moole)
International Journal of Uncertainty, Fuzziness and Knowledge-Based
Systems,
Vol. 12, Suppl. (October 2004), 101-122.
(Click here for
the pdf version of an almost final draft)
"A Prototypical System for Soft Evidential Update"
(with Young-Gyun Kim and Jiri Vomlel)
Applied Intelligence, 21, 1 (July-August 2004), 81-97, 2004.
(Click here for gzipped
postscript version of an almost final draft.)
(Click here for pdf version.)
"Causal Explanation with Background Knowledge"
(with Bhaskara Reddy Moole)
Proceedings of the First Indian International Conference on Artificial
Intelligence,
Hyderabad, India, December 18-20, 2003.
(Click here for pdf version of an almost
final draft.)
"Soft Evidential Update for Probabilistic Multiagent Systems"
(with Young-Gyun Kim and Jiri Vomlel)
International Journal of Approximate Reasoning, 29, 1 (January 2002),
71-106.
(Click here for pdf version.)
(Click here for postscript version of an almost
final draft.)
"Probability and Agents" (with Michael H. Huhns)
IEEE Internet Computing, 6, 6 (November-December 2001), 77-79.
(Click here for pdf version of an almost
final draft.)
"A Hybrid Algorithm to Compute Marginal and Joint Beliefs in Bayesian Networks
and Its Complexity" (with Mark Bloemeke)
In: G.F. Cooper and S. Moral (eds.),
Uncertainty in Artificial Intelligence: Proceedings of the Fourteenth
Conference.
San Francisco, CA: Morgan-Kaufmann, 1998, 16-23.
(Click here for postscript version.)
(Click here for pdf version.)
"On the Detection of Conflicts in Diagnostic Bayesian Networks Using
Abstraction" (with Young-Gyun Kim)
In: Ph. Besnard and S. Hanks (eds.),
Uncertainty in Artificial Intelligence: Proceedings of the Eleventh
Conference.
San Francisco, CA: Morgan-Kaufmann, 1995, 362-367.
(Click here for postscript version.)
"Refinement of Uncertain Rule Bases via Reduction" (with Charles X.F. Ling)
International Journal of Approximate Reasoning, 13, 2 (August 1995), 95-126.
(Click here for postscript version.)
"Construction of Bayesian Belief Networks from Data: a Brief Survey and an
Efficient Algorithm" (with Moninder Singh)
International Journal of Approximate Reasoning, 12, 2 (February 1995),
111-131.
(Click here for postscript version.)
"On the Complexity of Belief Network Synthesis and Refinement" (with Donald W.
Loveland)
International Journal of Approximate Reasoning, 7, 3-4 (October-November
1992), 121-148.
(Click here for postscript version without figures.)
"Statistical Consistency with Dempster's Rule on Diagnostic Trees Having
Uncertain Performance Parameters" (with Stephen D. Durham and Jeffery S.
Smolka)
International Journal of Approximate Reasoning, 6, 1 (January 1992),
67-81.
"Some results on the computational complexity of refining rule strengths"
International Journal of Approximate Reasoning, 5, 2 (March 1991), p.123-148.
(Click here for postscript version without figures.)
"A prototype belief network-based expert system shell" (with Shijie Wang)
Proceedings of the Third International Conference on Industrial and
Engineering Applications of AI and Expert Systems, 1990, pp. 509-518.
Applications of Bayesian Networks:
"Ontological Support for Bayesian Evidence Management"
(with Michael Huhns)
Proceedings of the Second International Ontology for the Intelligence Community
Conference
(OIC-2007) (CD-ROM),
Columbia, MD, November 28-29, 2007, pp.47-52.
(Click here for pdf version from the conference digital library);
(Click here for complete proceedings, edited by Kathleen Stewart Hornsby);
(Click here for local copy of the paper)
"The Effects of Data Quality on Machine Learning Algorithms" (with Valerie
Sessions)
Proceedings of the 11th International Conference on Data Quality
(ICIQ-06) pp.485-498, Cambridge, MA, November 10-12.
This paper won
the Best Academic Paper award.
(Click here for local copy of the paper)
"PAID: A Probabilistic Agent-Based Intrusion Detection System"
(with Vaibhav Gowadia and Csilla Farkas)
Computers and Security, 24, 7 (October 2005), 529-545.
(Click here for an almost final version in
pdf)
"Extending Heuer's Analysis of Competing Hypotheses Method to Support
Complex Decision Analysis"
(with Jiangbo Dang, Hrishikesh Goradia, Jingshan Huang, and Michael Huhns)
Proceedings of the 2005 International Conference on Intelligence Analysis
(IA-05) (CD-ROM),
Washington, D.C., May 2-4, 2005, 2 pages.
(Click here for pdf version from the conference digital library);
(Click here for local copy of the paper)
"Building Bayesian Network Models in Medicine: the MENTOR Experience"
(with Subramani Mani and Suzanne McDermott)
Applied Intelligence, 22, 2 (March/April 2005), pp.93-108 (in press).
(Click here for an almost final version in
gzipped postscript)
"OmniSeer: A Cognitive Framework for User Modeling, Reuse of Prior and
Tacit Knowledge, and Collaborative Knowledge Services"
(corresponding author, with John Cheng, Ray Emami, Larry Kerschberg,
Eugene Santos, Jr., Qunhua Zhao,
Nien Nguyen, Hua Wang, Michael Huhns, Jiangbo Dang, Hrishikesh Goradia,
Jingshan Huang, and Sharon XI)
Proceedings of the 38th Hawaii International Conference on System Sciences
(HICSS38) (CD-ROM),
Big Island, Hawaii, January 3-6, 2005, 10 pages.
(Click here for pdf version from the conference digital library)
(Click here for local copy of the paper)
"Agent Based Intrusion Detection with Soft Evidence"
(with Vaibhav Gowadia and Csilla Farkas)
(Click here for MSWord version.)
Proceedings of the 14th Information Resources Association (IRMA)
International Conference, Philadelphia, PA, May 18, 2003, pp. 140-143.
"Building a Bayesian Network Model of Heart Disease (Extended Abstract)"
(with Jayanta K. Ghosh)
Proceedings of the 38th Annual ACM Southeastern Conference (ACMSE00),
Clemson, SC, April 7-8, 2000, pp.239-240.
(Click here for postscript version.)
(Full version available as Technical Report TR9911,
Department of Computer Science, University of South Carolina, November 1999.)
"MENTOR: A Bayesian Model for Prediction of Mental Retardation in Newborns"
(with Subramani Mani and Suzanne McDermott)
Research in Developmental Disabilities, 18 (1997), 5, 303-318.
Heuristic Search:
"Tie-Breaking Rules for 4xn Warnsdorff's Tours" (with M. Ishaq Zahid)
Congressus Numerantium, 95 (1993), 75-86.
"Warnsdorff's Tours of a Knight" (with M. Ishaq Zahid)
Journal of Recreational Mathematics, 25 (1993), 4, 263-275.
"A New Result on the Complexity of Heuristic Estimates for the A* Algorithm"
(with Othar Hansson and Andrew Mayer)
Artificial Intelligence, 55, 1 (May 1992), 129-143.
(Click here for postscript version.)
"A result on the computational complexity of heuristic estimates for
the A* algorithm"
Information Sciences, vol. 34, 1984, p. 47-59.
Knowledge Engineering:
"Polynomial Time Model-Based Diagnosis with the Critical Set Algorithm" (with
Rita L. Childress)
Working Notes of the Fourth International Workshop on Principles of
Diagnosis (DX-93), (1993), 166-177.
(Click here for postscript version.)
"Knowledge Base Refinement: A Bibliography."
Applied Intelligence, 1, 1 (July 1991), 87-94.
"Detecting ambiguity: An example in knowledge evaluation" (with
Donald W. Loveland)
Proceedings of the 8th International Joint
Conference on Artificial Intelligence , 1983, p. 182-184 (Reprinted
in Gupta, U. (ed) Validating and Verifying Knowledge-Based Systems,
Los Alamitos, CA: IEEE Computer Society Press , 1991.
Technical Reports and Preprints
Data used in the Mentor Project
(zipped)
Some Talks
Some talks
Also see under "Miscellaneous Links" below
Some Useful Links
Departmental Colloquia
UAI Bibliography, in BibTeX format
Miscellaneous Links
Department of
Statistics Colloquia
T&P
Unit Criteria
USC Thesis LaTeX Style,
from Prof. Jose' Vidal
Some
advice for getting through graduate school, linked from the Georgia Tech
College of Computing page.
