The velocity of multimodal information shared on web has increased signi cantly. Many reranking approaches try to improve the performance of multimodal retrieval, however not in the direction of true relevancy of a multimodal object. Metropolis-Hastings (MH) is a method based on Monte Carlo Markov Chain (MCMC) for sampling from a distribution when traditional sampling methods such as transformation or inversion fail. If we assume this probability distribution as true relevancy of documents for an information need, in this paper we explore how leveraging our model with Metropolis-Hastings algorithm may help towards true relevancy in multimodal IR.
There are many challenges in multimodal information
retrieval. Mei et al. [
SIGIR Workshop on Graph Search and Beyond ’15 Santiago, Chile Published on CEUR-WS: http://ceur-ws.org/Vol-1393/. relevant patterns for a query. 4) Interactive Reranking : in this case a user can edit a part of the search results (to delete or to emphasize).
Graph-based methods for reranking are a subset of
Selfreranking category, in which a graph oriented search is
performed based on relations between objects. Mostly, related
work in this area is performed on images/videos with
similarity links between them [
In this paper, we explore the capability of our model to approach probabilistic IR for multimodal retrieval with the help of the MH algorithm. MH is based on MCMC and is used in cases where it is hard to sample from a probability distribution. Assuming the true probability distribution of relevancy of documents to the query as stationary distribution, utilizing MH we make a Markov-chain of documents which results in the same stationary distribution of probabilities. We conduct the experiments on ImageCLEF2011 Wikipedia collection as a multimodal collection. 2.
There are many e orts in multimodal retrieval in
combining textual and visual modalities. Martinent et al. [
The application of MH method in information retrieval, is
limited to search in peer-2-peer networks [
MH is one of the algorithms based on MCMC to obtain samples from a complex probability distribution (x). The goal is to draw samples form (x) where (x) = eK(x) . The normalizing variable K is unknown and hard to compute. Based on the jumping distribution matrix of W , MH algorithm generates a sequence from this distribution as follows: 1. Start with initial value x that (x) > 0 2. Using the current x value, sample a candidate point y from W (x; y). 3. The transition probability then is made according to (1) (2) P r(x; y) = W (x; y) (x; y) (x; y) = min e(y):W (y; x) ; 1
e(x):W (x; y) Note that (x; y) does not require knowledge of the normalizing constant because (y)= (x) drops it out. If it increases the density ( > 1), accept y and set the next sample xt = y. Repeat step 3. If it decreases the density, sample u from uniform (0,1). Accept if > u, else reject it.
In order to reach a unique equilibrium state for a
Markovchain, it should be ergodic, satisfying irreducibility (for any
state, the probability of getting there given any starting
point is more than zero) and aperiodicity (there is no rhythm
in which states can be reached given a starting point). There
may be di erent proposal distributions for MH. Two general
approaches are [
We de ne a graph-based model G = (V; E), in which V
is the set of information objects and their facets, and E
is the set of edges. By facet we mean inherent feature or
representation of an object (e.g., tf.idf facet of a document
or edge histogram of an image). Each object may have a
number of facets. We de ne four types of relations. Their
characteristics are discussed in detail in [
Part-of ( ): a speci c type of semantic relation, indicating an object as part of another object, e.g. an image in a document. The weight is 1 because of containment relation as an object part of another one. Similarity ( ): relation between the facets of two information objects. The weight is the similarity value between the facets.
Facet ( ): linking an object to its representation(s). It is a unidirectional relation from facet to the parent object. Weights are given by perceived information content of features, with respect to the query type.
Our scoring method consists of two steps: 1) In the rst step, we perform an initial search with Lucene and/or Lire result based on the facets. This provides us a set of activation nodes. 2) In the second step, using the initial result set of data objects (with normalized scores) as seeds, we exploit the graph structure and traverse it.
The model can perform both partial/whole facet retrieval. We may decide to search e.g. only based on query textual or visual facets, or based on all query facets. In practice, we make a form of late facet fusion by combination of di erent scores and giving one score to the parent information object. However, it is not in the traditional way of late fusion. Since we do not make the result rank list out of top ranked nodes. We initiate their scores in graph nodes and then start propagation. In our model, facet fusion is implicitly calculated by matrix multiplication and nal vector computation. 5.
We want to achieve a query dependent stationary distribution such that the probability in node x is proportional to the probability that this node is relevant to the query, and at any other node (non-relevant) the probability is zero. This is the (x) distribution from which we cannot directly sample. Instead, we have the e(x) which could be a relevance scoring function (e.g. a BM25 score between the data object xi and the query). MH would formally provide us with a method to sample from the probability distribution, if the approximate probability e is properly chosen.
We have the graph of di erent relations in the adjacency matrix W . Assuming the true relevancy of nodes to the query as (x), we de ne the ~(x) as relevance score value function (RSV ). A node (M) in the graph may be of any modality: Text (T), Image (I), Audio (A) or Video (V), and the query (Q) may be combination of di erent modalities. We de ne the relevance score value function (RSV ), as follows: M 2 fT; I; V; Ag
n M = [i=1Mfi
m Q = [j=1Qfj l = jfQf jQfi = Mfi gj RSV (Q; M ) =
l X norm(sim(Qfi ; Mfi )):wfi i=1 (3) where n is the number of facet types of the information object node, m is the number of facet types of the query, sim is the similarity function between two facets, norm is the normalizing function and wfi is the weight of facet fi for this query. We compute the similarity (sim) between l number of the same facets of this information object and the query, in which Qfi and Mfi are the value of corresponding facets. Usually the value of a facet is in the form of a feature vector. In case of no common facet, the sim function output is zero. Relevancy of an information object to a query should be calculated in accordance to other information objects. For this purpose we compute the similarity of all objects for each query facet and normalize. As we have a multimodal graph and in each step may visit a node with di erent modality, we require a normalized value to be able to compare the relevancy values.
Di erent modalities have di erent facets. Reaching nodes with the same modality of query examples, we have all the facets in common (e.g. an image query and an image node). Visiting nodes with di erent modality than query examples, we perform similarity for common facets. For instance, if we have an audio object and an image query, we can compare their textual facets (the tf.idf facet of image metadata and tf.idf facet of the audio tags or lyrics). 5.1
Irreducibility: To check irreducibility we should prove that our graph is connected. By adding di erent relations of , and , we have a connected graph. For this purpose, starting from top ranked results for a sample query we traverse the graph. In each step we visit new neighbours and continue until we see no more new nodes. The number of nodes seen in this traversal was the whole graph size. This observation, even for one query, indicates the connectivity of our graph.
Aperiodicity: Finding nodes from a starting point is not multiple of a number in our graph. We satisfy this constraint by construction.
Stochastic property: According to the weight de nition in Astera for links, the sum of weights on a row may be more than one. However, semantic ( ) and/or similarity ( ) links can be used in a normalized form, complying with stochastic property.
Transition Function in Astera According to MetropolisHasitngs algorithm, and Eq. 2 we sample from W (x; y) and accept the move with probability (x; y). This implies on how we de ne high-order transition probabilities after t steps: P rqt+1(x; y) = Pk
i=1 P rqt(x; zi)(zi; y) where q is the query, k is the number of common nodes z between x and y, and P rt is the transition probability of starting from x and moving t steps further.
Mixing Walsh divides the mixing chains in two categories
of poorly mixing and well mixing chains [
In principle, MH either accepts a jumping density of W (x; y) (when > 1) and keeps the value and moves forward, or modi es the weight with the factor of . The new value of this link for next step is W (x; y) . According to stochastic property, the sum of the weights of links of an edge is 1. In each step, when weights are adjusted by MH, the sum may get lower than 1. In this case the link is accepted with probability of < 1. The decreased value is given as self-transitivity value to the node, indicating staying in this state is preferred than choosing that speci c link. Performing this for many steps, loosens the links with less relevant neighbours and keeps the links with increasing relevancy neighbours. This way, MH may modify the weights in the direction of making a Markov chain which reaches to the true probability distribution.
To prevent poorly mixing, we start from di erent starting points according to standard search result for each facet. These points satisfy the condition of e(x) > 0 as it is the scored ranked result. 6.
We applied the ImageCLEF 2011 Wikipedia collection for imgae retrieval task. Each image has one metadata le that provides information about name, location, one or more associated parent documents in up to three languages (EN, DE and FR), and textual image annotations (i.e. caption, description and comment). The collection consists of 125,828 documents and 237,434 images. We parsed the image metadata and created nodes for all parent documents, images and corresponding facets. We created di erent relation types: the relation between parent documents and images (as part of the document), and relation between information objects and their facets. We use the 50 English query topics. 6.1
In the rst phase of our hybrid search, we use standard indexing results both for documents and images. The computed scores in both modalities are normalized per topic between (0,1) based on min-max method. Di erent indexings based on di erent facets are:
Text tf.idf facet: We utilize default Lucene indexer, based on tf.idf, as text facet.
Image textual annotation tf.idf facet (Metadata):
We use metadata information of the images caption,
comment and description), as image textual facets.
CEDD facet: For image facets, we selected the Color
and Edge Directivity Descriptor (CEDD) feature since
it is considered the best method to extract purely
visual results [
In the second phase, starting from standard indexed results, we conduct the graph search based on MH. In this instantiation of Astera, we use only links between the documents and images. We investigate adding and link types are in our future works. 6.2
To compute the transition matrix P r, we need to compute the (x; y) for each two neighbour nodes to update the weights. In this instantiation of Astera with ImageCLEF RSV (Q; I) = norm(sim(Qtf:idf ; Itf:idf )):wtf:idf + norm(sim(QCEDD; ICEDD)):wCEDD where and
RSV (Q; D) = norm(sim(Qtf:idf ; Dtf:idf )):wtf:idf (6)
The RSV value is computed based on normalized Lucene and LIRE similarity score for tf.idf and CEDD facet respectively. The wCEDD and wtf:idf are facet weights for this query. For each query, we perform this similarity computation in all three languages, separately for image metadata and documents. We take this value as relevancy value of each image/document for a speci c query. 6.3
We included text tf.idf and metadata tf.idf facets in this experiment. We start with top 20 similar documents and images (as activated nodes) based on these facets for each query, and traverse the graph from these 40 touch points, step by step in parallel. In each step, for node x and its neighbour y, we compute the (x; y), update the weight and continue to the next neighbour. This is performed in the form of matrix multiplications.
In Markov chain random walks, without MH algorithm,
we utilize matrix multiplication to simulate the walk in the
graph. The probability distribution after t steps is
calculated as at = a0 W t, where a0 is the starting scores and
at is the scores after t steps. However, leveraging MH, the
edge weights are a ected by (Eq. 1). This is a potential
problem for computing the updated transition matrix. The
reason is that, in each iteration, the matrix W is a ected
by which is a min function - W in rst iteration and
W in the second iteration. However, Hlynka et al. [
We compute the nal score as at = a0 P rt after t steps. This computation is needed for middle steps, since in ideal case the multiplication is performed many times until the matrix converges and in stationary distribution the nodes' probability are independent of starting scores in the graph. 2011 Wikipedia collection, we have images and documents node types. The query topic in this collection is multimodal. It is a combination of keywords and image examples with facet set of ftf:idf; CEDDg.
Based on any of these facets, we can start traversal in the graph. For example, if we start from similarity with metadata tf.idf results, we will have a set of images as starting points to make the traversal. In this instantiation of Astera, an image object (I) has two facets of ftf:idf; CEDDg. The common set of facets of l between the query and image is l = ftf:idf; CEDDg. Each image is connected to at least one parent document (D) through link. To compute the P r(I; D) = W (I; D) (I; D), we need the value, which is: (I; D) =
RSV (Q; D) W (D; I)
: RSV (Q; I) W (I; D)
We compare the results with/without using MH algorithm (Tables 1, 2). We did not get better result in our preliminary experiment with MH. The reason is dependency of a jump to the value of RSV (y)=RSV (x). The implemented RSV function for images is based on metadata facet. A large number of images are not retrieved in Lucene result for Metadata facet- we retrieve in the scale of 1000 images for each query, compared to having 274,000 images. We set the minimum value of retrieved scores (0.0001), as RSV value of visited images not in the Lucene results. We have observed that this approach biases a large number of images to very low score, which we assume to be the cause of low precision. Though, further experiments in this direction are needed 1. 7.
We presented a graph-based model for multimodal IR leveraging MH algorithm. The graph is enriched by extracted facets of information objects. Di erent modalities are treated equally thanks to faceted search. We proposed a generic relevancy function based on facet similarity of objects to the query. Leveraging this model, we have a platform, potential to investigate the a ect of di erent facets on performance, and burning in the matrix. We have the opportunity to examine query dependent traversal, as weights in the graph are a ected by relevancy of source and target nodes to the query. The preliminary results with MH did not improve the result. Many steps in the graph should be taken until the matrix burns in to the stationary distribution, which is in our future work. However, this experiment brings some issues to discuss: 1) How much the nal probability distribution is dependent on the chosen e(x)? 2) Is MH algorithm on graph-based collections an opportunity to compare the e ect of di erent ranking models? 3) How much expensive is this approach regarding the need of high number of transitions until the matrix burns in? 4) How do we satisfy stochastic property in multimodal graph with heterogeneous relation types? In principle, this property is beyond mathematically summing the weights to 1, but it goes back to the utility of di erent modalities as neighbours to the user. The di culty is whether these neighbours are equally useful to the user? 1The code of Astera is open-source and available at link: http://www.ifs.tuwien.ac.at/ sabetghadam/Astera.html st 0.135 0.135 0.123 0.120 0.1148 0.1104 0.106 0.27 0.27 0.23 0.22 0.18 0.17 0.14 0.125 0.125 0.113 0.1097 0.1091 0.107 0.08 0.229 0.229 0.188 0.184 0.173 0.156 0.13 0.151 0.151 0.148 0.133 0.113 0.111 0.108 0.158 0.158 0.138 0.134 0.124 0.113 0.115 0.135 0.135 0.1295 0.1163 0.1163 0.109 0.087 steps steps