View Single Post
  #3  
Old 07-11-2012, 02:03 AM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: How to calculate VC dimension for matrix factorization (Netflix-like) tasks

Assume that the input space to be all the entries in the M by N (binary) matrix, and each hypothesis is simply sign(P * Q) for two matrices of rank at most K. The following paper

http://ttic.uchicago.edu/~nati/Publi...kolaNIPS04.pdf

gives a combinatorial upper bound on the growth function, and thus the VC dimension is bounded by K(M+N)* some log factors. Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote