Personalized Image Search Summarization For Flicker Based on Ternary Semantic Analysis

Personalized Image Search Summarization For Flicker Based on Ternary Semantic Analysis

Mranmayi G. Katkar

ME-II Computer Engineering

Vidya Pratishthans College of Engineering, Baramati, University of Pune, India

Prof. Sheetal. A. Takale

Department of IT

Vidya Pratishthans College of Engineering, Baramati, University of Pune, India

AbstractBeing a photo sharing website Flicker allow users to annotate, comment, and share images. This leads to creation of huge amount of metadata that reflects the user relevance feedback. Personalization of image search is need of every image surfer. In order to provide search results that are closer to his/her interest, an approach to the problem of personalized image search summarization is proposed here. As there are three entities user, image and tag on photo sharing website, instead of taking binary relation between user-image, image-tag and user-tag, this approach considers the ternary relation among users, images, and tags. Since original annotations provided by user are not enough for preference mining, RMTF method is employed to predict the user-specific annotations. One query corresponds to number of tags in tag vocabulary forms a one-to-many relationship between query and tag, hence topic modeling is required to extract the latent topics(cluster of user- specific tags). The user query is mapped to the topic to generate set of query-words. Finally, the personalized image search is achieved by retrieving the images possessing query-word as an tag.

KeywordsHOSVD, Tensor, Tensor Factorization, Topic Modeling, Tag Refinement.

1. INTRODUCTION

   Personalized Image Search is need of every web surfer seeking for images of his/her interest. Many personalization strategies use past history of searcher as relevance feedback to improve the precision of system. Personalized search strategies usually use databases to store the search history, previously visited web pages, email id of the user to exploit the search intent. Major challenge face by these personalized search systems is 1)majority of queries to search engines are short and ambiguous , and different users may have completely different information needs and goals under the same query. 2)There exist different forms of metadata, such as descriptions, comments, and ratings so, how to model other metadata for a overall understanding is another challenge.

   To address the problem of generating the personalized search and recommending the tags for a given query by

   theuser, the proposed system exploits the ternary relation among user, image and tag. For a given user query, an personalized image search system tries to recommend the images that are closely revevant to his search intent. The personalized search approach in this paper considers the users preference for ranking the search results. The fundamental assumption is that users tagging actions reflects their personal relevance judgment. But the fact is that user-specified annotations are not sufficient for building their Preference Profile. So the task of annotation prediction is achieved using Tensor Factorization using HOSVD method. There are three entities in photo sharing websites User, Image and Tag respectively, which forms ternary relation between them. The users tagging patterns are as follows,

   Fig. 1 Tagging Data Pattern

   One image can pursue maximum of 75 tags. The set of tags for each user that are produced by Tensor Factorization using HOSVD method are considered as Tag Vocabulary for that user. One query may correspond to more than one tags in the tag vocabulary that means this may lead to one-to-many relation between user query and tags. Hence the mapping between the query and tags is achieved using User-Specific Topic Modeling, where user query is mapped to one topic from set of user-specific topics. If user u has a principle interest on topic j and term X has a high probability in topic j, when user searches X, the query will have a high proportion on users topic j.

