# Presentation: 045934

## Hybrid User Model for Information Retrieval

- Hien Nguyen, Eugene Santos Jr, Qunhua Zhao
- University of Connecticut

## Outline

**Problem**
**Motivation**
**Our approach**
**Empirical evaluation**
**Conclusion **

## Outline

**Problem**
**Motivation**
**Our approach**
**Empirical evaluation**
**Conclusion **

## Problem

- Employing a user model for Information Retrieval (IR):  capture and use *knowledge* about a user to improve a user’s effectiveness in an information seeking task.
- Why do we need user models for IR?

## Problem

- Why is it a tough problem?
- Partiality
- Vagueness
- Dynamics
- Uncertainty

## Outline

**Problem**
**Motivation**
**Our approach**
**Empirical evaluation**
**Conclusion **

## Motivation

- Existing methodologies for building user model for IR include:
- System-centered approaches: use IR techniques. (*e.g Spink & Losee(1996), Efthimis(96), Lopez-Pujalte (03),Drucker et al(02))  *
- User-centered approaches: use Human Computer Interaction (HCI)/Artificial Intelligence (AI) techniques *(e.g:Belkin(93), Radlord(96))*
- Hybrid approaches: combine IR with HCI/AI techniques. *	**(e.g Logan et al. (94), Decampos et. al 98, Ruthven et al. 03) *
- Very little crossover between IR and AI/HCI to build user models for IR

## Motivation

- Existing methodologies for building user model for IR include:
- System-centered approaches: use IR techniques. (*e.g Spink & Losee(1996), Efthimis(96), Lopez-Pujalte (03),Drucker et al(02))**  *
- User-centered approaches: use Human Computer Interaction (HCI)/Artificial Intelligence (AI) techniques *(e.g:Belkin(93), Radlord(96))*
- Hybrid approaches: combine IR with HCI/AI techniques. *	**(e.g Logan et al. (94), Decampos et. al 98, Ruthven et al. 03) *
- Very little crossover between IR and AI/HCI to build user models for IR

## Motivation

- Existing methodologies for building user model for IR include:
- System-centered approaches: use IR techniques. (*e.g Spink & Losee(1996), Efthimis(96), Lopez-Pujalte (03),Drucker et al(02))**  *
- User-centered approaches: use Human Computer Interaction (HCI)/Artificial Intelligence (AI) techniques *(e.g:Belkin(93), Radlord(96))*
- Hybrid approaches: combine IR with HCI/AI techniques. *	**(e.g Logan et al. (94), Decampos et. al 98, Ruthven et al. 03) *
- Very little crossover between IR and AI/HCI to build user models for IR

## Motivation

- Important factors for building user models for IR:

- Partiality
- Vagueness

- Incremental

- Uncertainty

- Dynamics

- Adaptive

- Intent:
- 	Author’s intent
- 	User’s intent

- Relevance feedback

## Our approach

- We try to improve a user’s effectiveness in an information seeking task by:
- Developing a hybrid user model to capture ***user intent*** dynamically by analyzing behavioral information of retrieved relevant documents and by combiningthe captured user intent with the elements of an IR system in a decision theoretic framework *(ICAI00, IAT01, UM03, HFES03 & 04, AH04)** *
- Using IR evaluation procedures and collections and examining usability testing to evaluate this model (*HFES04, AH04, UM05*)

## Novelty of our approach

- Develop a hybrid user model by combining information about a user and information about an IR system in a decision theoretic framework
- Develop a  unified evaluation framework
- Fine-grained representation
- Ability to learn user knowledge dynamically

## Outline

**Problem**
**Motivation**
**Our approach**
**Empirical evaluation**
**Conclusion **

## Hybrid User Model

- Motivation
- Allows deeper influence on an IR system.
- Adaptation using only a user’s information may not be helpful if a user is new to a domain
- Insight information about an IR system may help a user get closer to his/her final searching goal

## Architecture of Hybrid User Model

- Attributes
- Describe
- a User

- Attributes
- Describe
- an IR system

- Decision
- Model

- User Intent

- IR elements

## Hybrid User Model

- Our approach:
- Convert this problem into a multi-attribute decision problem
**Determine a set of attributes**:
*{****I,P,C****,**Q,T,In,D,S**}*
**Use multi-attribute utility model to solve this problem**

## User Intent

- Consists of 3 components:
**User interests (I)**: *“****What**** needs to be done or accomplished?” *
**User preferences (P)**: *“****How**** is something done or accomplished?”*** **
**User context (C)**: *“****Why**** is the user trying to accomplish something?” *

## Context Network (C)

- Captures user knowledge. It contains *concept nodes* and *relation nodes.*

**Notes:**
It a directec acyclic graph that contains two kinds of nodes.
consist of 2 relations: setsubset (isa), and related to. One may ask from where do we get this. All documents in our database are converted to Document Graph by the process of extracting set-subset, and related to. 
This is done offline. Each node of the concept networks is associated with weight, bias and values which will be used in the spreading activation algorithm to infer a new interest set. The weight of a node represents its importance assigned initially by the system. The concept nodes and
``isa'' relation nodes have weights equal to 1 while the ``related to'' relation nodes have weight equals to 0.8. The value of a node
represents its importance to a user and is any real number from 0 to 1. The bias of a node represents whether this node is actually
in the user's interests or not. 

