nips nips2013 nips2013-113 knowledge-graph by maker-knowledge-mining

113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors

Source: pdf

Author: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu

Abstract: Tensor completion from incomplete observations is a problem of signiﬁcant practical interest. However, it is unlikely that there exists an efﬁcient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Speciﬁcally, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from O(nr log2 (n)) observations. For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative ﬁltering task and obtain state-of-the-art results. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Tensor completion from incomplete observations is a problem of signiﬁcant practical interest. [sent-6, score-0.213]

2 However, it is unlikely that there exists an efﬁcient algorithm with provable guarantee to recover a general tensor from a limited number of observations. [sent-7, score-0.521]

3 In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. [sent-8, score-0.804]

4 Speciﬁcally, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from O(nr log2 (n)) observations. [sent-9, score-1.291]

5 For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. [sent-10, score-0.266]

6 Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. [sent-11, score-0.345]

7 1 Introduction Many tasks of recommender systems can be formulated as recovering an unknown tensor (multiway array) from a few observations of its entries [17, 26, 25, 21]. [sent-13, score-0.6]

8 Moreover, there are several theoretical developments that guarantee exact recovery of most low-rank matrices from partial observations using nuclear norm minimization [8, 5]. [sent-15, score-0.601]

9 These results seem to suggest a promising direction to solve the general problem of tensor recovery. [sent-16, score-0.428]

10 However, there are inevitable obstacles to generalize the techniques for matrix completion to tensor recovery, since a number of fundamental computational problems of matrix is NP-hard in their tensorial analogues [10]. [sent-17, score-0.689]

11 For instance, H˚ stad showed that it is NP-hard to compute the rank of a a given tensor [9]; Hillar and Lim proved the NP-hardness to decompose a given tensor into sum of rank-one tensors even if a tensor is fully observed [10]. [sent-18, score-1.668]

12 The existing evidence suggests that it is very unlikely that there exists an efﬁcient exact recovery algorithm for general tensors with missing entries. [sent-19, score-0.636]

13 Therefore, it is natural to ask whether it is possible to identify a useful class of tensors for which we can devise an exact recovery algorithm. [sent-20, score-0.636]

14 In this paper, we focus on pairwise interaction tensors, which have recently demonstrated strong performance in several recommendation applications, e. [sent-21, score-0.549]

15 Pairwise interaction tensors are a special class of general tensors, which directly model the pairwise interactions between different attributes. [sent-24, score-0.781]

16 1 The existing recovery algorithms for pairwise interaction tensor use local optimization methods, which do not guarantee the recovery performance [18, 19]. [sent-27, score-1.567]

17 In this paper, we design efﬁcient recovery algorithms for pairwise interaction tensors with rigorous guarantee. [sent-28, score-1.09]

18 For noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. [sent-30, score-0.266]

19 In the proof of our main results, we reformulated the recovery problem as a constrained matrix completion problem with a special observation operator. [sent-31, score-0.547]

20 [8] have showed that the nuclear norm heuristic can exactly recover low rank matrix from a sufﬁcient number of observations of an orthogonal observation operator. [sent-33, score-0.399]

21 We believe that our technique can be generalized to handle other matrix completion problem with non-orthogonal observation operators. [sent-37, score-0.206]

22 Moreover, we extend existing singular value thresholding method to develop a simple and scalable algorithm for solving the recovery problem in both exact and noisy cases. [sent-38, score-0.491]

23 Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. [sent-39, score-0.345]

24 2 Recovering pairwise interaction tensors In this section, we ﬁrst introduce the matrix formulation of pairwise interaction tensors and specify the recovery problem. [sent-41, score-1.926]

25 Then we discuss the sufﬁcient conditions on pairwise interaction tensors for which an exact recovery would be possible. [sent-42, score-1.131]

26 After that we formulate the convex program for solving the recovery problem and present our theoretical results on the sample bounds for achieving an exact recovery. [sent-43, score-0.461]

