OpenRaiser/Intern-Atlas huggingface dataset:
Computing properties of stable configurations of thermodynamic binding networks
Venue: arXiv cs.ET 2019
Year: 2019

The promise of chemical computation lies in controlling systems incompatible with traditional electronic micro-controllers, with applications in synthetic biology and nano-scale manufacturing. Computation is typically embedded in kinetics---the specific time evolution of a chemical system. However, if the desired output is not thermodynamically stable, basic physical chemistry dictates that thermodynamic forces will drive the system toward error throughout the computation. The thermodynamic binding network (TBN) model was introduced to formally study how the thermodynamic equilibrium can be made consistent with the desired computation, and it idealizes tradeoffs between configurational entropy and binding. Here we prove the computational hardness of natural questions about TBNs and develop a practical algorithm for verifying the correctness of constructions by translating the problem into propositional logic and solving the resulting formula. The TBN model together with automated verification tools will help inform strategies for error reduction in molecular computing, including the extensively studied models of strand displacement cascades and algorithmic tile assembly.
DR.SGX: Hardening SGX Enclaves against Cache Attacks with Data Location Randomization
Venue: arXiv cs.CR 2019
Year: 2019

Recent research has demonstrated that Intel's SGX is vulnerable to software-based side-channel attacks. In a common attack, the adversary monitors CPU caches to infer secret-dependent data accesses patterns. Known defenses have major limitations, as they require either error-prone developer assistance, incur extremely high runtime overhead, or prevent only specific attacks. In this paper, we propose data location randomization as a novel defense against side-channel attacks that target data access patterns. Our goal is to break the link between the memory observations by the adversary and the actual data accesses by the victim. We design and implement a compiler-based tool called DR.SGX that instruments the enclave code, permuting data locations at fine granularity. To prevent correlation of repeated memory accesses we periodically re-randomize all enclave data. Our solution requires no developer assistance and strikes the balance between side-channel protection and performance based on an adjustable security parameter.
Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem
Venue: arXiv cs.AI 2019
Year: 2019

The container pre-marshalling problem (CPMP) is concerned with the re-ordering of containers in container terminals during off-peak times so that containers can be quickly retrieved when the port is busy. The problem has received significant attention in the literature and is addressed by a large number of exact and heuristic methods. Existing methods for the CPMP heavily rely on problem-specific components (e.g., proven lower bounds) that need to be developed by domain experts with knowledge of optimization techniques and a deep understanding of the problem at hand. With the goal to automate the costly and time-intensive design of heuristics for the CPMP, we propose a new method called Deep Learning Heuristic Tree Search (DLTS). It uses deep neural networks to learn solution strategies and lower bounds customized to the CPMP solely through analyzing existing (near-) optimal solutions to CPMP instances. The networks are then integrated into a tree search procedure to decide which branch to choose next and to prune the search tree. DLTS produces the highest quality heuristic solutions to the CPMP to date with gaps to optimality below 2% on real-world sized instances.
CAOS: Concurrent-Access Obfuscated Store
Venue: arXiv cs.CR 2019
Year: 2019

This paper proposes Concurrent-Access Obfuscated Store (CAOS), a construction for remote data storage that provides access-pattern obfuscation in a honest-but-curious adversarial model, while allowing for low bandwidth overhead and client storage. Compared to the state of the art, the main advantage of CAOS is that it supports concurrent access without a proxy, for multiple read-only clients and a single read-write client. Concurrent access is achieved by letting clients maintain independent maps that describe how the data is stored. These maps might diverge from client to client, but it is guaranteed that no client will ever lose track of current data. We achieve efficiency and concurrency at the expense of perfect obfuscation: in CAOS the extent to which access patterns are hidden is determined by the resources allocated to its built-in obfuscation mechanism. To assess this trade-off we provide both a security and a performance analysis of our protocol instance. We additionally provide a proof-of-concept implementation.
On the Capacity of Face Representation
Venue: arXiv cs.CV 2019
Year: 2019

In this paper we address the following question, given a face representation, how many identities can it resolve? In other words, what is the capacity of the face representation? A scientific basis for estimating the capacity of a given face representation will not only benefit the evaluation and comparison of different representation methods, but will also establish an upper bound on the scalability of an automatic face recognition system. We cast the face capacity problem in terms of packing bounds on a low-dimensional manifold embedded within a deep representation space. By explicitly accounting for the manifold structure of the representation as well two different sources of representational noise: epistemic (model) uncertainty and aleatoric (data) variability, our approach is able to estimate the capacity of a given face representation. To demonstrate the efficacy of our approach, we estimate the capacity of two deep neural network based face representations, namely 128-dimensional FaceNet and 512-dimensional SphereFace. Numerical experiments on unconstrained faces (IJB-C) provides a capacity upper bound of $2.7\times10^4$ for FaceNet and $8.4\times10^4$ for SphereFace representation at a false acceptance rate (FAR) of 1%. As expected, capacity reduces drastically at lower FARs. The capacity at FAR of 0.1% and 0.001% is $2.2\times10^3$ and $1.6\times10^{1}$, respectively for FaceNet and $3.6\times10^3$ and $6.0\times10^0$, respectively for SphereFace.
Discovery and recognition of motion primitives in human activities
Venue: arXiv cs.RO 2019
Year: 2019

