Course:CPSC522/Decision Support System using Interactive Preference Elicitation

Decision Support System using Interactive Preference Elicitation

Principal Author: Yu Yan
Papers referred:

1. Visual exploration and incremental utility elicitation

2. A decision support system for the design and evaluation of sustainable wastewater solutions

The first paper introduces an Interactive Preference Elicitation tool Veil and the second paper introduces the other Interactive Preference Elicitation tool ValueCharts. These two paper describe how the interactive procedure of each tool works as well as the different visualization methods applied in the two tools.

Abstract

This wiki page introduces the Decision Support System(DSS) using Interactive Preference Elicitation techniques. The first part of the page explains the motivation of DSS. Then it illustrates the basic Architecture of designing a DSS including Input, Decision Generation and Outputs. A computational algorithm applied in Decision Generation process is showed to help readers understand decision generation. The second part introduces Preference Elicitation, explaining the motivation as well as the applications. Two examples of Interactive Preference Elicitation tools based on additive multi-attribute value function preference model are presented and compared.

Background

Decision Networks (also called influence diagrams) are graphical representations of decision problems. Decision networks are generated by extending bayesian networks with decision making and utility, which are good prerequisite knowledge for this page.

Decision support system

Introduction

A Decision Support System (DSS) is a computer-based information system designed to provide assistance in determining and evaluating alternative courses of action. A DSS acquires data from different types of information, analyzes them with advanced statistical techniques to extract meaningful information, and narrows down the range of choices by applying rules based on constraints as well as users' preferences. Its goal is to facilitate the decision-making process.

DSS can be differentiated as passive, active, and cooperative DSS using the relationship with the user. A passive DSS is a system that aids the process of decision making, but that cannot bring out explicit decision suggestions or solutions. An active DSS can bring out such decision suggestions or solutions. A cooperative DSS allows the decision maker (or its advisor) to modify, complete, or refine the decision suggestions provided by the system, before sending them back to the system for validation. The system again improves, completes, and refines the suggestions of the decision maker and sends them back to them for validation. The whole process then starts again, until a consolidated solution is generated.

Architecture

The architecture of Decision support system can be divided into three parts:

• Inputs
• Decision Generation
• Outputs

In the following part, we will use the wastewater management system as an example to explain DSS in detail.

Input

Figure 1 - The Ontology of wastewater management model. The QUDT Ontologies, and derived XML Vocabularies, are being developed by TopQuadrant and NASA that means Quantities, Units, Dimensions and Data Types in OWL and XML.

Input is the information that will be provided to the DSS to be analyze. There are two main types of input:

1. Factors, numbers, and characteristics to analyze.
2. User Knowledge and Expertise.

For a wastewater management system, the input can be:

1. Information about the physical components of a system that provided by engineers, inventors, technology firms, etcetera. In the wastewater management model, pipe, activated sludge system and energy recovery system can be physical components inputs.
2. Context specific information (regulatory, demographic, geographical, etc.) that provided by, for example, planners (municipality, city, region, etc). In the wastewater management model, the geographical location to build the wastewater equipments, the tolerance of the odour can be context specific information input made by the municipality.
3. Information on values, preferences and predictions provided by various stakeholder representatives (e.g. elected officials, the public, special interest groups, NGOs).In the wastewater management model, the budget, the usable amount of energy can be Information on values, preferences and predictions input by the stakeholders.

Figure 2 - the relationship between database, ontology, input and output

Inputs can be provided by communities from diverse backgrounds. Therefore, we need to make different inputs as well as outputs consistent in same semantic level. One popular way is to define our own Ontology in order to enable information sources to inter-operate at a semantic level and to facilitate the adherence of different information sources to a common terminology for the same things. This can be done by importing other related ontologies as well as creating our own terminology. Figure 1 shows the ontology used in the wastewater management model.

After defining the Ontology, a database that contains all the input and output information can be created. Figure 2 shows the relationships between database, ontology, input and output.

Decision Generation

After receiving the inputs from the user, DSS will generate design alternatives. There are different ways for generating design alternatives, either based on predefined structure rules or computational methods. For example, In the wastewater management system presented in , a computational method based on depth-first branch-and-bound is applied. The pseudo code below provides detailed explanation of the generation process:

1:partialdesign = {community} // partialdesign means decision alternatives on constructing 
2:outputs = {community output} //outputs there mean different outputs of partialdesigns and are not the final 
                                                                 outputs of the DSS
3:repeat:
4:      choose output ∈ outputs
5:            &component such that type (output) = type (input) //type is defined by Ontology
                                                                  and stored in databse