27 In addition, we also show a quadratically constrained convex program is stable for the recovery from noisy observations. [sent-44, score-0.564]

28 The original formulation of pairwise interaction tensors by Rendle et al. [sent-46, score-0.781]

29 (1), in which each entry of a tensor is the sum of inner products of feature vectors. [sent-48, score-0.428]

30 (1) as follows Tijk = Aij + Bjk + Cki , (a) (a) for all (i, j, k) ∈ [n1 ] × [n2 ] × [n3 ], (b) (b) (c) (c) where we set Aij = ui , vj , Bjk = uj , vk , and Cki = uk , vi Clearly, matrices A, B and C are rank r1 , r2 and r3 matrices, respectively. [sent-52, score-0.225]

31 We call tensor T ∈ Rn1 ×n2 ×n3 a pairwise interaction tensor, which is denoted as T = Pair(A, B, C), if T obeys Eq. [sent-54, score-0.948]

32 In the rest of this paper, we will exclusively use the matrix formulation of pairwise interaction tensors. [sent-57, score-0.55]

33 Suppose we have partial observations of a pairwise interaction tensor T = Pair(A, B, C). [sent-59, score-0.985]

34 Our goal is to recover matrices A, B, C and therefore the entire tensor T from exact or noisy observations of {Tijk }(ijk)∈Ω . [sent-62, score-0.722]

35 Before we proceed to the recovery algorithm, we ﬁrst discuss when the recovery is possible. [sent-63, score-0.618]

36 The original recovery problem for pairwise interaction tensors is illposed due to a uniqueness issue. [sent-65, score-1.09]

37 In fact, for any pairwise interaction tensor T = Pair(A, B, C), 1 For simplicity, we only consider three-way tensors in this paper. [sent-66, score-1.209]

38 This ambiguity prevents us to recover A, B, C even if T is fully observed, since it is entirely possible to recover A , B , C instead of A, B, C based on the observations. [sent-71, score-0.134]

39 In order to avoid this obstacle, we construct a set of constraints such that, given any pairwise interaction tensor Pair(A, B, C), there exists unique matrices A , B , C satisfying the constraints and obeys Pair(A, B, C) = Pair(A , B , C ). [sent-72, score-0.994]

40 For any pairwise interaction tensor T = Pair(A, B, C), there exists unique A ∈ SA , B ∈ SB , C ∈ SC such that Pair(A, B, C) = Pair(A , B , C ) where we deﬁne SB = {M ∈ Rn2 ×n3 : 1T M = 0T },SC = {M ∈ Rn3 ×n1 : 1T M = 0T } and SA = {M ∈ Rn1 ×n2 : 1T M = 1 T n2 1 M1 1T }. [sent-75, score-0.923]

41 It is easy to see that recovering a pairwise tensor T = Pair(A, 0, 0) is equivalent to recover the matrix A from a subset of its entries. [sent-79, score-0.845]

42 Therefore, the recovery problem of pairwise interaction tensors subsumes matrix completion problem as a special case. [sent-80, score-1.296]

43 Previous studies have conﬁrmed that the incoherence condition is an essential requirement on the matrix in order to guarantee a successful recovery of matrices. [sent-81, score-0.426]

44 Let M = UΣVT be the singular value decomposition of a rank r matrix M. [sent-83, score-0.216]

