My Blog List

Tuesday, April 25, 2017

Reading 15: User-Driven System-Mediated Collaborative Information Retrieval

Motivation: Collaborative information retrieval (CIR) involves more than one information seekers in a searching process. Different from individual information retrieval (IIR), CIR needs to take into account users' skills and preferences, also to support their communication and cooperations. Existing approaches can be generally divided into two categories. One is user-based CIR system which allows users to decide role assignments and supports their communication in searching process; the other one is system-based CIR which system would impose roles to users and optimizes information retrieval. Both of them have limitations and merits. This paper tries to combine them together, and proposes a user-driven system-mediated CIR system.

Approach: In the user-driven system-mediated CIR, users' searching behaviors would be monitored and analyzed; it would discover significant behavioral differences between each pair of users; finally it suggests roles to users in order to leverage the best of users' skills and preferences. Take the pair of roles "Gatherer versus Surveyor" as an example. In a collaborative searching process, gatherer would be more likely to seek highly relevant documents, so that he or she would perform queries with much overlap, and spend more time reading webpage contents; whereas, surveyor would tend to explore new things on websites, he or she would try different queries, spend less them on each webpage and accordingly, the query success is low. By analyzing such features, i.e. query overlap, dwell time and query success, we can obtain insights into user's role difference.

Experiments: They ask participants (students in Rutgers University) to collaboratively write a report on an exploratory topic. User study #1 has the topic of "Gulf oil spill" and user study #2 focuses on the topic of "Global warming". In the searching session, supportive chat system and search tools enable bookmarking webpages and saving snippets. Specifically, three types of features are considered (shown in Table 1).
Table 1. Features used to describe a searching session.
By analyzing users' searching behaviors, they found that significant behavioral difference became obvious after a short period of time as a session started. Figure 1 reveals this observation as p values are very significant. Besides, during the same session, users do not change their roles.
Figure 1. Significant difference in users' search behaviors.
Finally, they compare the effect of role mining on information retrieval in a CIR task. Table 2 shows the comparison with four baselines and report the average increase that RB-CIR has obtained. From it we observe that, RB-CIR outperforms all other methods except for PM-CIR. They argued that since the difference between RB-CIR and PM-CIR is not significant, it's still reasonable to say that RB-CIR has better performance.
Table 2. Comparison of RB-CIR with four baselines.
One limitation in their proposed method is the lacking of prior knowledge of users' skills as roles are mined from current searching behaviors. Therefore, in the further they would consider users' prior searching behaviors and preferences to complement current actions.



Thursday, April 20, 2017

Reading 14: Jointly Modeling Aspects, Ratings and Sentiments for Movie Recommendation (JMARS)

Motivation: In recommendation and review systems, users might not only provide overall ratings but also write more informative reviews. In reviews, users usually express their sentiments, discuss the aspects they like or do not like, and provide interpretations about their ratings. It is necessary to exploit such implicit comments to boost recommendation performance. For such purpose, this paper determines to model ratings and sentiments in comments in a per-aspect way, and finally they propose a probabilistic model based on topic modeling and collaborative filtering that holds superior performance.
Fig. 1 Rating and review model in a per-aspect way. It consists of two parts: modeling ratings and modeling reviews.
Approaches: Given a user and a movie, their task is to predict (i) the observed rating as well as (ii) the review. (i) In terms of ratings, they assume that any observed overall rating is generated from individual aspect-specific ratings, including rating for actors, rating for plots and rating for visual effect etc. Different aspects (actors, plot, visual effect) may hold different importance weights. Larger value implies that user has an interest in such aspect and the movie also highlights such aspect. Simply speaking, high overall rating is generated through a good matching between user's expectations and movie's quality in those aspects that user cares most. (ii) When writing a review, the user might talk about movie specific contents, and also express aspect specific judgements (sentiments). To describe such variety, they assume that the review language model contains five components:
1. A background language component;
2. A background sentiment language component;
3. A movie-specific language component;
4. An aspect-specific language component;
5. An aspect-specific sentiment language component.

Fig.1 illustrate the entire framework of their probabilistic model. User's interest and movie's relevance are collectively used to model the final rating and review contents. Their model is called "JMARS".

