Title: NEURAL VIDEO ENCODING

Abstract: Deep neural networks have had unprecedented success in computer vision, natural language processing, and speech largely due to the ability to search for suitable task algorithms via differentiable programming. In this paper, we borrow ideas from Kolmogorov complexity theory and normalizing flows to explore the possibilities of finding arbitrary algorithms that represent data. In particular, algorithms which encode sequences of video image frames. Ultimately, we demonstrate neural video encoded using convolutional neural networks to transform autoregressive noise processes and show that this method has surprising cryptographic analogs for information security.

:

In algorithmic information theory, the Kolmogorov complexity of an object is the length of the shortest computer program that, without additional input, produces the object as output (Ming & Paul, 2008) . For example, a long sequence of ones contains very little information because a short program for i ← 0, n do print 1 can output the data. Similarly, the transcendental number π = 3.1415 . . . is an infinite sequence of seemingly random decimal digits but contains only a small amount of information since there exists a very short program that produces the consecutive digits of π forever (Bailey et al., 1997) .

While this idea of exchanging data with computation is theoretically intriguing, from a practical point of view, explicit specification of instructions to obtain some target representation is generally an intractable approach for arbitrary data.

Recently, however, artificial intelligence had broad success in computer vision, natural language processing, and speech largely due to the ability to search for suitable task algorithms using differentiable programming together with large datasets to obtain abstract computations in the form of neural networks. In this paper, we turn the process around and leverage this same differentiable programming approach to find abstract computations which represent data. That is, we seek algorithms which encode arbitrary information for storage and retrieval. In particular, we demonstrate methods for the encoding of sequential video data within the weights of convolutional neural networks.

In the simplest formulation, video data, X, is treated as an finite ordered sequence of image frames

EQUATION

and we seek an autoregressive computation of the form

EQUATION

where y 0 ← x 0 and f is some convolutional neural network parametrized by weights θ such that y i ≈ x i . It is possible that f can be trained using a self-supervised learning approach where consecutive image frames form training examples and the sum-of-squares, y i -x i 2 , is minimized. That is, during training, f learns a mapping from x i to x i+1 , or rather, learns to advance the current frame by one step. The idea is somewhat similar to conventional autoencoders (Hinton & Zemel, 1993) , but there, f is trained with the identity mapping, from x i on to x i . The catch here is that after training, during recall, f does not receive x i as input but instead y i from the previous evaluation. Since y i only approximates x i , reconstruction error accumulates at each iteration of eq. 2 until sequence reproduction fails1 .

The natural inclination at this point is to extend the approach to train over the full sequence by evaluating eq. 2 N times to produce {y 1 , . . . , y N } and minimizing the mean squared error over the entire sequence at each training iteration. This way, how the network is trained and how the sequence is recalled post-training are congruent. Unfortunately, for sequences beyond a few elements, this is not tractable as long unrolled gradients readily vanish or explode and there is no opportunity for batching which significantly limits training performance and scalability.

The situation can be salvaged by adopting a curriculum learning strategy (Bengio et al., 2009) whereby the training sequence length is slowly increased after achieving some nominal loss objective over shorter intervals. It is important to note that, because CNNs have no recurrent hidden state, this approach can be successfully batched during training over random subsequences of X. Therefore, modulating the training subsequence length to one yields the aforementioned self-supervised learning approach whereas a training sequence length equal to the number of frame elements yields the full sequence loss. While this batched curriculum learning strategy does mitigate challenges associated with teacher forcing, gradients can still be temperamental for larger training sequence lengths necessitating the use of gradient clipping and learning rate scaling (You et al., 2017; 2019) .

An interesting situation occurs when x i = x j but f (x i ) = f (x j ). That is, there exists a nonunique mapping or sequence ambiguity which is not resolvable from a purely supervised learning point of view since a unique input evaluates to multiple output. It is perhaps surprising to some readers that eq. 2 above is capable of handling this situation successfully, despite CNNs having no recurrent hidden state. Due to the lack of teacher forcing and high dimensionality of the data, the network learns to encode (and decode) state information within the pixels thus willfully incurring a local reconstruction penalty in order to facilitate sequence completion. The success of the batched sequence learning strategy depends on the nature of the ambiguity.