45 It is well known the recovery is possible only if the matrix is (µ0 , µ1 )-incoherent for bounded µ0 , µ1 (i. [sent-88, score-0.364]

46 Since the matrix completion problem is reducible to the recovery problem for pairwise interaction tensors, our theoretical result will inherit the incoherence assumptions on matrices A, B, C. [sent-90, score-1.092]

47 We show that, under the incoherence conditions, the above nuclear norm minimization method successful recovers a pairwise interaction tensor T when the number of observations m is O(nr log2 n) with high probability. [sent-95, score-1.138]

48 Let T ∈ Rn1 ×n2 ×n3 be a pairwise interaction tensor T = Pair(A, B, C) and A ∈ SA , B ∈ SB , C ∈ SC as deﬁned in Proposition 1. [sent-97, score-0.923]

49 Under this assumption on the observations, we derive the error bound of the following quadratically-constrained convex program, which recover T from the noisy observations. [sent-106, score-0.191]

50 [19] proposed pairwise interaction tensors as a model used for tag recommendation. [sent-120, score-0.832]

51 [18] applied pairwise interaction tensors in the sequential analysis of purchase data. [sent-122, score-0.781]

52 In both applications, their methods using pairwise interaction tensor demonstrated excellent performance. [sent-123, score-0.923]

53 However, their algorithms are prone to local optimal issues and the recovered tensor might be very different from its true value. [sent-124, score-0.489]

54 In contrast, our main results, Theorem 1 and Theorem 2, guarantee that a convex program can exactly or accurately recover the pairwise interaction tensors from O(nr log2 (n)) observations. [sent-125, score-0.985]

55 In this sense, our work can be considered as a more effective way to recover pairwise interaction tensors from partial observations. [sent-126, score-0.848]

56 In practice, various tensor factorization methods are used for estimating missing entries of tensors [12, 20, 1, 26, 16]. [sent-127, score-0.786]

57 In addition, inspired by the success of nuclear norm minimization heuristics in matrix completion, several work used a generalized nuclear norm for tensor recovery [23, 24, 15]. [sent-128, score-1.026]

58 However, these work do not guarantee exact recovery of tensors from partial observations. [sent-129, score-0.662]

59 However, these solvers become prohibitively slow for pairwise interaction tensors larger than 100 × 100 × 100. [sent-135, score-0.781]

60 In order to apply the recover algorithms on large scale pairwise interaction tensors, we use singular value thresholding (SVT) algorithm proposed recently by Cai et al. [sent-136, score-0.625]

61 We ﬁrst discuss the SVT algorithm for solving the exact completion problem Eq. [sent-138, score-0.192]

62 It is easy −1/2 −1/2 −1/2 to see that the recovered tensor is given by Pair(n3 X, n1 Y, n2 Z), where X, Y, Z is the 4 optimal solution of Eq. [sent-142, score-0.489]

63 We can show that our constrained version of shrinkage operators can also be calculated using singular value decompositions of column centered matrices. [sent-170, score-0.192]

64 We refer interested readers to [3] for The optimization problem for noisy completion Eq. [sent-180, score-0.229]

65 yk sk = PK yk−1 sk−1 +δ ek − −1/2 X, n1 −1/2 Y, n2 Z)) , ˆ where PΩ (T ) is the noisy observations and the cone projection operator PK can be explicitly computed by  (x, t) if x ≤ t,  x +t (x, x ) if − x ≤ t ≤ x , PK : (x, t) → 2 x (0, 0) if t ≤ − x . [sent-184, score-0.35]

66 By iterating between Step (1) and Step (2n) and selecting a sufﬁciently large τ , the algorithm generates a sequence of {Xk , Yk , Zk } that converges to a nearly optimal solution to the noisy completion program Eq. [sent-185, score-0.294]

67 Previously, we showed that the computation of 1 shrinkage operators requires a SVD of a column centered matrix center(M) − n1 11T X, which is the sum of a sparse matrix M and a rank-one matrix. [sent-191, score-0.207]

68 Further, for an appropriate choice of τ , {Xk , Yk , Zk } turned out to be low rank matrices, which matches the observations in the original SVT algorithm [3]. [sent-195, score-0.16]

69 We can see that, in sum, the overall complexity per iteration of the recovery algorithm is O(r(n + m)). [sent-200, score-0.309]

70 We uniformly sampled a subset Ω of m entries and reveal them to the recovery algorithm. [sent-211, score-0.343]