Experiments: The experiment is conducted on a dataset collected from IMDb - a famous movie review website. In total, 50k movies along with their reviews are crawled. They use 80% of data as training data, 10% as validation and 10% for testing. Fig. 2 shows comparison of JMARS in terms of perplexity. When factor size is set as 5 or 10 (5 or 10 aspects are considered in movie), JMARS could always outperforms HFT approach. Besides, Fig. 3 reveals MSE comparison which also proves JMARS good performance.

Fig. 2 Comparison of models using perplexity.
Fig. 3 Comparison of models in terms of MSE.

Tuesday, April 11, 2017

Week 13: Visual-Textual Joint Relevance Learning for Tag-Based Social Image Search

Title: Visual-Textual Joint Relevance Learning for Tag-based Social Image Search, IEEE Transactions on Image Processing, 2013.

Motivation: With the development of social media, a new type of search has become increasingly popular - social search, and this paper particularly focuses on image search in social media. Given a tag query, for example "apple", a good search engine is able to output a set of highly relevant but also diverse images showing fruit apples, cellphone and MacBook. Tag-based social image search always leverages user-generated tags to calculate image's relevance score, however, such tags contain too much noises and it's difficult to form an optimal ranking strategy. Therefore, this paper seeks to simultaneously utilizes tags as well as visual information for image relevance learning.
Fig 1. Framework of the proposed visual-textual joint relevance learning method.
Method: The basic framework can be seen in Fig 1. (I) Given a set of images, each of them can be represented by two kinds of features - visual as well as textual features. (II) Based on such two types of representations, a hypergraph can be constructed. Here it should be highlighted that hypergraph is different from the general graph. In a hypergraph, edge is called "hyperedge", which does not represent pairwise interactions, while it is a relationship consisting of a set of images. To be specific, the nodes sharing the same tags can be "linked" by a textual-based hyperedge, and the images sharing the same visual "words" can be connected by a visual-based hyperedge. Fig 2. reveals textual-based hyperedges (left) and visual-based hyperedges (right). (III) A joint image relevance learning process is performed on a set of pseudo-relevant samples. Pseudo-relevant samples are actually labeled images collected based on tags. Then they propose an objective function aiming to learn a relevance vector f with each element indicating an image's relevance score. (IV) Based on the learned relevance score, the algorithm will return top-K images to users.

Fig 2. Examples of hyperedge construction. The left figure shows textual-based hyperedges and the right one shows visual-based hyperedges.
Experiment: They perform experiments on Flickr Image Dataset (104,000 images, 83,999 tags), and compare the proposed textual-visual joint hypergraph learning approach (HG-WE-joint) with five stat-of-the-art baselines, including graph-based semi-supervised learning, sequential social image relevance learning, tag ranking, tag relevance combination, hypergraph-based relevance learning with equal weight (HG). It also examines the performance of the proposed approach with only single information, HG-WE-visual or HG-WE-textual. Results show that HG-WE-joint outperforms all baselines and maintains good robustness to parameters. However, HG-WE-joint requires the highest computational cost to achieve the best retrieval performance.

Wednesday, April 5, 2017

Talk summary 2: Modeling Sequential Decision Making in Team Sports using Imitation Learning

Dr. Peter Carr is working as a research scientist at Disney Research, Pittsburgh. In this talk, he introduced their recent work about modeling sequential decision making in sports using imitation learning techniques. I would like to summarize his talk from the following three critical points.

What is the objective of their work?

In terms of team sports analysis, researchers try to compare the performance of a specific teams or players with that of a typical team in a professional league, i.e. average league performance. To be able to quantitatively study players' movement patterns, it requires existence of player tracing dataset. Fortunately, with the advance of data collection techniques in recent years, it becomes possible that people gather spatiotemporal sport data by tracing players' movements in a large number of games. In the talk, Dr. Peter Carr mentioned that they have used approximately 100 games of player tracking data from a professional soccer league for modeling sequential decision making.

With such dataset, they are interested in modeling defensive situations - what players would do within under the situation where the opposition had control of the ball. They explore what a defensive player should have done, based on the average league performance revealed by data, in comparison with what they actually did. This kind of work help us better understand the overall defensive strategies of a league as well as how a certain team would play differently. In this framework, the "should-have-done" motions are learned from player tracking data through "data-driven ghosting" method. In next section, we will summarize the high-level intuition of the method.

What is the method?

Data-driven ghosting is implemented based on imitation learning. Imitation learning, also called "learning from demonstration", is a process that computer automatically learns strategies by observing expert behaviors. It is similar to what human would do in learning process - a person who has no knowledge of sports, can understand what to do if he/she has observed a sufficient number of games.

Figure 1. Deep multi-agent imitation learning framework. Single player learning (Upper) and multi-agent learning (Bottom).
Their task is to predict the action of a player at each time step given the state feature, which actually is a online sequence decision making problem. Besides, they need to predict actions for multiple players at the same time. Therefore, they proposed a deep multi-agent imitation learning framework (figure 1). Two major components are presented - single player modeling and joint training of multiple players. In stage 1, the algorithm learns a model for each player to predict average league action, and in stage 2, these pre-trained models learned in stage 1 would be used in stage 2 for joint training of multiple agents. In both stages, training and prediction are combined together, so that a model can learn from their prediction mistakes to go back to "right" track (see in figure 1).

How about the results?

An example is shown in figure 2. The data-driven ghosting players (white) and their trajectories (white) represent average league movements; colored dots and trajectories represent actual movements in games. Results have revealed that the proposed model can generate a sequence of behaviors showing spatial and formational awareness. More information can be viewed in the video: http://www.disneyresearch.com/publication/data-driven-ghosting.
Figure 2. Ghosting behaviors (white) in comparison of actual movements.

[1] Le, Hoang M., et al. "Data-Driven Ghosting using Deep Imitation Learning." (2017).

Week 12: FolkTrails: Interpreting Navigation Behavior in a Social Tagging System

Motivation: Social tagging systems have been widely used to organize and store online information, such as webpages and publications (Delicious and Bibsonomy). In such systems, users can freely assign keywords to specific resources for retrieval and organization in the future. By tracing users' behaviors in those tagging systems, researchers are able to understand how they assign tags, navigate among resources and consume information. This paper focuses on the specific problem of interpreting human navigation behaviors within Bibsonomy, and exploring the behavioral differences between different user subgroups.

Methods: It formulates a set of hypotheses which can be encoded as transition probability, and then apply HypTrails [1], a framework for comparing hypotheses based on empirical observations, to figure out which hypotheses better capture the intrinsic mechanism of human navigation trails. Figure 1 shows an example of user reviews for restaurants in Italy on Yelp. To be specific, HypTrails defines a navigation trail as a first-order Markov chain over a sequence of states, so that each hypothesis can be formulated as transition probabilities jumping from one state to another. To conclude which hypothesis better reflect empirical observations, it leverages Bayes factor, which compares the marginal likelihood P(D|H) where D represents real observations and H indicates hypothesis.

Figure 1. (a-c) show three hypotheses about human trails - uniform hypothesis, geo hypothesis and self-loop hypothesis, (d) reveals the empirical observation.
In this paper, six basic hypotheses are formulated:

  1. Uniform Hypothesis - user randomly select a page for next visit
  2. Page Consistent Hypothesis - user visits the same page in next step (due to pagination)
  3. Category Consistent Hypothesis - user visits page under the same category as current page
  4. User Consistent Hypothesis - a transition's target and source belong to the same user
  5. Folksonomy Consistent Hypothesis - user goes to a page by following folksonomy structure
  6. Semantic Navigation Hypothesis - user goes to a page which maintains semantic relations with current one


Three combined hypotheses are introduced:

  1. Folksonomy Consistent & Semantic Navigation Hypothesis
  2. User Consistent & Semantic Navigation Hypothesis
  3. User Consistent & Folksonomy Navigation Hypothesis


Experiment results: The above mentioned hypotheses are tested based on empirical dataset collected from the social tagging system Bibsonomy. Results show that (i) in overall, the combination of user consistent & semantic navigation hypothesis works best, and the second one is user consistent hypothesis; (ii) users show different browsing behaviors between within his/her resources and outside his/her resources - within navigations tend to be explained by semantic navigation hypothesis, while outside behaviors are likely to be following folksonomy structure; (iii) short-term and long-term users show different behaviors - short-term users are likely to follow semantic navigation while long-term users are prone to follow folksonomy structure.


References:
[1]  Singer, P., Helic, D., Hotho, A., Strohmaier, M.: HypTrails: A bayesian approach for comparing hypotheses about human trails on the Web. In: Proc. of the 24th WWW Conf. (2015)