Right now, we incoporate uncertainty in C on the weight of each node. We hope later on to map C to BN because probabilistic information is there.

We currently consider three heuristics: noun phrase heuristics, sentence heuristics and preposition heuristics. Noun phrase heuristics produces set-subset relations while the other two produces related to relation,

## Context Network (C)

-  Is constructed “*on-the-fly*” by finding intersections of all retrieved relevant document graphs.

## Interest Set (I)

- Determines what is currently relevant to a user.
- Each element of interest set consists of ***interest concept**** (**a**) *and ***interest level**** **L(a).*
- Fading mechanism:
- 		L(a) = 0.5*(L(a) + n/m)
- 		n: number of retrieved relevant document with *a*
- 		m: number of retrieved documents

**Notes:**
Read the first sentence. 
The concepts in an interest relevancy set are determined from a
user's query and the set of documents that the user has indicated
as relevant in recent search. Initially, the interest relevancy set contains the concepts found
in a {\it query graph} (QG) and their assigned interest levels are 1.
We compute interest level after every query by this formula. 
Because people change over time, therefore, we use a fading technique to get rid of concepts that are not in the current interests of a user. The new algorithm for determining the new Interest set is bascially based on the idea that the further one concept node located from the being observed current interest concept, the less likely a user is interested in the concept.

## Preference Network (P)

-  Represents how a user wants to form a query
-  Is represented using Bayesian networks.
-  Consists of pre-condition, goal and action nodes
- Pre-condition: represents the requirement of a tool used to form a query
- Goal: represents a tool to form a query (filter/expander)
- Action: represents the modified query

**Notes:**
Preference network is a bayesian network which reflects the preference of a user over a set of tools for modifying the user query. 
Bayesian networks are directed acyclic graphs where graph nodes represents variables and the link represent probabilistic influence relationships between two nodes.
Generally, it contains 3 types of nodes, precondition nodes, goal node and action node.  Each node has two states: T or F. Example of precodition nodes are nodes representing a user query, a node representing an interest concept. Example of a goal node is a filter that that
narrows down the search topics semantically or an expander that
expands the search topics semantically. An example of {\it A} is a
modified query. For each pre-condition node representing a user's
current interest, its prior probability will be set as the
interest level of the corresponding interest concept. For each
pre-condition node representing a subgraph of a query graph (QG),
its prior probability will be set as the frequency of this query fragment being asked in the past. The conditional probability table of each goal node is similar to the truth table of logical AND. Each {\it G} is associated with only one {\it A}. The probability of {\it A} is set to 1 if the tool is chosen and to 0, otherwise. 

## Preference Network (P)

## Preference Network (P)

- Update: When a user gives relevance feedback after each query.
- Correction function calculates the probability that a new tool will improve retrieval performance for both tools.
- The one with higher probability will be added

**Notes:**
our current version, there are two
different tools, filter and expander. Therefore, two new
preference networks are created, one of them contains an
additional new tool labelled as filter, and another contains a new
tool labelled as expander. The correction function will then
calculate the probability that a new network will improve the
user's effectiveness for both of the two new preference networks.
The preference network updates itself according to the one with
higher probability. The calculation is simple, which is to find
out the frequency that a tool helps in the
previous retrieval process. Currently, if the total number of
retrieved relevant documents excesses a user-defined threshold,
the tool used for the query modification is considered as helpful.

So basically, the Context network contains all the knowledge will be used to modify a user’s query, interest set contains the set of concepts that the user is currently focus one and preference contains the tools – which use the information in Context network about the link between interest concept and concept in the user query to change the user query

## Using IPC to modify a user’s query

- Given M=*{I,P,C} *and a query graph *q.*
- Construct I’ by spreading activation algorithm on *C*.
- Set as evidences all interest concepts of *I’* found in P and query node representing *q *found in P*.*
- Perform belief updating on *P. *Choose top *n *goal nodes from *P *(*G)*
- For every goal *g *in G:
- Depending on each *g,* add corresponding paths in C to *q*

## Hybrid User Model

- Use multi-attribute decision model
- Evaluate each outcome by effectiveness function: *average precision at three point fixed recalls*
- Reduce the number of attributes, only Query (Q) and Threshold (T) are considered
- Construct a value function over these two attributes:
**V(Q,T) = ********1****V****1****(Q) + ********2****V****2****(T) **
**	**
- iff 	x2i  x1i	for all i=1,2
- 		x2i > x1i	for some i

## Hybrid User Model

- Sub value function for a query
- Take advantage of literature on predicting query performance from IR
- Initial sub value function (He and Ounis 04)
**Update sub value function**

## Hybrid User Model

- Sub value function over threshold

**(Boughanem 00)**

## Implementation of Hybrid User Model

**Query**

**Q****1****,Q****2****,...,Q****m**
**Computer V(Qi)**

**Threshold**
**preference**

**Compute**
**Threshold**

**Send Q****i****,T to **
**search module**

**Update V(Q) **
**V(T)**

**Feedback**

**IPC **

## Outline

**Problem**
**Motivation**
**Our approach**
**Empirical evaluation**
**Conclusion **

## Evaluations with a hypothetical user

- Metrics: precision, recall, **average precision at three point fixed recall**
- Testbed: home-made medical database, **Cranfield**, **CACM, Medline**.
- Procedures: **standard and new**.
- Compare with **Ide dec-hi** using term frequency inverted document frequency (TFIDF) (Salton and Buckley 90) (Lopez-Pujalte et al 03)

***(HEFS 04, AH04)***

**Notes:**
I have talked about the user model. Now, we are doing some initial evaluation to see if we are on the right track and also get some feedback from related communities for our work. We evaluate the effectiveness of our user model in terms of its effects on retrieval performance and on users. These results are reported in our UM 03 and Human factors paper 03.

## Standard procedure for hybrid model

## New procedure for hybrid model

## Discussion

- Hybrid user model achieves more relevant documents in the top 15 compare to IPC model alone.
- There is insufficient evidence to conclude which value function works best.
- Implication: we can use a simple value function and still achieve good results.

## Evaluation with real users(UM05)

- Test bed: CNS collection on WMD and terrorism.
- Our approach vs. Verity Query Language.
- Subjects use two different systems in parallel.
- There are 10 scripted queries on “Iran R&D supporting Biological Weapons”.
- Only 10 documents are reviewed for relevancy.
- Three analysts took part in the experiments.

## Evaluation with real users

- User Model

- Verity Query Language

## Outline

**Problem**
**Motivation**
**Our approach**
**IPC Model**
**Hybrid Model**
**Empirical evaluation**
**Conclusion **

## Conclusion

- Capturing a user’s intent and combining the captured user intent with elements of an IR system in a decision theoretic framework.
- Novelties of our approach:
- Hybrid user model which truly integrates information about a user and information about an IR system.
- Unified evaluation framework.
- Fine-grained representation of user model
- Learn user knowledge dynamically

## Acknowledgement

- This research has been funded by AFRL Human Effectiveness Directorate Through Sytronics Inc. and Advanced Research and Development Activity (ARDA) – US Government.
- Thanks to Dr. Santos Jr, Dr. McCartney, Dr. Henning, Dr. Doan, Dr. Zhao, Hua Wang, Fei Gao, Erik Pukinskis, Bence Mayar, Chester Lee, Greg Johnson, Hang Dinh, and Feng Zhang.

## References

- Impacts of User Modeling on Personalization of Information Retrieval: An evaluation with hyman intelligence analysts. Eugene Santos Jr., Qunhua Zhao, **Hien Nguyen**, Hua Wang. 2005. In *Technical report of Workshop on Evaluation of Adaptive Systems at UM 2005. *To appear.
- Capturing User Intent for Information Retrieval. 2004. **Hien Nguyen**, Eugene Santos Jr., Qunhua Zhao and Hua Wang. In  Proceedings of the 48th Annual Meeting for the Human Factors and Ergonomics Society (HFES-04). New Orleans, LA. 2004. Pages 371-375.
- Evaluation of Effects on Retrieval Performance for an Adaptive User Model. **Hien Nguyen**, Eugene Santos Jr., Qunhua Zhao and Chester Lee. 2004. In Adaptive Hypermedia 2004: Workshop Proceedings - Part I. Eindhoven, the Netherlands. Pages 193-202.
- User Modeling for Intent Prediction in Information Analysis. 2003. Eugene Santos Jr., **Hien Nguyen**, Qunhua Zhao, and Hua Wang. In Proceedings of the 47th Annual Meeting for the Human Factors and Ergonomics Society (HFES-03), Denver, CO. Pages 1034-1038.
- Empirical Evaluation of Adaptive User Modeling in a Medical Information Retrieval Application. 2003. Eugene Santos Jr., **Hien Nguyen**, Qunhua Zhao, and Erik Pukinskis. Lecture Notes in Artificial Intelligence 2702: User Modeling 2003 (Eds. P. Brusilovsky, A. Corbett, and F. de Rosis), Springer. Pages 292-296.
- Kavanah: An Active User Interface Information Retrieval Application. 2001.Eugene Santos Jr., **Hien Nguyen** and Scott M. Brown. Proceedings of the 2nd Asia-Pacific Conference on Intelligent Agent Technology. Maebashi, Japan. Pages 412-423.
- Active User Interface in a Knowledge Discovery and Retrieval System. 2000. **Hien Nguyen**, Mitch G. Saba, Eugene Santos, Jr. and Scott M. Brown. In Proceedings of the International Conference on Artificial Intelligence (ICAI2000). Las Vegas, Nevada. June 2000. Pages 339-344.
- Medical Document Information Retrieval through Active User Interfaces. 2000. Eugene Santos Jr., **Hien Nguyen, **Scott M. Brown. In Proceedings of the International Conference on Artificial Intelligence (ICAI2000). Las Vegas, Nevada. June 2000. Pages 323-329. (*Invited paper*).