71 Finally, we set the parameters τ, δ of the exact √ recovery algorithm by τ = 10 n1 n2 n3 and δ = 0. [sent-213, score-0.35]

72 White denotes exact recovery in all 10 experiments, and black denotes failure for all experiments. [sent-220, score-0.35]

73 In this simulation, we show the recovery performance with respect to noisy data. [sent-235, score-0.387]

74 For each entry (i, j, k) ∈ Ω, we simulated the noisy observation Tijk = Tijk + ijk , where 2 ˆ ijk is a zero-mean Gaussian random variable with variance σn . [sent-239, score-0.278]

75 Then, we revealed {Tijk }(ijk)∈Ω to the noisy recovery algorithm and collect the recovered matrix X, Y, Z. [sent-240, score-0.503]

76 The error of recovery result is measured by ( X − A F + Y − B F + Z − C F )/( A F + B F + C F ). [sent-241, score-0.309]

77 Table 1(b) indicates that the recovery is not reliable when we have too few observations, while the performance of the algorithm is much more stable for a sufﬁcient number of observations around four times of the degree of freedom. [sent-286, score-0.436]

78 Table 1(c) shows that the recovery error is not affected much by the rank, as the number of observations scales with the degree of freedom in our setting. [sent-287, score-0.435]

79 In order to demonstrate the performance of pairwise interaction tensor on real world applications, we conducted experiments on the Movielens dataset. [sent-289, score-0.923]

80 We randomly select 10% ratings as test set and use the rest of the ratings as training set. [sent-293, score-0.132]

81 In the end, we obtained a tensor T of size 6040 × 3706 × 36, in which the axes corresponded to user, movie and timestamp respectively, with 0. [sent-294, score-0.539]

82 We applied the noisy recovery algorithm on the training set. [sent-296, score-0.387]

83 Following previous studies which applies SVT algorithm on movie recommendation datasets [11], we used a pre-speciﬁed truncation level r for computing SVD in each iteration, i. [sent-297, score-0.193]

84 Therefore, the rank of recovered matrices are at most r. [sent-300, score-0.205]

85 We compared our algorithm with noisy matrix completion method using standard SVT optimization algorithm [3, 4] to the same dataset while ignore the time information. [sent-302, score-0.284]

86 Here we can regard the noisy matrix completion algorithm as a special case of the recover a pairwise interaction tensor of size 6040 × 3706 × 1, i. [sent-303, score-1.274]

87 We also noted that the training tensor had more than one million observed entries and 80 millions total entries. [sent-306, score-0.462]

88 This scale made a number of tensor recovery algorithms, for example Tucker decomposition and PARAFAC [12], impractical to apply on the dataset. [sent-307, score-0.737]

89 In contrast, our recovery algorithm took 2430 seconds to ﬁnish on a standard workstation for truncation level r = 100. [sent-308, score-0.369]

90 The empirical result of Figure 2(a) suggests that, by incorporating the temporal information, pairwise interaction tensor recovery algorithm consistently outperformed the matrix completion method. [sent-310, score-1.483]

91 Interestingly, we can see that, for most parameter settings in Figure 2(b), our algorithm recovered a rank 2 matrix Y representing the change of movie popularity over time and a rank 15 matrix Z that encodes the change of user interests over time. [sent-311, score-0.486]

92 861 (quote from Figure 7 of the paper) result of 30-dimensional Bayesian Probabilistic Tensor Factorization (BPTF) on the same dataset, where the authors predict the ratings by factorizing a 6040 × 3706 × 36 tensor using BPTF method [26]. [sent-315, score-0.52]

93 We may attribute the performance gain to the modeling ﬂexibility of pairwise interaction tensor and the learning guarantees of our algorithm. [sent-316, score-0.923]

94 5 Conclusion In this paper, we proved rigorous guarantees for convex programs for recovery of pairwise interaction tensors with missing entries, both in the absence and in the presence of noise. [sent-330, score-1.162]

