**Previous message:**masoud nikravesh: "BISC: BISC Program Announcement: NAFIPS-FLINT 2002"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*********************************************************************

Berkeley Initiative in Soft Computing (BISC)

*********************************************************************

A Prototype-Centered Approach to

Adding Deduction Capability to Search Engines -- The Concept of Protoform

BISC Seminar

Lotfi A. Zadeh

EECS-CS Division

University of California-Berkeley

Feb. 8, 2002

320 Soda Hall

4:00-5:30 p.m.

Abstract:

Existing search engines have many remarkable capabilities. But what is not among

them is the deduction capability -- the capability to answer a

query by drawing on information which resides in various parts of the knowledge

base or is augmented by the user.

Limited progress toward a realization of deduction capability is achievable

through application of methods based on bivalent logic and standard

probability theory. But to move beyond the reach of standard methods it is

necessary to change direction. In the approach which is outlined, a concept

which plays a pivotal role is that of a prototype -- a concept which has a

position of centrality in human reasoning, recognition, search and decision

processes.

Informally, a prototype may be defined as a sigma-summary, that is, a summary of

summaries. With this definition as the point of departure, a

prototypical form, or protoform, for short, is defined as an abstracted

prototype. As a simple example, the protoform of the proposition "Most

Swedes are tall" is "QA's are B's," where Q is a fuzzy quantifier, and A and B

are labels of fuzzy sets.

Abstraction has levels, just as summarization does. For example, in the case of

"Most Swedes are tall," successive abstracted forms are "Most A's

are tall," "Most A's are B's" and "QA's are B's."

At a specified level of abstraction, propositions are PF-equivalent if they have

identical protoforms. For example, propositions "Usually Robert

returns from work at about 6 pm" and "In winter, the average daily temperature

in Berkeley is usually about fifteen degrees centigrade," are

PF-equivalent. The importance of the concepts of protoform and PF-equivalence

derives in large measure from the fact that they serve as a basis for

knowledge compression.

A knowledge base is assumed to consist of a factual database, FDB, and a

deduction database, DDB. In both FDB and DDB, knowledge is assumed

to fall into two categories: (a) crisp and (b) fuzzy. Examples of crisp items of

knowledge in FDB might be: "Height of the Eiffel tower is 324m" and

"Paris is the capital of France." Examples of fuzzy items might be "Most Swedes

are tall," and "California has a temperate climate." Similarly, in

DDB, an example of a crisp rule might be "If A and B are crisp convex sets, then

their intersection is a crisp convex set." An example of a fuzzy rule

might be "If A and B are fuzzy convex sets, then their intersection is a fuzzy

convex set." A fuzzy rule may be a crisp assertion about fuzzy sets or a

fuzzy assertion about crisp sets or a fuzzy assertion about fuzzy sets.

The deduction database is assumed to consist of a logical database and a

computational database, with the rules of deduction having the structure of

protoforms. An example of a computational rule is "If Q1 A's are B's and Q2 (A

and B)'s are C's," then "Q1 Q2 A's are (B and C)'s," where Q1 and

Q2 are fuzzy quantifiers, and A, B and C are labels of fuzzy sets. The number of

rules in the computational database is assumed to be very large in

order to allow a chaining of rules that may be query-relevant.

A very simple example of deduction in the prototype-centered approach-an example

which involves string matching but no chaining -- is the

following. Suppose that a query is "How many Swedes are very tall?" A protoform

of this query is: ?Q A's are B^^2, where Q is a fuzzy quantifier

and B^^2 is assumed to represent the meaning of "very B," with the membership

function of B^^2 being the square of the membership function of B.

Searching DDB, we find the rule "If Q A's are B then Q^0.5 A's are B^^2," whose

consequent matches the query, with ?Q instantiated to Q^.5, A to

"Swedes" and B to "tall." Furthermore, in FDB, we find the fact "Most Swedes are

tall," which matches the antecedent of the rule, with Q instantiated

to "Most." A to "Swedes" and B to "tall." Consequently, the answer to the query

is "Most^0.5 Swedes are very tall," where the membership function

of "Most^0.5" is the square root of Most in fuzzy arithmetic.

The concept of a prototype is intrinsically fuzzy. For this reason, the

prototype-centered approach to deduction is based on fuzzy logic and

perception-based theory of probabilistic reasoning, rather than on bivalent

logic and standard probability theory.

What should be underscored is that the problem of adding deduction capability to

search engines is many-faceted and complex. It would be

unrealistic to expect rapid progress toward its solution.

* Lotfi A. Zadeh is Professor in the Graduate School and director, Berkeley

initiative in Soft Computing (BISC), Computer Science Division and the

Electronics Research Laboratory, Department of EECS, University of California,

Berkeley, CA 94720-1776; Telephone: 510-642-4959; Fax:

510-642-1712;E-Mail: zadeh@cs.berkeley.edu. Research supported in part by ONR

Contract N00014-99-C-0298, NASA Contract NCC2-1006,

NASA Grant NAC2-117, ONR Grant N00014-96-1-0556, ONR Grant FDN0014991035, ARO

Grant DAAH 04-961-0341 and the BISC Program of

UC Berkeley.

-- Dr. Masoud Nikravesh BISC Associate Director and Program AdministratorBTexact (British Telecom-BT) Senior Fellow Chairs: BISC-SIG-FLINT,ES, RT Berkeley Initiative in Soft Computing (BISC) Computer Science Division- Department of EECS University of California, Berkeley, CA 94720 Phone: (510) 643-4522; Fax: (510) 642-5775 Email: Nikravesh@cs.berkeley.edu URL: http://www-bisc.cs.berkeley.edu/

Staff Scientist Lawrence Berkeley National Lab, Imaging and Collaborative Computing Group Email: Masoud@media.lbl URL: http://vision.lbl.gov/ -------------------------------------------------------------------- If you ever want to remove yourself from this mailing list, you can send mail to <Majordomo@EECS.Berkeley.EDU> with the following command in the body of your email message: unsubscribe bisc-group or from another account, unsubscribe bisc-group <your_email_adress>

############################################################################ This message was posted through the fuzzy mailing list. (1) To subscribe to this mailing list, send a message body of "SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at (2) To unsubscribe from this mailing list, send a message body of "UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com" to listproc@dbai.tuwien.ac.at (3) To reach the human who maintains the list, send mail to fuzzy-owner@dbai.tuwien.ac.at (4) WWW access and other information on Fuzzy Sets and Logic see http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info (5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html

**Next message:**Thomas Lukasiewicz: "Uncertainty Frameworks in Nonmonotonic Reasoning at NMR'2002: extended"**Previous message:**masoud nikravesh: "BISC: BISC Program Announcement: NAFIPS-FLINT 2002"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b30
: Fri Jan 25 2002 - 02:07:30 MET
*