Just as the state of a dynamical system is not well defined by a single observation, often encoding is facilitated by sequence dilation of the learned mapping which more uniquely defines the trajectory of sequence evolution. A single frame mapping from x i to x i+1 exhibits a dilation of d = 1 and can be naturally extended to d = 2 by channel concatenation to learn a computation of the form [y i ; y i+1 ] = f ([y i-1 ; y i ]) with dimension (2C) × H × W ; and so on.2 This helps to individuate samples and thereby allay the need for contextual sequence information to achieve recall. For example, the alternating sequence ambiguity in {A, B, A, C, A, D} is easily resolved by dilation d = 2 since all training examples, f (AB) → BA, f (BA) → AC and so on, are unique.

The KTH (Schüldt et al., 2004) and DAVIS17 (Pont-Tuset et al., 2017) datasets are used to investigate the methods described above. KTH data provide a simple initial investigative platform with monochromatic videos featuring simple repetitious actions performed by humans (clapping, hand waving, punching, etc) against a static background while the DAVIS17 data features multi-channel RGB capture of generic action scenes across a variety of dynamic environments (surfing, breakdancing, paragliding, etc). See Figure 1 and Figure 2 for encoding examples using a simple autoencoder style network defined in (1) and applied according to eq. ( 2). Although compression and fidelity are peripheral considerations (see Wu et al. (2018) for full treatment), the examples presented generally yield faithful reproductions according to a multi-scale similarly measure (Wang et al., 2003) and achieve respectable compression ratios of 10x -15x simply by modulating the number of convolutional layers in the CNN. Compression ratios can be further improved by applying mixed precision training techniques (Micikevicius et al., 2017) .

A variety of practical engineering considerations arise during implementation. For example, it is possible to analyze sequence loss during post-production and inject a ground truth frame at a particular deterioration threshold to renew the recall process; analogous to the use of key-frames in standard compression algorithms. It is also possible to train additional networks which upscale the base reproduction. This upscaling approach has advantages in controlling network parameter growth (and hence the compression ratio) as two convolution layers each with 32 filters have only half the parameters compared to a single layer of 64 filters. In this way, eq. 2 is written as the composition of two functions

EQUATION

where f θ advances the sequence and the subsequent application of f θ * bolsters fidelity. From this point of view, f θ * performs the role of denoising autoencoder (Vincent et al., 2008) which strives to form a 'repaired' output from 'corrupted' input. This allows computational demands during recall to be modulated on a frame-by-frame basis according to platform limitations, real-time constraints, and so on. This application of upscaling is shown in Figure 3 .

From here, we can generalize further and leverage the recent advancements in normalizing flows whereby a simple initial density is transformed into a more complex one by applying a sequence of transformations until a desired level of complexity is attained (Tabak & Turner, 2013; Dinh et al., 2014; Jimenez Rezende & Mohamed, 2015; Kingma et al., 2016) . The density q K (z) obtained by successively transforming a random variable z 0 with distribution q 0 through a chain of K transformations f k is:

EQUATION

) where eq. ( 4) is shorthand for the composition f M (f M -1 (. . . f 1 (z 0 ))). In this way, the initial density is said to 'flow' through the sequence of mappings. For our purposes, the original sequence X defined in (1) can be seen as just an arbitrary random noise process in some high-dimensional space. Rather than model the process X directly, instead, it can be approximated, to some acceptable level of fidelity, through a chain of transformations over some known latent process, Z = {z 0 , . . . , z N }. That is, given a random process, Z, defined by g, we have z i+1 = g(z i )

EQUATION

where z j i ≈ x i represents j consecutive transformations applied to z i , and where each f j is a deep neural network defined by Algorithm 1. These transformations are simply a series of bijective mappings (under the given restricted domain and range) and therefore alleviate the aforementioned sequence training challenges associated with realizing computations of the form defined by eq. ( 2). The question then becomes, what is g?

The choice of g must be some random but deterministic high dimensional process with the requirement that ∀z i , z j ∈ Z, z i = z j . That is, the elements of Z are unique such that the process is noncyclic in order to support a bijective mapping. A key insight is that given some g defined by Algorithm 1 and applied according to eq. ( 5), the process Z is completely defined by the starting point, z 0 . Therefore, from the point of view of Kolmogorov complexity, {z 0 , g} is a random computation for the production of the sequence, Z, and normalizing flows with differential programming provide the framework to transform this computation: X f ← -{z 0 0 , g}. From a compiler point of view, z j is simply an abstract intermediate representation (IR).