6:            & all constraints are satisfied //constraints are from inputs
7:      add component to partialdesign //add means construct a new partialdesign
8:      remove output from outputs, // this output has been used to construct a new partialdesign and should
                                                                  removed from the set outputs above
9:      if component not already in partialdesign
10:     add outputs of component to outputs
11:until outputs = {}

Outputs

In some passive and active DSSs, when the alternatives generated are returned to the decision-maker, the decision-maker is not able to do further analysis on the alternatives, but only choose one or some as the final design. However, many complex decisions require the selection of a preferred alternative out of a set of objectives. Since it is common that conflicts exist between the objectives, tradeoffs among the conflicting objectives are therefore needed. For example, two design alternatives are given for a wastewater management system. One alternative is more environmentally friendly and requires a higher cost. The other design, while is less expensive, leads to a higher risk of environmental pollution. Therefore, the decision-maker will need to consider the tradeoff between different factors. As is indicated by previous studies, humans are generally not very effective at considering the tradeoffs . Thus, we need an extra model to support the task of selecting a design that will best satisfy the stated values and priorities by exploring how the values, and tradeoffs between designs, influence the evaluation of the alternatives.

Preference Elicitation

Introduction

Preference Elicitation is a critical component of many recommender systems and decision support systems. It refers to the problem of developing a decision support tool that is able to generate recommendations to the decision-maker and assist the decision-making process. It is important for such a system to model user's preferences accurately, find hidden preferences and avoid redundancy.

Methodology

Typically, the decision support with conflicting objectives methodology is composed of three phases . The first phase is inferring a preference model. Preferences are elicited from the decision-maker to build a quantitative model that includes all the objectives that the decision-maker cares about, as well as the specification of how the achievement of each objective can be measured. In the second phase, the preference model will be analyzed by the decision maker and applied to a set of alternatives. In the third phase, techniques such as sensitivity analysis will be applied to the model to further reduce the potential noise introduced in the elicitation process.

Additive Value Function

One commonly used model is called additive multi-attribute value function (AMVF). It is an easy-to-compute linear model under additive independence assumption and was devised in the context of the most popular decision analysis theory for preferential choice (Multi-Attribute Utility Theory). An AMVF usually consists of a value tree and a set of component value functions. A value tree shows the hierarchy of objectives, as well as how higher order objectives are linked to sub-objectives. It can help link objectives to evaluation criteria.

Figure 3 - Value Tree Example

Figure 3 shows a value tree example used to represent the preference in building a rural wastewater management system. In the value tree, non-leaf-node objectives are called abstract objectives and leaf-node objectives are called primitive objectives. Each primitive objective is associated with a component value function representing the preferability of each domain value for that objective as a number in the [0,1] interval, with the most preferable domain-value mapped to 1, and the least preferable one to 0. The arcs in the value tree are weighted to represent how valuable it would be for the decision maker to move from the worst to the best level of an objective, with respect to doing the same for its siblings. For the example shown in Figure 3, the preferability for medium odor is 0.4. Finally, given an alternative design, the value of the design can be evaluated using

$v=\sum w_{i}v_{i}(x_{i})$

, where $x_{i}$ is the value of primitive objective $v_{i}$, and $w_{i}$ is its absolute weight of $v_{i}$.

Other Elicitation Methods

Apart from elicitation methods using additive independence, there are also methods relying on conditional independence assumption. Although the elicitation methods under the independence assumptions make elicitation task easier, the elicitation of a complete value function may still be very time-consuming. Furthermore, objectives are preferentially dependent. Therefore, many research works focus on releasing the assumptions concerning preference structure, but still along with the goal of simplifying the elicitation task. The general idea is based on Clustering, that is to predict new users' utility function based on previously collected utility functions of similar users. Another popular elicitation approach is Collaborative Filtering described in Recommendation System using Matrix Factorization, in which the system make recommendations to a user based on other users' opinions. But this approach is not in the framework of decision theory.

Interactive Preference Elicitation

With the development of DSS, researchers began to realize that the fundamental goal of preference elicitation should not be returning an alternative that should be blindly accepted. Instead, it is to provide the decision-maker with more insights on the problem. The fundamental goal of preference elicitation is to enable the decision-maker to organize all relevant knowledge into a structure that can be effectively analyzed and investigated . Building preference model can be regarded as the first step of the decision aid process.

