Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Electronic shopping
Reexamination Certificate
1999-05-21
2003-10-14
Kemper, M. (Department: 3622)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Electronic shopping
C706S012000
Reexamination Certificate
active
06633852
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to data processing systems and, more particularly, to a preference-based product browser that utilizes a belief network.
BACKGROUND OF THE INVENTION
Systems currently exist that display an electronic catalog of products to a user so that the user may select one or more products that suit their needs. These systems typically display hundreds or even thousands of products to the user, and each product may have tens or hundreds of features. When a user is attempting to select a product, however, the user is left to aimlessly peruse the catalog with little or no direction. The user is thus confronted with numerous products with numerous features and must evaluate each product before they can select the product that best suits their needs. Many users become frustrated with the overwhelming task of selecting a product from among numerous choices, and consequently, these users do not purchase a product. It is thus desirable to improve such product selection systems.
An exemplary embodiment of the present invention is described below as using a belief network, so to better explain the details of the exemplary embodiment, an overview of belief networks is presented. A belief network is a representation of the probabilistic relationships among distinctions about the world. A distinction in a belief network can take on a set of values and are thus called variables. A belief network is expressed as an acyclic-directed graph where the variables correspond to nodes, and the relationships between the nodes correspond to arcs.
FIG. 1
depicts an example belief network
101
. The belief network
101
contains three variables, x
1
, x
2
, and x
3
, which are represented by nodes
102
,
106
, and
110
, respectively. Also, the example belief network
101
contains two arcs
104
and
108
. Associated with each variable in a belief network is a set of probability distributions. Using conditional probability notation, the set of probability distributions for a variable can be denoted by p(x
i
|pa(x
i
)), where “p” refers to the probability distribution and where “pa(x
i
)” denotes the parents of variable x
i
. Thus, this expression reads as follows, “the probability distribution for variable x
i
given the parents of x
i
.” For example, x
1
is the parent of x
2
. The probability distributions specify the strength of the relationships between variables. For instance, if x
1
has two states (true and false), then associated with x
1
is a single probability distribution p(x
1
) and associated with x
2
are two probability distributions p(x
2
|x
1
=t) and p(x
2
|x
1
=f).
An important aspect of belief networks is the concept of dependence. Sets of variables x and y are said to be conditionally independent, given a set of variables z, if the probability distribution for x given z does not depend on y. That is, if p(x|z,y)=p(x|z), x and y are conditionally independent given z. If z is empty, however, x and y are said to be “independent” as opposed to conditionally independent. If x and y are not conditionally independent given z, then x and y are said to be conditionally dependent given z.
The arcs in a belief network convey dependence between nodes. When a belief network has an arc from a first node to a second node, the probability distribution of the second node depends upon the value of the first node. For example, belief network
101
contains an arc from node
102
to node
106
, and therefore, node
106
is said to be dependent on node
102
. Just like the presence of arcs in a belief network conveys dependence, the absence of arcs in a belief network conveys conditional independence. For example, node
102
and node
110
are conditionally independent given node
106
. That is, the values of nodes
102
and
110
are conditionally independent if the value of node
106
is known, the condition being the observation of node
106
. However, two variables indirectly connected through intermediate variables are dependent given lack of knowledge of the values (“states”) of the intermediate variables. Therefore, if the value for x
2
is unknown, x
1
and x
3
are dependent.
FIG. 2
depicts an example belief network for troubleshooting automobile problems. The belief network of
FIG. 2
contains many variables
202
-
234
relating to whether an automobile will work properly and arcs
236
-
268
. A few examples of the relationships between the variables follow: For the radio
214
to work properly, there must be battery power
212
(arc
246
). Battery power
212
, in turn, depends upon the battery working properly
208
and a charge
210
(arcs
242
and
244
). The battery working properly
208
depends upon the battery age
202
(arc
236
). The charge
210
of the battery depends upon the alternator
204
working properly (arc
238
) and the fan belt
206
being intact (arc
240
).
The automobile troubleshooting belief network also provides a number of examples of conditional independence and conditional dependence. The operation of the lights
216
and battery power
212
are dependent, and the operation of the lights
216
and operation of the radio
214
are conditionally independent given battery power. The concept of conditional dependence and conditional independence can be expressed using conditional probability notation. For example, the operation of the lights
216
is conditionally independent of the radio
214
given battery power
212
. Therefore, the probability of the lights
216
working properly given both the battery power
212
and the radio
214
is equal to the probability of the lights working properly given the battery power alone, P(Lights|Battery Power, Radio)=P(Lights|Battery Power). Also, the probability of the lights
216
working properly is conditionally dependent on the radio
214
given the battery
208
. Therefore, the probability of the lights
216
working properly given both the radio
214
and the battery
208
is not equal to the probability of the lights given the battery alone: P(Lights|Radio, Battety)≠(Lights|Battery).
There are two conventional approaches for constructing belief networks. Using the first approach (“the knowledge-based approach”), a person known as a knowledge engineer interviews an expert in a given field to obtain the knowledge of the expert about the expert's field of expertise. The knowledge engineer and expert first determine the distinctions of the world that are important for decision making in the expert's field of expertise. These distinctions correspond to the variables of the domain of the belief network. The “domain” of a belief network is the set of all variables in the belief network. The knowledge engineer and the expert next determine the dependencies among the variables (the arcs) and the probability distributions that quantify the strengths of the dependencies.
In the second approach (“the data-based approach”), the knowledge engineer and the expert first determine the variables of the domain. Next, data is accumulated for those variables, and an algorithm is applied that creates a belief network from this data. The accumulated data comes from real world instances of the domain. That is, real world instances of decision making in a given field. Conventionally, this second approach exists for domains containing only discrete variables.
A method for generating a belief network that is an improvement over these conventional approaches is described in U.S. Pat. No. 5,704,018, entitled “Generating Improved Belief Networks” assigned to a common assignee, which is hereby incorporated by reference. This improved method uses both expert knowledge and accumulated data to generate a belief network.
After the belief network has been created, the belief network becomes the engine for a decision-support system. The belief network is converted into a computer-readable form, such as a file, and input into a computer system. Then, the computer system uses the belief network to deter
Fayad Usama M.
Heckerman David E.
Meek Christopher A.
Amin & Turocy LLP
Kemper M.
Microsoft Corporation
LandOfFree
Preference-based catalog browser that utilizes a belief network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Preference-based catalog browser that utilizes a belief network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Preference-based catalog browser that utilizes a belief network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3127152