A simple recipe for realizing g is to choose any two random points z 0 , z ∈ R C×H×W and learn parameters, φ, such that N recursive applications of g φ starting with z 0 yields z . Although, in practice, after sufficient number of training iterations of g φ , it does not matter if z N computed according to eq. ( 5) does not equal z rather it is only required that g φ satisfy the noncyclic random walk properties described above. This recipe for g is described in Algorithm 2 and demonstrated in Figure 4 . The full workflow of transforming random process, Z, generated by g into the target sequence X according to eq. ( 5) is shown in Figure 5 .

Algorithm 2 Simple recipe for realizing a high-dimensional autoregressive noise process.

function FORWARD(g,z,n) defined according to eq. ( 5)

for i ← 0, n do z ← g(z) return z N ←length(X) z 0 = uniform(C × H × W )

samples from a uniform distribution over the interval [0, 1)

z = uniform(C × H × W ) g φ ← NETWORK(nconv) described in Algorithm 1 determine φ that minimizes the z -z 2 for i ← 0, T do z ← FORWARD(g φ , z 0 , N ) l ← z -z 2 δ ← ∂l ∂φ φ ← step(φ,δ)

CRYPTOGRAPHIC CONSIDERATIONS:

The neural video encoding process shares many analogs with symmetric cryptographic algorithms.

In general, cryptography is the body of techniques for secure communications focused on the con- struction of protocols that prevent third parties or the public from reading private information. A protocol defines a system of information exchange which includes rules, syntax, semantics and synchronization of communication. Moreover, a cryptographic protocol usually focuses on various aspects of information security such as confidentiality, data integrity and authentication. Cryptography is often synonymous with encryption which is the conversion or encoding of information from a coherent readable state to an incoherent state of apparent randomness and the reverse process of decryption. A cipher is defined by a pair of algorithms specifying an encryption and decryption process controlled by the use of an auxiliary private key which is required to decrypt the associated data. A key must be selected before using a cipher to encrypt data and without the key, it should be extremely difficult or impossible to decrypt the contents. When the same key is used for both The variables {z 1 30 , z 1 62 , z 1 81 } as computed by eq.( 5) where

z 1 i = f θ1 (z 0 i ) = f θ1 • g φ (z 0 i-1

) and f θ1 is configured with nconv = 32 having been trained for 30000 epochs. (C) The variables {z 2 30 , z 2 62 , z 2 81 } computed as

z 2 i = f θ2 (z 1 i ) = f θ2 • f θ1 (z 0 i

) with f θ2 again having nconv = 32 and trained for 30000 epochs. (D) Ground truth sequence elements {x 30 , x 62 , x 81 } from the unencoded data, X encryption and decryption, the cipher defines a symmetric key algorithm.3 Symmetric cryptography deals with the efficient construction of pseudo random functions which form the building blocks of symmetric algorithms and have the form x = h(z) with the following properties (Ramkumar, 2014) 1. Given x = h(z), small changes to z produce output x unrelated to x.

2. Given z, there is no way to make reliable predictions regarding any part of x.

3. Given x, the easiest way to find z that satisfies x = h(z ) is brute-force search.

4. The fastest way to determine preimages x and x satisfying h(x) = h(x ) is brute-force search.

