Transcript Nonnegative Shared Subspace Learning

Nonnegative Shared Subspace Learning
and
Its Application to Social Media Retrieval
Sunil Kumar Gupta, Dinh Phung, Brett Adams, Tran The Truyen, Svetha Venkatesh
Institute for Multi-sensor Processing & Content Analysis (IMPCA)
Curtin University of Technology, Perth, Australia
KDD 2010, Washington DC
28th July, 2010
Outline






Introduction
Motivation
Shared Subspace Learning
Social Media Retrieval
Experimental Results
Conclusion
Introduction

Social tags have the potential to improve search, personal organization
and have been instrumental in the rising popularity of social sharing sites
such as Del.icio.us, Flickr and YouTube.

However, these tags are often very subjective, ambiguous and incomplete
[17, 14] due to the lack of constraints during their creation.

The tag quality should be improved for better retrieval performance.
Problem
Aim
To improve tag-based search performance in social media by transferring
knowledge across related auxiliary sources.
Motivation

Tags in some tagging systems are cleaner.

Why? Because they are created with controlled vocabulary for different
purpose (e.g. object detection)

Can we do “knowledge-transfer” from these cleaner tagging systems to
improve search in noisy tagging systems?
Related Works
Flickr image and tags
LabelMe image and tags
hawaii
maui
hdr
tree
building
person
woman
tree
bench
window
roof
sidewalk
road
sky
cloud
Related works

Marlow et al.[17] study user tagging behaviour

Li et al. [14,15] present a method to learn tag relevance

Wang et al. [24] do content based processing and fuse with text-based retrieval results
Text Mining : NMF

NMF aims to factorize a nonnegative data matrix X as
X  FH , F  0, H  0
where
and usually,

X  M  N matrix
F  M  R matrix
H  R  N matrix
R  min M , N 
NMF is widely used in text mining applications due to its ability to find part-based
and intuitive representation.
Nonnegative Shared Subspace
Learning (JSNMF)
Let us represent the two datasets by X, Y with dimension MxN1 and MxN2 respectively and
write the decomposition as :

X  
W
|U
 H  FH
LabelMe
F
Y  
W
|
V L  GL
U
G
Optimize the cost function

 X  W | U H
min 
2
W ,U ,V , H , L 0
X

F

2
F
2
Y  W | V L F 



2
Y F


W
Flickr
V
Illustration of NMF and JS-NMF
Consider toy datasets X1 (shown in red) and X2 (shown
in blue) each having 2 clusters
Apply standard NMF to
determine 2 basis vectors
for each data
Treat both data similar by
augmenting them together
and use NMF with K = 3
Individual Basis
Vectors
Common Basis
Vector
Use JSNMF framework with
one shared vector
Social Media Retrieval
JSNMF based retrieval algorithm
Query set
(SQ)
Vocabulary
(D)
{Retrieved
items}
Construct query vector qx
using vocabulary D and SQ
Rank the similarities in
decreasing order
No. of items (N)
W ,U , H
Project qx on the subspace (qh)
qx  W | U qh
Compute cosine similarity between
query vector and the items in the
subspace
Experiments
Data collection

We created our dataset by crawling metadata for 50000 images (Flickr), 12000
videos (YouTube ) and used 7000 images (LabelMe).

To download data, we used a variety of concepts



Indoor (‘chair’, ‘computer’, ‘cup’, ‘door’, ‘desk’, ‘microwave’)
Outdoor (‘beach’, ‘boat’, ‘building’, ‘plane’, ‘ship’, ‘sky’, ‘tree’)
Generic (‘book’, ‘car’, ‘pen’, ‘person’, ‘phone’, ‘picture’, ‘window’).
Choice of Shared Subspace
Dimensionality (K)

Find the number of the common features (tags in our case) between the two datasets, say
Mxy.

Use “the rule of thumb” suggested by [K.V. Mardia et al 1979, Multivariate Analysis] as
K  M xy / 2
K

U
W
V

R1 
R2
Figure: Sharing Configuration
Choice of Shared Subspace
Dimensionality (K)

Another way to estimate K : supposedly, if subspaces spanned by W, U and V are
mutually-orthogonal then

K  rank X T Y


However, in our case, W, U and V are only approximately mutually-orthogonal,
suggesting that

K  rank X T Y

K

U
W
V

R1 
R2
Figure: Sharing Configuration
Effect of Shared Subspace
Dimensionality (K)
No Sharing
BASELINES
Baseline-I : NMF (No sharing)
Baseline-II : JSNMF with full-sharing
(Lin et al. [16])
RESULTS SUMMARY
Dataset
Baseline-I
Baseline-II
JSNMF
(with LabelMe)
Flickr
50%
46%
58%
YouTube
38%
36.5%
48%
Full Sharing
Flickr Retrieval Results
P@N, MAP and 11-point interpolated precision-recall results
(a) Precision-Scope and MAP results
for JSNMF, baseline-I (NMF) and
baseline-II (Fully Shared)
(b) 11-point interpolated precision
recall for JSNMF, baseline-I (NMF)
and baseline-II (Fully Shared)
YouTube Retrieval Results
P@N, MAP and 11-point interpolated precision-recall results
(a) Precision-Scope and MAP results
for JSNMF, baseline-I (NMF) and
baseline-II (Fully Shared)
(b) 11-point interpolated precision
recall for JSNMF, baseline-I (NMF)
and baseline-II (Fully Shared)
Conclusion