We present a novel framework for the automatic discovery and recognition of motion primitives in videos of human activities. Given the 3D pose of a human in a video, human motion primitives are discovered by optimizing the `motion flux', a quantity which captures the motion variation of a group of skeletal joints. A normalization of the primitives is proposed in order to make them invariant with respect to a subject anatomical variations and data sampling rate. The discovered primitives are unknown and unlabeled and are unsupervisedly collected into classes via a hierarchical non-parametric Bayes mixture model. Once classes are determined and labeled they are further analyzed for establishing models for recognizing discovered primitives. Each primitive model is defined by a set of learned parameters. Given new video data and given the estimated pose of the subject appearing on the video, the motion is segmented into primitives, which are recognized with a probability given according to the parameters of the learned models. Using our framework we build a publicly available dataset of human motion primitives, using sequences taken from well-known motion capture datasets. We expect that our framework, by providing an objective way for discovering and categorizing human motion, will be a useful tool in numerous research fields including video analysis, human inspired motion generation, learning by demonstration, intuitive human-robot interaction, and human behavior analysis.
Scalable Nonlinear AUC Maximization Methods
Venue: arXiv cs.LG 2019
Year: 2019

The area under the ROC curve (AUC) is a measure of interest in various machine learning and data mining applications. It has been widely used to evaluate classification performance on heavily imbalanced data. The kernelized AUC maximization machines have established a superior generalization ability compared to linear AUC machines because of their capability in modeling the complex nonlinear structure underlying most real-world data. However, the high training complexity renders the kernelized AUC machines infeasible for large-scale data. In this paper, we present two nonlinear AUC maximization algorithms that optimize pairwise linear classifiers over a finite-dimensional feature space constructed via the k-means Nyström method. Our first algorithm maximize the AUC metric by optimizing a pairwise squared hinge loss function using the truncated Newton method. However, the second-order batch AUC maximization method becomes expensive to optimize for extremely massive datasets. This motivate us to develop a first-order stochastic AUC maximization algorithm that incorporates a scheduled regularization update and scheduled averaging techniques to accelerate the convergence of the classifier. Experiments on several benchmark datasets demonstrate that the proposed AUC classifiers are more efficient than kernelized AUC machines while they are able to surpass or at least match the AUC performance of the kernelized AUC machines. The experiments also show that the proposed stochastic AUC classifier outperforms the state-of-the-art online AUC maximization methods in terms of AUC classification accuracy.
You can't always sketch what you want: Understanding Sensemaking in Visual Query Systems
Venue: arXiv cs.DB 2019
Year: 2019

Visual query systems (VQSs) empower users to interactively search for line charts with desired visual patterns, typically specified using intuitive sketch-based interfaces. Despite decades of past work on VQSs, these efforts have not translated to adoption in practice, possibly because VQSs are largely evaluated in unrealistic lab-based settings. To remedy this gap in adoption, we collaborated with experts from three diverse domains---astronomy, genetics, and material science---via a year-long user-centered design process to develop a VQS that supports their workflow and analytical needs, and evaluate how VQSs can be used in practice. Our study results reveal that ad-hoc sketch-only querying is not as commonly used as prior work suggests, since analysts are often unable to precisely express their patterns of interest. In addition, we characterize three essential sensemaking processes supported by our enhanced VQS. We discover that participants employ all three processes, but in different proportions, depending on the analytical needs in each domain. Our findings suggest that all three sensemaking processes must be integrated in order to make future VQSs useful for a wide range of analytical inquiries.
MMCR4NLP: Multilingual Multiway Corpora Repository for Natural Language Processing
Venue: arXiv cs.CL 2019
Year: 2019

Multilinguality is gradually becoming ubiquitous in the sense that more and more researchers have successfully shown that using additional languages help improve the results in many Natural Language Processing tasks. Multilingual Multiway Corpora (MMC) contain the same sentence in multiple languages. Such corpora have been primarily used for Multi-Source and Pivot Language Machine Translation but are also useful for developing multilingual sequence taggers by transfer learning. While these corpora are available, they are not organized for multilingual experiments and researchers need to write boilerplate code every time they want to use said corpora. Moreover, because there is no official MMC collection it becomes difficult to compare against existing approaches. As such we present our work on creating a unified and systematically organized repository of MMC spanning a large number of languages. We also provide training, development and test splits for corpora where official splits are unavailable. We hope that this will help speed up the pace of multilingual NLP research and ensure that NLP researchers obtain results that are more trustable since they can be compared easily. We indicate corpora sources, extraction procedures if any and relevant statistics. We also make our collection public for research purposes.
A Transfer-Learning Approach for Accelerated MRI using Deep Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Purpose: Neural networks have received recent interest for reconstruction of undersampled MR acquisitions. Ideally network performance should be optimized by drawing the training and testing data from the same domain. In practice, however, large datasets comprising hundreds of subjects scanned under a common protocol are rare. The goal of this study is to introduce a transfer-learning approach to address the problem of data scarcity in training deep networks for accelerated MRI. Methods: Neural networks were trained on thousands of samples from public datasets of either natural images or brain MR images. The networks were then fine-tuned using only few tens of brain MR images in a distinct testing domain. Domain-transferred networks were compared to networks trained directly in the testing domain. Network performance was evaluated for varying acceleration factors (2-10), number of training samples (0.5-4k) and number of fine-tuning samples (0-100). Results: The proposed approach achieves successful domain transfer between MR images acquired with different contrasts (T1- and T2-weighted images), and between natural and MR images (ImageNet and T1- or T2-weighted images). Networks obtained via transfer-learning using only tens of images in the testing domain achieve nearly identical performance to networks trained directly in the testing domain using thousands of images. Conclusion: The proposed approach might facilitate the use of neural networks for MRI reconstruction without the need for collection of extensive imaging datasets.
Secret-Key Generation in Many-to-One Networks: An Integrated Game-Theoretic and Information-Theoretic Approach
Venue: arXiv cs.IT 2019
Year: 2019

This paper considers secret-key generation between several agents and a base station that observe independent and identically distributed realizations of correlated random variables. Each agent wishes to generate the longest possible individual key with the base station by means of public communication. All keys must be jointly kept secret from all external entities. In this many-to-one secret-key generation setting, it can be shown that the agents can take advantage of a collective protocol to increase the sum-rate of their generated keys. However, when each agent is only interested in maximizing its own secret-key rate, agents may be unwilling to participate in a collective protocol. Furthermore, when such a collective protocol is employed, how to fairly allocate individual key rates arises as a valid issue. This paper studies this tension between cooperation and self-interest with a game-theoretic treatment. The work establishes that cooperation is in the best interest of all individualistic agents and that there exists individual secret-key rate allocations that incentivize the agents to follow the protocol. Additionally, an explicit coding scheme that achieves such allocations is proposed.
Entropy operates in non-linear semifields
Venue: arXiv cs.IT 2019
Year: 2019

We set out to demonstrate that the Rényi entropies with parameter $α$ are better thought of as operating in a type of non-linear semiring called a positive semifield. We show how the Rényi's postulates lead to Pap's g-calculus where the functions carrying out the domain transformation are Renyi's information function and its inverse. In its turn, Pap's g-calculus under Rényi's information function transforms the set of positive reals into a family of semirings where "standard" product has been transformed into sum and "standard" sum into a power-deformed sum. Consequently, the transformed product has an inverse whence the structure is actually that of a positive semifield. Instances of this construction lead into idempotent analysis and tropical algebra as well as to less exotic structures. Furthermore, shifting the definition of the $α$ parameter shows in full the intimate relation of the Rényi entropies to the weighted generalized power means. We conjecture that this is one of the reasons why tropical algebra procedures, like the Viterbi algorithm of dynamic programming, morphological processing, or neural networks are so successful in computational intelligence applications. But also, why there seem to exist so many procedures to deal with "information" at large.
Hyper-reduction over nonlinear manifolds for large nonlinear mechanical systems
Venue: arXiv cs.CE 2019
Year: 2019

Common trends in model order reduction of large nonlinear finite-element-discretized systems involve the introduction of a linear mapping into a reduced set of unknowns, followed by Galerkin projection of the governing equations onto a constant reduction basis. Though this reduces the number of unknowns in the system, the computational cost for obtaining the solution could still be high due to the prohibitive computational costs involved in the evaluation of nonlinear terms. Hyper-reduction methods are then seen as a fast way of approximating the nonlinearity in the system of equations. In the finite element context, the energy conserving sampling and weighing (ECSW) method has emerged as a stability and structure-preserving method for hyper-reduction. Classical hyper-reduction techniques, however, are applicable only in the context of linear mappings into the reduction subspace. In this work, we extend the concept of hyper-reduction using ECSW to general nonlinear mappings, while retaining its desirable stability and structure-preserving properties. As a proof of concept, the proposed hyper-reduction technique is demonstrated over models of a flat plate and a realistic wing structure, whose dynamics has been shown to evolve over a nonlinear (quadratic) manifold. An online speed-up of over one thousand times relative to the full system has been obtained for the wing structure using the proposed method, which is higher than its linear counterpart using the ECSW.
Approximate Hotspots of Orthogonal Trajectories
Venue: arXiv cs.CG 2019
Year: 2019

In this paper we study the problem of finding hotspots, i.e. regions in which a moving entity has spent a significant amount of time, for polygonal trajectories. The fastest optimal algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) finds an axis-parallel square hotspot of fixed side length in $O(n^2)$. Limiting ourselves to the case in which the entity moves in a direction parallel either to the $x$ or the $y$-axis, We present an approximation algorithm with the time complexity $O(n \log^3 n)$ and approximation factor $1/2$.
The Reliability Function of Lossy Source-Channel Coding of Variable-Length Codes with Feedback
Venue: arXiv cs.IT 2019
Year: 2019

We consider transmission of discrete memoryless sources (DMSes) across discrete memoryless channels (DMCs) using variable-length lossy source-channel codes with feedback. The reliability function (optimum error exponent) is shown to be equal to $\max\{0, B(1-R(D)/C)\},$ where $R(D)$ is the rate-distortion function of the source, $B$ is the maximum relative entropy between output distributions of the DMC, and $C$ is the Shannon capacity of the channel. We show that, in this setting and in this asymptotic regime, separate source-channel coding is, in fact, optimal.
Communication-free Massively Distributed Graph Generation
Venue: arXiv cs.DC 2019
Year: 2019

Analyzing massive complex networks yields promising insights about our everyday lives. Building scalable algorithms to do so is a challenging task that requires a careful analysis and an extensive evaluation. However, engineering such algorithms is often hindered by the scarcity of publicly~available~datasets. Network generators serve as a tool to alleviate this problem by providing synthetic instances with controllable parameters. However, many network generators fail to provide instances on a massive scale due to their sequential nature or resource constraints. Additionally, truly scalable network generators are few and often limited in their realism. In this work, we present novel generators for a variety of network models that are frequently used as benchmarks. By making use of pseudorandomization and divide-and-conquer schemes, our generators follow a communication-free paradigm. The resulting generators are thus embarrassingly parallel and have a near optimal scaling behavior. This allows us to generate instances of up to $2^{43}$ vertices and $2^{47}$ edges in less than 22 minutes on 32768 cores. Therefore, our generators allow new graph families to be used on an unprecedented scale.
Impact of Processing-Resource Sharing on the Placement of Chained Virtual Network Functions
Venue: arXiv cs.NI 2019
Year: 2019

Network Function Virtualization (NFV) provides higher flexibility for network operators and reduces the complexity in network service deployment. Using NFV, Virtual Network Functions (VNF) can be located in various network nodes and chained together in a Service Function Chain (SFC) to provide a specific service. Consolidating multiple VNFs in a smaller number of locations would allow decreasing capital expenditures. However, excessive consolidation of VNFs might cause additional latency penalties due to processing-resource sharing, and this is undesirable, as SFCs are bounded by service-specific latency requirements. In this paper, we identify two different types of penalties (referred as "costs") related to the processingresource sharing among multiple VNFs: the context switching costs and the upscaling costs. Context switching costs arise when multiple CPU processes (e.g., supporting different VNFs) share the same CPU and thus repeated loading/saving of their context is required. Upscaling costs are incurred by VNFs requiring multi-core implementations, since they suffer a penalty due to the load-balancing needs among CPU cores. These costs affect how the chained VNFs are placed in the network to meet the performance requirement of the SFCs. We evaluate their impact while considering SFCs with different bandwidth and latency requirements in a scenario of VNF consolidation.
Large Player games on Wireless Networks
Venue: arXiv cs.SY 2019
Year: 2019

We consider a scenario where $N$ users send packets to a common access point. The receiver decodes the message of each user by treating the other user's signals as noise. Associated with each user is its channel state and a finite queue which varies with time. Each user allocates his power and the admission control variable dynamically to maximize his expected throughput. Each user is unaware of the states, and actions taken, by the other users. This problem is formulated as a Markov game for which we show the existence of equilibrium and an algorithm to compute the equilibrium policies. We then show that when the number of users exceeds a particular threshold, the throughput of all users at all the equilibria are the same. Furthermore the equilibrium policies of the users are invariant as long as the number of users remain above the latter threshold. We also show that each user can compute these policies using a sequence of linear programs which does not depend upon the parameters of the other users. Hence, these policies can be computed by each user without any information or feedback from the other users. We then provide numerical results which verify our theoretical results.