95 In the noiseless case, simulations showed that the exact recovery almost always succeeded if the number of observations is a constant time of the degree of freedom, which agrees asymptotically with the theoretical result. [sent-333, score-0.514]

96 In the noisy case, the simulation results conﬁrmed that the stable recovery algorithm is able to reliably recover pairwise interaction tensor from noisy observations. [sent-334, score-1.516]

97 Our results on the temporal movie recommendation application demonstrated that, by incorporating the temporal information, our algorithm outperforms conventional matrix completion and achieves state-of-the-art results. [sent-335, score-0.429]

98 Tensor completion for estimating missing values in visual data. [sent-385, score-0.151]

99 Learning optimal ranking with tensor factorization for tag recommendation. [sent-391, score-0.517]

100 Non-negative tensor factorization with applications to statistics and computer vision. [sent-400, score-0.466]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('tensor', 0.428), ('recovery', 0.309), ('tensors', 0.286), ('tijk', 0.26), ('pairwise', 0.25), ('interaction', 0.245), ('completion', 0.151), ('sb', 0.144), ('sa', 0.138), ('sc', 0.133), ('yk', 0.125), ('bjk', 0.118), ('cki', 0.118), ('rendle', 0.118), ('shrinka', 0.118), ('shrinkb', 0.118), ('svt', 0.112), ('ijk', 0.1), ('rank', 0.098), ('svd', 0.087), ('nuclear', 0.086), ('shrinkc', 0.079), ('movie', 0.079), ('noisy', 0.078), ('pair', 0.074), ('movielens', 0.069), ('recover', 0.067), ('ratings', 0.066), ('program', 0.065), ('singular', 0.063), ('zk', 0.062), ('observations', 0.062), ('aij', 0.061), ('recovered', 0.061), ('truncation', 0.06), ('svdpackc', 0.059), ('yjk', 0.059), ('zki', 0.059), ('rmse', 0.058), ('shrinkage', 0.058), ('matrix', 0.055), ('recommendation', 0.054), ('xk', 0.053), ('tag', 0.051), ('ek', 0.049), ('emmanuel', 0.048), ('nr', 0.047), ('matrices', 0.046), ('convex', 0.046), ('recovering', 0.045), ('steffen', 0.045), ('temporal', 0.045), ('vt', 0.041), ('exact', 0.041), ('user', 0.04), ('ai', 0.04), ('lars', 0.039), ('collaborative', 0.039), ('cuhk', 0.039), ('hillar', 0.039), ('rpit', 0.039), ('operators', 0.039), ('factorization', 0.038), ('operator', 0.036), ('incoherence', 0.036), ('reformulate', 0.036), ('agrees', 0.036), ('bptf', 0.035), ('psa', 0.035), ('recoverability', 0.035), ('succeeded', 0.035), ('entries', 0.034), ('stable', 0.034), ('freedom', 0.033), ('center', 0.032), ('ua', 0.032), ('ryota', 0.032), ('timestamp', 0.032), ('alexandros', 0.032), ('hisashi', 0.032), ('kohei', 0.032), ('constrained', 0.032), ('norm', 0.031), ('degree', 0.031), ('recommender', 0.031), ('xij', 0.029), ('personalized', 0.029), ('tamara', 0.029), ('uj', 0.028), ('simulation', 0.027), ('vk', 0.027), ('factorizing', 0.026), ('movies', 0.026), ('vi', 0.026), ('pk', 0.026), ('absence', 0.026), ('guarantee', 0.026), ('obeys', 0.025), ('hayashi', 0.025), ('kolda', 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000005 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors

Author: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu

2 0.41765621 11 nips-2013-A New Convex Relaxation for Tensor Completion

Author: Bernardino Romera-Paredes, Massimiliano Pontil

Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves signiﬁcantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable. 1

3 0.37445924 179 nips-2013-Low-Rank Matrix and Tensor Completion via Adaptive Sampling

Author: Akshay Krishnamurthy, Aarti Singh

Abstract: We study low rank matrix and tensor completion and propose novel algorithms that employ adaptive sampling schemes to obtain strong performance guarantees. Our algorithms exploit adaptivity to identify entries that are highly informative for learning the column space of the matrix (tensor) and consequently, our results hold even when the row space is highly coherent, in contrast with previous analyses. In the absence of noise, we show that one can exactly recover a n ⇥ n matrix of rank r from merely ⌦(nr3/2 log(r)) matrix entries. We also show that one can recover an order T tensor using ⌦(nrT 1/2 T 2 log(r)) entries. For noisy recovery, our algorithm consistently estimates a low rank matrix corrupted with noise using ⌦(nr3/2 polylog(n)) entries. We complement our study with simulations that verify our theory and demonstrate the scalability of our algorithms. 1

4 0.34286919 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors

Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma

Abstract: In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efﬁciency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efﬁcient and effective than previous work. The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms “RASL” and “TILT” can be viewed as two special cases of our work, and yet each only performs part of the function of our method.

5 0.29696161 155 nips-2013-Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition

Author: Tzu-Kuo Huang, Jeff Schneider

Abstract: Learning dynamic models from observed data has been a central issue in many scientiﬁc studies or engineering tasks. The usual setting is that data are collected sequentially from trajectories of some dynamical system operation. In quite a few modern scientiﬁc modeling tasks, however, it turns out that reliable sequential data are rather difﬁcult to gather, whereas out-of-order snapshots are much easier to obtain. Examples include the modeling of galaxies, chronic diseases such Alzheimer’s, or certain biological processes. Existing methods for learning dynamic model from non-sequence data are mostly based on Expectation-Maximization, which involves non-convex optimization and is thus hard to analyze. Inspired by recent advances in spectral learning methods, we propose to study this problem from a different perspective: moment matching and spectral decomposition. Under that framework, we identify reasonable assumptions on the generative process of non-sequence data, and propose learning algorithms based on the tensor decomposition method [2] to provably recover ﬁrstorder Markov models and hidden Markov models. To the best of our knowledge, this is the ﬁrst formal guarantee on learning from non-sequence data. Preliminary simulation results conﬁrm our theoretical ﬁndings. 1

6 0.26325485 74 nips-2013-Convex Tensor Decomposition via Structured Schatten Norm Regularization

7 0.22141899 203 nips-2013-Multilinear Dynamical Systems for Tensor Time Series

8 0.16948618 281 nips-2013-Robust Low Rank Kernel Embeddings of Multivariate Distributions

9 0.14111066 307 nips-2013-Speedup Matrix Completion with Side Information: Application to Multi-Label Learning

10 0.13686399 185 nips-2013-Matrix Completion From any Given Set of Observations

11 0.1249911 108 nips-2013-Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion

12 0.12290819 263 nips-2013-Reasoning With Neural Tensor Networks for Knowledge Base Completion

13 0.11608377 254 nips-2013-Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms

14 0.10000037 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

15 0.099261411 353 nips-2013-When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity

16 0.095214799 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

17 0.094940588 286 nips-2013-Robust learning of low-dimensional dynamics from large neural ensembles

18 0.092637964 222 nips-2013-On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization

19 0.090372361 306 nips-2013-Speeding up Permutation Testing in Neuroimaging

20 0.087452553 354 nips-2013-When in Doubt, SWAP: High-Dimensional Sparse Recovery from Correlated Measurements

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.207), (1, 0.132), (2, 0.172), (3, 0.402), (4, -0.022), (5, -0.347), (6, 0.077), (7, -0.07), (8, 0.13), (9, 0.05), (10, -0.017), (11, -0.067), (12, -0.013), (13, 0.004), (14, -0.039), (15, -0.021), (16, -0.068), (17, -0.049), (18, 0.0), (19, 0.02), (20, 0.003), (21, 0.044), (22, -0.066), (23, -0.018), (24, -0.042), (25, 0.038), (26, 0.007), (27, 0.0), (28, 0.042), (29, -0.017), (30, 0.052), (31, 0.047), (32, 0.026), (33, 0.007), (34, 0.016), (35, -0.02), (36, 0.048), (37, -0.01), (38, -0.057), (39, -0.028), (40, -0.03), (41, -0.02), (42, 0.05), (43, 0.011), (44, 0.08), (45, 0.009), (46, 0.02), (47, -0.025), (48, -0.016), (49, 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96329069 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors

Author: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu

2 0.9296301 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors

Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma

3 0.90934855 11 nips-2013-A New Convex Relaxation for Tensor Completion

Author: Bernardino Romera-Paredes, Massimiliano Pontil

4 0.84376419 74 nips-2013-Convex Tensor Decomposition via Structured Schatten Norm Regularization

Author: Ryota Tomioka, Taiji Suzuki

Abstract: We study a new class of structured Schatten norms for tensors that includes two recently proposed norms (“overlapped” and “latent”) for convex-optimizationbased tensor decomposition. We analyze the performance of “latent” approach for tensor decomposition, which was empirically found to perform better than the “overlapped” approach in some settings. We show theoretically that this is indeed the case. In particular, when the unknown true tensor is low-rank in a speciﬁc unknown mode, this approach performs as well as knowing the mode with the smallest rank. Along the way, we show a novel duality result for structured Schatten norms, which is also interesting in the general context of structured sparsity. We conﬁrm through numerical simulations that our theory can precisely predict the scaling behaviour of the mean squared error. 1

5 0.84327888 203 nips-2013-Multilinear Dynamical Systems for Tensor Time Series

Author: Mark Rogers, Lei Li, Stuart Russell

Abstract: Data in the sciences frequently occur as sequences of multidimensional arrays called tensors. How can hidden, evolving trends in such data be extracted while preserving the tensor structure? The model that is traditionally used is the linear dynamical system (LDS) with Gaussian noise, which treats the latent state and observation at each time slice as a vector. We present the multilinear dynamical system (MLDS) for modeling tensor time series and an expectation–maximization (EM) algorithm to estimate the parameters. The MLDS models each tensor observation in the time series as the multilinear projection of the corresponding member of a sequence of latent tensors. The latent tensors are again evolving with respect to a multilinear projection. Compared to the LDS with an equal number of parameters, the MLDS achieves higher prediction accuracy and marginal likelihood for both artiﬁcial and real datasets. 1

6 0.78127009 179 nips-2013-Low-Rank Matrix and Tensor Completion via Adaptive Sampling

7 0.68422687 155 nips-2013-Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition

8 0.53273606 254 nips-2013-Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms

9 0.52463102 307 nips-2013-Speedup Matrix Completion with Side Information: Application to Multi-Label Learning

10 0.49956101 281 nips-2013-Robust Low Rank Kernel Embeddings of Multivariate Distributions

11 0.48653853 185 nips-2013-Matrix Completion From any Given Set of Observations

12 0.47330335 342 nips-2013-Unsupervised Spectral Learning of Finite State Transducers

13 0.42405632 352 nips-2013-What do row and column marginals reveal about your dataset?

14 0.41714695 108 nips-2013-Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion

15 0.40721175 306 nips-2013-Speeding up Permutation Testing in Neuroimaging

16 0.40167817 222 nips-2013-On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization

17 0.39864349 354 nips-2013-When in Doubt, SWAP: High-Dimensional Sparse Recovery from Correlated Measurements

18 0.39163223 117 nips-2013-Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis

19 0.37594453 70 nips-2013-Contrastive Learning Using Spectral Methods

20 0.36903265 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(2, 0.012), (16, 0.029), (30, 0.164), (33, 0.186), (34, 0.073), (36, 0.012), (41, 0.08), (49, 0.037), (56, 0.149), (70, 0.026), (84, 0.014), (85, 0.055), (89, 0.024), (93, 0.042), (95, 0.031)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.93919015 19 nips-2013-Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

Author: Shai Shalev-Shwartz, Tong Zhang

Abstract: Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is often used in practice. Our main contribution is to introduce an accelerated mini-batch version of SDCA and prove a fast convergence rate for this method. We discuss an implementation of our method over a parallel computing system, and compare the results to both the vanilla stochastic dual coordinate ascent and to the accelerated deterministic gradient descent method of Nesterov [2007]. 1

2 0.89621538 110 nips-2013-Estimating the Unseen: Improved Estimators for Entropy and other Properties

Author: Paul Valiant, Gregory Valiant

Abstract: Recently, Valiant and Valiant [1, 2] showed that a class of distributional properties, which includes such practically relevant properties as entropy, the number of distinct elements, and distance metrics between pairs of distributions, can be estimated given a sublinear sized sample. Speciﬁcally, given a sample consisting of independent draws from any distribution over at most n distinct elements, these properties can be estimated accurately using a sample of size O(n/ log n). We propose a novel modiﬁcation of this approach and show: 1) theoretically, this estimator is optimal (to constant factors, over worst-case instances), and 2) in practice, it performs exceptionally well for a variety of estimation tasks, on a variety of natural distributions, for a wide range of parameters. Perhaps unsurprisingly, the key step in our approach is to ﬁrst use the sample to characterize the “unseen” portion of the distribution. This goes beyond such tools as the Good-Turing frequency estimation scheme, which estimates the total probability mass of the unobserved portion of the distribution: we seek to estimate the shape of the unobserved portion of the distribution. This approach is robust, general, and theoretically principled; we expect that it may be fruitfully used as a component within larger machine learning and data analysis systems. 1