2. LITERATURE SURVEY

   In recent years most of the work has been done on

   improving the web search. This section reviews the related work on personalized image search stratigies.

   1. Automated Analysis of Interests and Activities[5]: Here the information about the searcher is used to infer an implicit goal or intent. The search related information such as previously issued queries and previously visited Web pages, and on other information such as documents and email the user has read and created can be explored. The implicitly constructed user profile as a form of relevance feedback can achieve better performance than explicit relevance feedback and can improve on Web search. With this approach to personalization, there is no need for the user to specify or maintain a profile of interests.

      Drawback: Need to use a wide range of implicit user activities over a long period of time to develop an implicit user profile. This profile is used to rerank Web search results employing a relevance feedback framework.

   2. Personalized Search on Searchers Preference Prediction[3]: This personalized search model assists users in obtaining interested photos on Flickr, by exploiting the favorite marks of the searchers friends to predict the searchers preference on the returned photos. This model utilizes a co-clustering method to extract latent interest dimensions from users implicit interests, and employs a discriminative learning method to predict searchers preference on the returned photos. Drawback:

      Typically, users are interested in more than one field, and the searcher may share different interests with different friends. The variety of users implicit interests can be mined and encoded into the latent interest dimensions. Friends may contribute differently to searchers preference prediction according to the submitted query and the interest distribution.

   3. Personalized Search Based on Social Annotations[4]:

      This system explores the use of social annotations to improve web search.The web search optimized by using social annotations from the following two aspects: 1) Similarity ranking: The similarity between a query and a web page. For example, the top 5 annotations of Amazons homepage in Delicious are shopping, books, amazon, music and store, which depict the page or even the whole website exactly. These annotations provide a new metadata for the similarity calculation between a query and a web page. 2) Static ranking: The amount of annotations assigned to a page indicates the popularity of web pages using social annotations.

      Drawback: First, the user submitted queries may not match any social annotation. Second, many web pages may have no annotations. Annotation ambiguity is another problem concerned with Similarity Ranking, i.e., the similar terms to the query terms while fail to disambiguate terms that have more than one meanings. For example, ticket may refer to either airplane ticket or concert ticket, and terms with these two different meanings will be mixed up.

   4. Recommendations Based on Ternary Semantic Analysis[5]: Social tagging systems (STSs) can provide three different types of recommendations: They can recommend 1) tags to users, based on what tags other users have used for the same items, 2) items to users, based on tags they have in common with other similar users, and 3) users with common social interest, based on common tags on similar items. However, users may have different interests for an item, and

   items may have multiple facets. In this system data are modeled by a 3-

   order tenso, on which multiway latent semantic analysis and dimensionality reduction is performed using both the Higher Order Singular Value Decomposition (HOSVD) method and the Kernel SVD smoothing technique.

   Drawback: Need to apply different weighting methods for the initial construction of a tensor to improve the overall

   performance of web search. E. Capturing User Intention for One-Click Image Search[2]: It is difficult to interpret users intention only by query words and this leads to ambiguous and noisy search results which are far from satisfactory. Hence to overcome this problem an approach is proposed which requires the user to click on one query image with minimum effort and images from a pool retrieved by text- based search are re-ranked based on both visual and textual content.

   Drawback: User intention can not be well expressed by a single query image. the user may be interested in only part of the image. In those cases, more user interactions, such as labeling the regions that the user thinks are more important, have to be allowed. however more user burden has to be added.

3. IMPLEMENTATION DETAILS

   The proposed framework is organized into two stages, Offline stage and Online stage respectively.

   Offline Stage: In offline stage, the tagging data representing ternary relation among user-image-tag is collected from Flickr. The three-dimensional tensor is constructed from the collected ternary relation which is further given as input to RMTF method for generating user-specific annotation prediction. Then after the topic modeling is carried out to extract the user specific topics for user-specific tags which is the final outcome of the offline stage. The modules which comes under offline stage are as follows:

   RMTF Method: Performs Annotation Prediction for each user.

   Topic Modeling using PLSA: Generates User-Specific topics for each user.

   Online Stage: In online stage, when a user u submits a query q, q is mapped to one of the user-specific topic. Mapped topic is further used to generate the query-words. From the set of query-words, the images are retrieved from the dataset possessing query-word as tag which is the final outcome of online stage. The modules which comes under online stage are as follows. The user-specific query mapping: The user query is mapped to user-specific topic. Generation of query- words: The query-words are extracted from the mapped topic. Retrieve the images possessing query-word tag: The images having query-word tag are retrieved from tha database. The system architecture is as shown in Fig.3

   1. Tensor Factorization using HOSVD

      Tagging Data Collection: As there are three entities in Flickr namely user, image and tag, there exist ternary relation between user-image-tag only when user u have annotated image i with tag t which is represented using tensor as

      Y R|U|×|I|×|T|

      Where, |U|: Set of users, |I|: Set of images, |T|: Set of tags.

      The tensor would look as follows,

      Yu,i,t = 1, If User u have actually tagged image I with tag

      t

      unfolded matrix. The mode-3 unfolding columns of each slices become rows in unfolded matrix.The ranks of unfolded matrices is determined as follows,

      0, Otherwise

      Initial Tensor Construction: The initial tensor is constructed by inserting 1s in only those cells where user u has actually annotated image i with tag t, and 0s in other cells. For running example shown below in Fig. 5,

      the initial tensor looks as follows:

      Fig. 2. System Architecture

      Tensor Reduction Algorithm Input :Initial Tensor Y

      Output: Reconstructed Tensor Y

      1. Matrix Unfolding of Tensor y:

         Matrix Unfolding is a process of converting a tensor into matrix. In short it is a process of rearranging the elements of tensor. The matrix unfolding is done in all three modes, hence the resulting matrices are three Y1, Y2, Y3 respectively. While unfolding matrix in mode-1, the vertical slices of the initial tensor are arranged in one after another in matrix. The mode-2 unfolding rows of each slices become columns in

      2. Application of SVD on Each Mode: SVD is employed to generate the three matrices A1, A2, A3.

         Where, A1= Y1. Y 1T , A2= Y2. Y 2T , A3= Y3. Y 3T .

         SVD results to total 9 new matrices. where, the columns of U are nothing but Eigen values of A1. And Si is diagonal matrix, whose diagonal elements are square roots of the Eigen values of A1, arranged in descending order.

      3. Computing the Low-Rank Approximations:

         Here tensor is dimensionality reduced to extract the compact representation for image, tag and user, and at the same time reconstruct the user-image-tag ternary relations for annotation prediction. The Ci is the number of dimensions maintained for i-mode. The selection of C1, C2, and C3 determines the final dimensionality of the core tensor C. From the observations it is concluded that the values of C1, C2, and C3 lies between 40 to 100 percent of the sum of diagonal

         elements of Si. This percentage is also based on no. of users, no. of images

         and no. of tags respectively. Here in this running example the percentage of for determining C1, C2 and C3 is 80, 70 and 40 and values are C1=5, C2=4 and C3=2. This means the core tensor will be of rank C1 _ C2 _ C3. The resulting tensors after low rank approximation are shown below.

      4. The Core Tensor C Construction:

         The core tensor C governs the interactions among user, item and tag entities. The core tensor is built by the product of initial tensor Y and the mode products of three matrices U, I and T.

         Where, (U(1)c1 )T , (I(2) c2 )T , (T(3) c3 )T are shown in fig. 6, here the value of C1 is 5 the resulting (U(1) c1 )T consists of 5 rows, value of C2 is 4 the resulting (I(2) c2 )T consists of 4 rows, and value of C3 is 2 the resulting (U(3) c3 )T consists of 2 rows respectively. The resulting core tensor for running example is shown below.

      5. The tensor Y Construction:

         Finally Y is built by the product of the core tensor C and

         the mode products of the three matrices (U(1)c1 )T , (I(2)c2

         )T and (T(3)c3 )T which can be used as users potential annotations.

   2. Topic Modeling using PLSA

      One query is mapped to number of tags in the tag vocabulary which leads to one-to-many relationship, therefore topic modeling is applied to build topic space for each user to exploit this one-to-many relationship. The Probabilistic Latent Semantic Analysis(PLSA) algorithm is employed to achieve the topic modeling which extracts the user-specific topics from user-specific corpus. Corpus is collection of M documents denoted by D={d1, d2 …..dM }. A document is a sequence of N words denoted by d = {w1, w2, .., wN}where wN is the nth word in the sequence. A word is the basic unit of discrete data, defined to be an item from a vocabulary indexed by f1,…, Vg PLSA makes several assumptions to define the model. P(zk |dm): Given a document dm in the corpus, we are able to infer the topic zk of the document P(wv |zk): Given a topic, we are able to infer which word wv is likely to appear P(dm, wv, zk ): Joint probability of observing a word in the document.

      Algorithm:

      Input: Document-Term matrix. Where, M: No of Documents.

      {d1, d2,…… dM} V: No of Words in Tag Vocabulary. {w1, w2, ……… wV }

      Output:

      K-topics. {topic1, topic2….topick }PLSA aims at finding the following values, The probability that documentn appears in topicn denoted by P(dm|zk) and the probability that termn appears in topicn denoted by P(wv|zk). Iterate until convergence For d=1 to M, For z =1 to K, For w=1:V

      Where,

      After iterative calculation of probability values, the topics extracted are as follows:

   3. User-Specific Query Mapping.

   In the online stage, when user u submits a query q, the query is mapped to one of the iser-specific topics.And set of query-words are generated from that topic.

   Generate Personalized rnked List by employing ranking function over Query distribution over topics and topic- sensitive user preferences.

4. RESULTS AND DATASET

   1. Read the no. of Users, images, Tags:

      To understand the tagging pattern, three-dimensional tensor is constructed. The tensor can be only initialized if no. of users, images, and tags are known.

   2. User Specified Tags: Once the three-dimensional tensor is constructed, next task is to initialize it. Initializing the tensor meaning reflecting the user-specified tagging pattern.

   3. Predicted Annotations: After applying tensor reduction algorithm the predicted annotations are generated.

   We perform the experiments on a large-scale web image dataset, NUS-WIDE. It contains 269 648 images with 5018 unique tags collected from Flickr. We assumed the user IDs.

5. CONCLUSION

   1. Effectively utilizing the rich user metadata in the social sharing websites for personalized search is challenging as well as significant.

   2. The proposed framework exploit the users social activities for personalized image search, such as annotations and the participation of interest groups.

   3. The query relevance and user preference are simultaneously

      integrated into the final rank list

   4. Experiments on a large-scale Flickr dataset show that the proposed framework greatly outperforms the baseline.

6. ACKNOWLEDGEMENT

This is to acknowledge and thank all the individuals who played defining role in shaping this IJERT paper.. Without their Coordination, guidance and reviewing this task could not be completed alone. I avail this opportunity to express my deep sense of gratitude and whole hearted thanks to my guide Prof. S. A. Takale madam for giving her valuable guidance, inspiration and encouragement to embark this paper. Prof. S.

A. Takale madam gave me all the freedom I needed for this project. This project being conceptual one needed a lot of support from my guide so that I could achieve what I was set out to get. I also take great pleasure in thanking Prof. S. S. Nandgaonkar for providing appropriate guidance. I would personally like to thank Prof. G. J. Chhajed, Head of Computer Dept. at Vidya Pratistaisthans Collage of Engineering (VPCOE), and our Honble principal Dr. S. B. Deosarkar sir who creates a healthy environment for all of us to learn in best possible way.

REFERENCES

1. Jitao Sang, Changsheng Xu, Senior Member, IEEE, and Dongyuan Lu, Learn to Personalized Image Search From the Photo Sharing Websites, IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 14, NO. 4, AUGUST 2012

2. Xiaoou Tang, Fellow, IEEE, Ke Liu, Jingyu Cui, Student Member, IEEE, Fang Wen, Member, IEEE and Xiaogang Wang, Member,IEEE,IntentSearch: Capturing User Intention for One-Click Internet Image Search IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE VOL.34 NO.7 YEAR 2012

3. Dongyuan Lu, Qiudan Li, Personalized Search on Flickr based on Searchers Preference Prediction WWW 2011 Poster March 28April 1, 2011, Hyderabad, India

4. P. Symeonidis, A. Nanopoulos, and Y. Manolopoulos, A unified framework for providing recommendations in social tagging systems based on ternary semantic analysis, IEEE Trans. Knowl. Data Eng., vol. 22, no. 2, pp. 179192, Feb. 2010.

5. Panagiotis Symeonidis, Alexandros Nanopoulos, Yannis ManolopoulosTag Recommendations based on Tensor Dimensionality eduction, RecSys08, October 2325, 2008, Lausanne, Switzerland. Copyright 2008 ACM 978-1-60558- 093- 7/08/10

6. Panagiotis Symeonidis, Maria Ruxanda, Alexandros Nanopoulos, Yannis Manolopoulos, TERNARY SEMANTIC ANALYSIS OF SOCIAL TAGS FOR PERSONALIZED MUSIC RECOMMENDATION