From a high-level perspective, it is easy to identify latent variable Z and target sequence X as the encrypted and unencrypted data respectively, while the variable, z 0 0 performs the role of shared key. The encryption algorithm is defined by the realization of a generator function, g, which consumes z 0 0 to produce Z, and the decryption algorithm is defined by the application of learned transformations, F = {f j } M j=1 , applied according to eq. ( 5). Together, the neural video components, {g, F }, form a neural cipher and with shared use of key, z 0 0 , define a symmetric cryptographic algorithm. An informal analysis indicates the necessary alignment with the properties of pseudo random functions. For a particular instance of g φ , changes to z 0 0 yield unrelated sequences Z and, by definition, the random values of Z alone provide no information regarding X. Moreover, as black box functions, given some target element x i , the only way to find z satisfying x i = F (z ) is indeed brute-force search. It is natural to go further and consider the significantly more empowered situation in which an adversary could perform differential calculations over F to optimize the search for z which minimizes x i -F (z ) . Effectively, this means the decryption algorithm and a portion of the unencrypted data have been compromised. Even so, without the associated generator, g, it remains very difficult or impossible to resolve additional content since despite having obtained z , it is not possible to make reliable predictions regarding any part of x. Finally, an example of these properties is provided in Figure 6 demonstrating a failed attempt to decrypt an encoded video with an imposter key. In this situation, both the encryption and decryption algorithms have been compromised but the adversary has no knowledge of Z or X. A robust cryptographic algorithm must remain secure even if everything about the implementation, except the key, becomes available to an adversary. 4 Indeed, some work has suggested that CNNs retain accurate image information with different degrees of geometric and photometric invariance (Mahendran & Vedaldi, 2014) . However, the authors attempts at extracting meaningful content using total variation based approaches were unsuccessful since having the encryption and decryption algorithms alone provides little basis for the construction of a loss function to minimize (see also Ulyanov et al. (2017) ). This discussion is, of course, not intended to provide a thorough cryptographic analysis of neural video encoding but rather to facilitate understanding of various properties and highlight the potential for information security.

RELATED WORK:

The storage of information in neural networks has a rich history (Kohonen & Lehtiö, 1989) . Early parallel models of associative memory were used in the investigation of long-term memory systems in cognitive science probing questions of how information is represented in the brain and what kinds of processes operate on it (Anderson & Hinton, 1989) . Some of this early work was motivated by holography as a mechanism for distributed associative recall (Willshaw, 1989) made possible by Nobel prize wining advancements in the development of the holographic method by Gabor. Interestingly, as highlighted by Hinton (1989) in the same body of work, Marr, Palm, and Poggio (Marr et al., 1978) were particularly interested in equations of the form C n+1 = σ(L(C n )) where L is a linear operator and σ a nonlinear function and stressed the importance of understanding their behavior. These associative memory models continue to garner some attention (Karbasi et al., 2013; Mazumdar & Rawat, 2015) Next frame prediction in moving imagery and video data shares similar motivations with neural video encoding but differ in ultimate objective. See Lotter et al. (2017) for discussion and relevant references. Although observed but not highlighted, video encoding networks trained on KTH data for simple repetitious actions often exhibited the ability to generalize beyond encoded sequence for short periods and so demonstrating a limited capacity for what could be argued as generalization versus pure recall.

The application of neural networks to cryptographic problems is not new (Kanter et al., 2002; Klimov et al., 2002; Abadi & Andersen, 2016) and the synergies between machine learning and cryptography have been appreciated for some time (Rivest, 1993) . Many applications of machine learning to cryptography are realized through cryptanalysis tools and majority of neural network applications have been orchestrated at the bit level and around anti-symmetric public protocols as in (Kanter et al., 2002) . Neural video encoding defines a simple symmetric protocol operating in situ at the pixel and hence leverages the native advantages of distributed representation. Although, Figure 6 : An attempt to decrypt (i.e. recall) an encoded video using an imposter key. (A) Key z 0 0 and imposter key z 0 0 . (B) On the left, z 0 0 and g φ applied to generate the appropriate keys {z 0 30 , z 0 62 , z 0 81 } and decrypted through application of F . On the right, the imposter key, z 0 0 , with the same g φ yields an invalid key stream {z 0 30 , z 0 62 , z 0 81 } which decrypt to incoherent states under F .

visual cryptographic methods applied to images directly have existed for some time as well (Naor & Shamir, 1995) (see also Punithavathi & Subbiah (2017) for recent survey).

CONCLUSION:

This work demonstrates encoding methods for the storage and retrieval of video data with convolutional neural networks. There remain many open considerations but ultimately the ability to realize computations of arbitrary complexity which represent data is clear. Moreover, these computations are abstract representations of data and therefore exhibit desirable synergies with cryptographic systems underpinning confidentiality to facilitate information security. Recent advancements in alloptical neural networks (Lin et al., 2018; Zuo et al., 2019) motivate the future exploration of combining past holographic based associative memories efforts with the encoding methods presented here to create potential new forms of optical memory and beyond.

This problem is associated with teacher forcing. See, e.g.,Goodfellow et al. (2016).

In some ways, dilation is akin to the order of an autoregressive model

See Paar & Pelzl (2010),Schneier (2015), andFerguson et al. (2010) for additional discussion.

This is known as Kerckhoffs's principle and (Claude) Shannon's maxim

Figures and Tables:

Figure 1: Video encoding reproductions at 128x128 pixel resolution from the KTH dataset. (A) A reproduction of person15 handclapping d4 using 128 convolutional filters per layer which, although not parameter efficient, achieve high fidelity after 99800 training epochs at full FP32 precision. (B) A reproduction of person15 handwaving d4 using only 32 convolutional filters per layer and dilation d = 2 after 363947 training epochs with mixed FP16 precision. This encoding achieves a compression ratio of 27x but at the cost of some fidelity. (C) Finally, a reproduction of person25 boxing d1 using 32 convolution filters per layer and dilation d = 2 after 473701 training epochs with FP16 precision.

Figure 2: Video encoding reproductions from the DAVIS'17 dataset. (A) Rhino scene reproduction at 3x128x128 pixel resolution with 128 convolutional filters per layer and 200000 training epochs. (B) Miami surf scene recalled at 3x128x128 pixel resolution using 128 filters per layer and 77000 training epochs. (C) Recalled frames at 3x128x128 pixel resolution from the Rollerblade scene using 128 convolutional filters per layer and 250000 training steps. (D) Breakdance reproduction at 120p with pixel resolution 3x120x213 using 48 convolutional filters per layer at 85000 training epochs.

Figure4: Visualizing the training of a high-dimensional autoregressive noise process. The computation, g, as defined is a simple convolutional neural network according to Algorithm 1 and trained as defined by Algorithm 2. In this instance, g φ was initialized with nconv = 8. To help visualize the learning process, distance matrices are calculated over the elements of Z at various stages of training. After 17000 epochs of training, the distance matrix confirms that the elements generated by g φ are sufficient to support bijective transformation.

Figure 5: Neural video encoding via normalizing flows of the DAVIS'17 Breakdance scene at 120p. (A) Visualizations of the variables {z 0 30 , z 0 62 , z 0 81 } from some random autoregressive noise process, g φ , having nconv = 8 and procured according to Algorithm 2 having 10000 training epochs. (B)The variables {z 1 30 , z 1 62 , z 1 81 } as computed by eq.(5) wherez 1 i = f θ1 (z 0 i ) = f θ1 • g φ (z 0 i-1) and f θ1 is configured with nconv = 32 having been trained for 30000 epochs. (C) The variables {z 2 30 , z 2 62 , z 2 81 } computed asz 2 i = f θ2 (z 1 i ) = f θ2 • f θ1 (z 0 i) with f θ2 again having nconv = 32 and trained for 30000 epochs. (D) Ground truth sequence elements {x 30 , x 62 , x 81 } from the unencoded data, X

Peer review (iclr2020):
Summary: This paper introduces convolutional neural networks to encode video sequences. In particular, it exploits an autoencoder style convolutional network to compress videos with certain ratios by modulating the number of convolution layers. Furthermore, it studies an autoregressive model to learn the sequential information over videos. Strength: The idea of using convolutional networks to encode the videos is interesting. The used autoencoder and autoregressive techniques are promising for video encoding. Weakness: The paper gives me an impression that there are very few works to apply convolutional networks (including autoencoder with autoregressive processing) to encode videos. I cannot see any existing works sharing the same motivation, and the paper does not evaluate any related works for comparison. But it seems the use of autoencoder and autoregressive techniques look very straightforward to me. Please clarify the concern. About technical contribution, it is not clear to see if there are any improvement over the conventional autoencoder and autoregressive models. It would be better to make some necessary discussions in the paper. In addition, it seems no descriptions showing how to learn the bijective mappings f_1, ..f_j. Regarding the evaluation, the paper uses visual results and multi-scale SSIM (mssim) to study the effectiveness of the proposed method on the KTH and DAVIS’17 datasets. While a small number of video frames are used, it would be necessary to evaluate the overall (average) mssim on the whole dataset. There are quite a few typos or grammatical problems on sentences such as “...algorithms which encode sequences of video image frames.”, “f is some convolutional neural network…”, “analogous to the use of key-frames in standard compression algorithms.