same-paper 3 0.89081293 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors

Author: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu

4 0.86770022 224 nips-2013-On the Sample Complexity of Subspace Learning

Author: Alessandro Rudi, Guillermo D. Canas, Lorenzo Rosasco

Abstract: A large number of algorithms in machine learning, from principal component analysis (PCA), and its non-linear (kernel) extensions, to more recent spectral embedding and support estimation methods, rely on estimating a linear subspace from samples. In this paper we introduce a general formulation of this problem and derive novel learning error estimates. Our results rely on natural assumptions on the spectral properties of the covariance operator associated to the data distribution, and hold for a wide class of metrics between subspaces. As special cases, we discuss sharp error estimates for the reconstruction properties of PCA and spectral support estimation. Key to our analysis is an operator theoretic approach that has broad applicability to spectral learning methods. 1

5 0.84574515 11 nips-2013-A New Convex Relaxation for Tensor Completion

Author: Bernardino Romera-Paredes, Massimiliano Pontil

6 0.84561199 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives

7 0.83201319 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing

8 0.82833916 333 nips-2013-Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

9 0.82717586 142 nips-2013-Information-theoretic lower bounds for distributed statistical estimation with communication constraints

10 0.82665271 179 nips-2013-Low-Rank Matrix and Tensor Completion via Adaptive Sampling

11 0.82652074 20 nips-2013-Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

12 0.82585496 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances

13 0.82573944 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors

14 0.82545829 175 nips-2013-Linear Convergence with Condition Number Independent Access of Full Gradients

15 0.82503998 149 nips-2013-Latent Structured Active Learning

16 0.82478112 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

17 0.82327044 318 nips-2013-Structured Learning via Logistic Regression

18 0.82264602 314 nips-2013-Stochastic Optimization of PCA with Capped MSG

19 0.82172942 74 nips-2013-Convex Tensor Decomposition via Structured Schatten Norm Regularization

20 0.8217259 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic