The tremendous success of deep neural networks has motivated the need to better understand the fundamental properties of these networks, but many of the theoretical results proposed have only been for shallow networks. In this paper, we study an important primitive for understanding the meaningful input space of a deep network: span recovery. For $k<n$, let $\mathbf{A} \in \mathbb{R}^{k \times n}$ be the innermost weight matrix of an arbitrary feed forward neural network $M: \mathbb{R}^n \to  \mathbb{R}$, so $M(x)$ can be written as $M(x) = \sigma(\mathbf{A} x)$, for some network $\sigma: \mathbb{R}^k \to  \mathbb{R}$. The goal is then to recover the row span of $\mathbf{A}$ given only oracle access to the value of $M(x)$. We show that if $M$ is a multi-layered network with ReLU activation functions, then partial recovery is possible: namely, we can provably recover $k/2$ linearly independent vectors in the row span of $\mathbf{A}$ using poly$(n)$ non-adaptive queries to $M(x)$.  Furthermore, if $M$ has differentiable activation functions, we demonstrate that \textit{full} span recovery is possible even when the output is first passed through a sign or $0/1$ thresholding function; in this case our algorithm is adaptive. Empirically, we confirm that full span recovery is not always possible, but only for unrealistically thin layers. For reasonably wide networks, we obtain full span recovery on both random networks and networks trained on MNIST data. Furthermore, we demonstrate the utility of span recovery as an attack by inducing neural networks to misclassify data obfuscated by controlled random noise as sensical inputs. 
 Consider the general framework in which we are given an unknown function f : R n → R, and we want to learn properties about this function given only access to the value f (x) for different inputs x. There are many contexts where this framework is applicable, such as blackbox optimization in which we are learning to optimize f (x) (Djolonga et al., 2013) , PAC learning in which we are learning to approximate f (x) (Denis, 1998) , adversarial attacks in which we are trying to find adversarial inputs to f (x) (Szegedy et al., 2013) , or structure recovery in which we are learning the structure of f (x). For example in the case when f (x) is a neural network, one might want to recover the underlying weights or architecture (Arora et al., 2014; . In this work, we consider the setting when f (x) = M (x) is a neural network that admits a latent low-dimensional structure, namely M (x) = σ(Ax) where A ∈ R k×n is a rank k matrix for some k < n, and σ : R k → R is some neural network. In this setting, we focus primarily on the goal of recovering the row-span of the weight matrix A. We remark that we can assume that A is full-rank as our results extend to the case when A is not full-rank. Span recovery of general functions f (x) = g(Ax), where g is arbitrary, has been studied in some contexts, and is used to gain important information about the underlying function f . By learning Span(A), we in essence are capturing the relevant subspace of the input to f ; namely, f behaves identically on x as it does on the projection of x onto the row-span of A. In statistics, this is known as effective dimension reduction or the multi-index model Li (1991) ; Xia et al. (2002) . Another important motivation for span recovery is for designing adversarial attacks. Given the span of A, we compute the kernel of A, which can be used to fool the function into behaving incorrectly on inputs which are perturbed by vectors in the kernel. Specifically, if x is a legitimate input correctly classified by f and y is a large random vector in the kernel of A, then x + y will be indistinguishable from noise but we will have f (x) = f (x + y). Several works have considered the problem from an approximation-theoretic standpoint, where the goal is to output a hypothesis function f which approximates f well on a bounded domain. For instance, in the case that A ∈ R n is a rank 1 matrix and g(Ax) is a smooth function with bounded derivatives, Cohen et al. (2012) gives an adaptive algorithm to approximate f . Their results also give an approximation A to A, under the assumption that A is a stochastic vector (A i ≥ 0 for each i and i A i = 1). Extending this result to more general rank k matrices A ∈ R k×n , Tyagi & Cevher (2014) and Fornasier et al. (2012) give algorithms with polynomial sample complexity to find approximations f to twice differentiable functions f . However, their results do not provide any guarantee that the original matrix A
We provably recover the span of a deep multi-layered neural network with latent structure and empirically apply efficient span recovery algorithms to attack networks by obfuscating inputs.
{"src": "scitldr-AIC_train", "paper_id": "B1guLAVFDB"}