To achieve this goal, the decision-maker should be able to investigate the decision problem from multiple aspects: by analyzing the model itself, the results of applying the model to the alternatives, and how the results are sensitive to the model parameters. Most decision-makers will not be satisfied if only the evaluation and the ranking of the alternatives are provided.

Many research works have been conducted to provide interactive techniques to support decision-makers in inspecting preference model and evaluation. Typically, the design alternatives returned from the preference model will be visualized and displayed to the decision-maker, for the easiness of analysis. The decision-makers are able to provide more utility information by changing objective weights or by indicating a preference between two alternatives directly in the interface . Below are two examples of interactive preference elicitation applications.

VEIL

VEIL is an incremental utility elicitation system initially created to support users in selecting round-trip flights. Incremental utility elicitation is a framework which can simultaneously make suggestions to decision-makers based on the incomplete preference model, and update the model according to feedback from the decision-maker. VEIL supports visual exploration of the available alternatives according to the domain values of objectives and to a linear combination of preferences. In VEIL, users are able to view alternatives through two-dimensional projections and can investigate on the information about a specific alternative. Users can also provide preference information by changing weights or by indicating a preference between two design alternatives on the interface.

Figure 4 - VEIL Example

Figure 4 shows an example of VEIL. It shows a projection of alternative airlines for a round-trip flight from Los Angeles to Victoria, British Columbia. It composes of two subfigures which represent the applications of default utilities and customized utilities. In the example, both $x$ and $y$ axis are based on the outbound departure time. The width of each bar represents the duration of the outbound flight. As many round-trip flights share the same outbound leg, each rectangle accounts for a group of multiple flights. The labels on each rectangle include the airline, cost of the flight with the maximum utility estimate in the group, the number of alternatives in the group, and the maximum utility estimate which ranges from 0 to 100. VIEL uses grey-scale shading to represent the utility rank among alternatives, with the best alternative in white and the worst in black. In the left subfigure, default utilities are used. The result shows that the preferred option is the United flight leaving at 1 pm and there are also good flights leaving at regular intervals until about 4 pm. Users can interact with the model by directly changing the attribute weights or expressing a preference for a specific flight. In this example, the user prefers to depart as late as possible, and expresses this as a preference for the Air Canada flight departing at 1 pm over the flight departing at 12 pm. This leads to an updated result shown on the right. Preferred flights have now changed to mostly the lower right corner of the screen, and the most preferred alternative becomes the Alaska flight leaving after 4 pm.

ValueCharts

ValueCharts is a set of visualizations and interactive techniques intended to support decision-makers in preferential choice . In ValueCharts, columns(or rows in another version) represent alternatives and rows(or columns in another version) represent objectives. Each row is assigned an amount of space proportional to the absolute weight of the objective, which enables the comparison of objective values across rows. As is shown in Fig 5, objectives are listed on the left side. Stacked bars, shown on the right side, are used to enable the comparison of alternatives with respect to the value of each primitive objective and abstract objective. The cumulative assessments of every attributes' weights of different alternatives in the left parts are visualized stacked bars on the right.

Figure 5 - ValueCharts Example

With ValueCharts, it is clear for the decision-makers to investigate the pros and cons of each alternatives design. Decision-makers can also adjust the weights on the interface to further explore the trade-offs between different criteria. By dragging the edges of the divided chart, the corresponding objective weight will be changed and all the other weights are recomputed accordingly. Therefore, decision-makers are able to conduct sensitivity analysis for the model in this way. The example shown in Figure 5 consists of three subfigures representing three different scenarios given the same information. There are three primitive objectives: economic (black), environmental (dark grey) and social (light grey). In the left figure, all three objectives are weighted equally. In the center figure, environmental and social objectives are weighted more heavily. In the right figure, specific criteria are selected. The outcomes of different weight applications are shown with stacked bars. It is clear that the ranks of design alternatives are different under different weighting scheme. The visualization and interaction technique facilitates the analysis of different alternatives and thus support a more informed final decision.

Comparison

Both of the two interactive preference elicitation tools are based on the same linear model - Additive Value Function to express preferences and evaluations. With respect to ValueCharts, VEIL allows the user only a minimal inspection of the preference model and of its application to the alternatives. Also, no support for efficient sensitivity analysis is provided in VEIL. As for interaction methods, in VEIL, input data is provided through entering a weight value directly or expressing preferences between alternative pairs indirectly. With ValueCharts, users are able to drag between stacked bars to investigate the influence of objectives. The dragging method of ValueCharts is more flexible and user-friendly. Moreover, in ValueCharts, the visualization interface is easier for user to compare every decision alternatives.