We presented a novel nonnegative shared subspace learning framework.

We demonstrated its application to improve tag-based image and video retrieval
in Flickr and YouTube respectively.

We empirically demonstrated that controlled sharing is crucial to avoid any
negative knowledge-transfer from auxiliary data sources.

Our JSNMF framework is generic and can be applied widely to carry out flexible
knowledge transfer from related data sources.
References
[1] http://code.google.com/apis/youtube/overview.html. Accessed in Oct, 2009.
[2] http://www.flickr.com/services/api/. Accessed in July, 2009.
[3] H.D. Abdulla, M. Polovincak, and V. Snasel. Search Results Clustering using Nonnegative Matrix Factorization (NMF).
ASONAM ’09, pages 320–323, July 2009.
[4] M.W. Berry and M. Browne. Email Surveillance using Non-negative Matrix Factorization. Computational & Mathematical
Organization Theory, 11(3):249–264, 2005.
[5] R. Caruana. Multitask learning. Machine Learning, 28(1):41–75,1997.
[6] A.P. Dempster, N.M. Laird, D.B. Rubin, et al. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of
the Royal Statistical Society. Series B (Methodological), 39(1):1–38, 1977.
[7] L. Fei-Fei, R. Fergus, and P. Perona. One-shot Learning of Object Categories. PAMI, 28(4):594–611, 2006.
[8] S.A. Golder and B.A. Huberman. Usage Patterns of Collaborative Tagging Systems. Journal of Information Science, 32(2):198,
2006.
[9] D.R. Hardoon, S. Szedmak, and J. Shawe-Taylor. Canonical Correlation Analysis: An Overview With Application To Learning
Methods. Neural Computation, 16(12):2639–2664, 2004.
[10] P.O. Hoyer. Non-negative Matrix Factorization with Sparseness Constraints. The Journal of Machine Learning Research,
5:1457– 1469, 2004.
[11] M.S. Kankanhalli and Y. Rui. Application Potential of Multimedia Information Retrieval. Proceedings of the IEEE,
96(4):712, 2008.
[12] J.R. Kettenring. Canonical Analysis of Several Sets of Variables. Biometrika, 58(3):433–451, 1971.
[13] D.D. Lee and H.S. Seung. Algorithms for Non-negative Matrix Factorization. In Advances in Neural Information Processing,
2000.
[14] X. Li, C. G. M. Snoek, and M.Worring. Learning Social Tag Relevance by Neighbour Voting. IEEE Transactions on
Multimedia, in press, 2009.
[15] X. Li, C.G.M. Snoek, and M. Worring. Annotating Images by Harnessing Worldwide User-tagged Photos. ICASSP. Taipei,
Taiwan, 2009.
References
[16] Y.R. Lin, H. Sundaram, M. De Choudhury, and A. Kelliher. Temporal Patterns in Social Media Streams: Theme Discovery
And Evolution Using Joint Analysis Of Content and Context. In ICME 2009, pages 1456–1459, 2009.
[17] C. Marlow, M. Naaman, D. Boyd, and M. Davis. Ht06, Tagging Paper, Taxonomy, Flickr, Academic Article, Toread.
Proceedings Of The Seventeenth Conference On Hypertext And Hypermedia, pages 31–40, 2006.
[18] S.J. Pan and Q. Yang. A Survey on Transfer Learning. Technical Report HKUST-CS08-08, Department of Computer Science
and Engineering, HKUST, Hong Kong, China, 2008.
[19] R. Raina, A. Battle, H. Lee, B. Packer, and A.Y. Ng. Self-taught Learning: Transfer Learning from Unlabeled Data.
Proceedings of the 24th International Conference on Machine Learning, page 766, 2007.
[20] B.C. Russell, A. Torralba, K.P. Murphy, andW.T. Freeman. Labelme: A Database and Web-based Tool for Image Annotation.
International Journal of Computer Vision, 77(1):157–173, 2008.
[21] G. Salton and C. Buckley. Term-weighting Approaches in Automatic Text Retrieval. Information Processing & Management,
24(5):513–523, 1988.
[22] F. Shahnaz, M.W. Berry, V.P. Pauca, and R.J. Plemmons. Document Clustering using Nonnegative Matrix Factorization.
Information Processing and Management, 42(2):373–386, 2006.
[23] B. Sigurbjörnsson and R. Van Zwol. Flickr Tag Recommendation based on Collective Knowledge. Proceeding of ACM
International World Wide Web Conference, 2008.
[24] C. Wang, F. Jing, L. Zhang, and H.J. Zhang. Scalable Search-based Image Annotation. Multimedia Systems, 14(4):205–220,
2008.
[25] X. Wang, C. Pal, and A. McCallum. Generalized Component Analysis for Text with Heterogeneous Attributes. Proceedings
of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 803, 2007.
[26] L. Wu, L. Yang, N. Yu, and X.S. Hua. Learning to Tag. Proceedings of the 18th International Conference on World Wide
Web, pages 361–370, 2009.
[27] Z.Wu, C.W. Cheng, and C. Li. Social and Semantics Analysis via Nonnegative Matrix Factorization. Proceedings of the 17th
International Conference on World Wide Web, 2008.