OpenRaiser/Intern-Atlas huggingface dataset:
Estimating scale-invariant future in continuous time
Venue: arXiv cs.AI 2018
Year: 2018

Natural learners must compute an estimate of future outcomes that follow from a stimulus in continuous time. Widely used reinforcement learning algorithms discretize continuous time and estimate either transition functions from one step to the next (model-based algorithms) or a scalar value of exponentially-discounted future reward using the Bellman equation (model-free algorithms). An important drawback of model-based algorithms is that computational cost grows linearly with the amount of time to be simulated. On the other hand, an important drawback of model-free algorithms is the need to select a time-scale required for exponential discounting. We present a computational mechanism, developed based on work in psychology and neuroscience, for computing a scale-invariant timeline of future outcomes. This mechanism efficiently computes an estimate of inputs as a function of future time on a logarithmically-compressed scale, and can be used to generate a scale-invariant power-law-discounted estimate of expected future reward. The representation of future time retains information about what will happen when. The entire timeline can be constructed in a single parallel operation which generates concrete behavioral and neural predictions. This computational mechanism could be incorporated into future reinforcement learning algorithms.
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

One of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset whose total weight is below a capacity threshold T. Despite its wide applicability in various areas in Computer Science, Operations Research, and Finance, the best known running time for the problem is O(Tn). The main result of our work is an improved algorithm running in time O(TD), where D is the number of distinct weights. Previously, faster runtimes for Knapsack were only possible when both weights and values are bounded by M and V respectively, running in time O(nMV) [Pisinger'99]. In comparison, our algorithm implies a bound of O(nM^2) without any dependence on V, or O(nV^2) without any dependence on M. Additionally, for the unbounded Knapsack problem, we provide an algorithm running in time O(M^2) or O(V^2). Both our algorithms match recent conditional lower bounds shown for the Knapsack problem [Cygan et al'17, Künnemann et al'17]. We also initiate a systematic study of general capacitated dynamic programming, of which Knapsack is a core problem. This problem asks to compute the maximum weight path of length k in an edge- or node-weighted directed acyclic graph. In a graph with m edges, these problems are solvable by dynamic programming in time O(km), and we explore under which conditions the dependence on k can be eliminated. We identify large classes of graphs where this is possible and apply our results to obtain linear time algorithms for the problem of k-sparse Delta-separated sequences. The main technical innovation behind our results is identifying and exploiting concavity that appears in relaxations and subproblems of the tasks we consider.
Fast 5DOF Needle Tracking in iOCT
Venue: arXiv cs.CV 2018
Year: 2018

Purpose. Intraoperative Optical Coherence Tomography (iOCT) is an increasingly available imaging technique for ophthalmic microsurgery that provides high-resolution cross-sectional information of the surgical scene. We propose to build on its desirable qualities and present a method for tracking the orientation and location of a surgical needle. Thereby, we enable direct analysis of instrument-tissue interaction directly in OCT space without complex multimodal calibration that would be required with traditional instrument tracking methods. Method. The intersection of the needle with the iOCT scan is detected by a peculiar multi-step ellipse fitting that takes advantage of the directionality of the modality. The geometric modelling allows us to use the ellipse parameters and provide them into a latency aware estimator to infer the 5DOF pose during needle movement. Results. Experiments on phantom data and ex-vivo porcine eyes indicate that the algorithm retains angular precision especially during lateral needle movement and provides a more robust and consistent estimation than baseline methods. Conclusion. Using solely crosssectional iOCT information, we are able to successfully and robustly estimate a 5DOF pose of the instrument in less than 5.5 ms on a CPU.
D-Sempre: Learning Deep Semantic-Preserving Embeddings for User interests-Social Contents Modeling
Venue: arXiv cs.SI 2018
Year: 2018

Exponential growth of social media consumption demands effective user interests-social contents modeling for more personalized recommendation and social media summarization. However, due to the heterogeneous nature of social contents, traditional approaches lack the ability of capturing the hidden semantic correlations across these multi-modal data, which leads to semantic gaps between social content understanding and user interests. To effectively bridge the semantic gaps, we propose a novel deep learning framework for user interests-social contents modeling. We first mine and parse data, i.e. textual content, visual content, social context and social relation, from heterogeneous social media feeds. Then, we design a two-branch network to map the social contents and users into a same latent space. Particularly, the network is trained by a large margin objective that combines a cross-instance distance constraint with a within-instance semantic-preserving constraint in an end-to- end manner. At last, a Deep Semantic-Preserving Embedding (D-Sempre) is learned, and the ranking results can be given by calculating distances between social contents and users. To demonstrate the effectiveness of D-Sempre in user interests-social contents modeling, we construct a Twitter dataset and conduct extensive experiments on it. As a result, D-Sempre effectively integrates the multi-modal data from heterogeneous social media feeds and captures the hidden semantic correlations between users' interests and social contents.
Finite-Length Construction of High Performance Spatially-Coupled Codes via Optimized Partitioning and Lifting
Venue: arXiv cs.IT 2018
Year: 2018

Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant attention thanks to their capacity approaching performance and low decoding latency. An SC code is constructed by partitioning an underlying block code into a number of components and coupling their copies together. In this paper, we first introduce a general approach for the enumeration of detrimental combinatorial objects in the graph of finite-length SC codes. Our approach is general in the sense that it effectively works for SC codes with various column weights and memories. Next, we present a two-stage framework for the construction of high-performance binary SC codes optimized for additive white Gaussian noise channel; we aim at minimizing the number of detrimental combinatorial objects in the error floor regime. In the first stage, we deploy a novel partitioning scheme, called the optimal overlap partitioning, to produce optimal partitioning corresponding to the smallest number of detrimental objects. In the second stage, we apply a new circulant power optimizer to further reduce the number of detrimental objects in the lifted graph. An SC code constructed by our new framework has nearly 5 orders of magnitudes error floor performance improvement compared to the uncoupled setting.
Attributed Hierarchical Port Graphs and Applications
Venue: arXiv cs.LO 2018
Year: 2018

We present attributed hierarchical port graphs (AHP) as an extension of port graphs that aims at facilitating the design of modular port graph models for complex systems. AHP consist of a number of interconnected layers, where each layer defines a port graph whose nodes may link to layers further down the hierarchy; attributes are used to store user-defined data as well as visualisation and run-time system parameters. We also generalise the notion of strategic port graph rewriting (a particular kind of graph transformation system, where port graph rewriting rules are controlled by user-defined strategies) to deal with AHP following the Single Push-out approach. We outline examples of application in two areas: functional programming and financial modelling.
Efficient Implementation of Evaluation Strategies via Token-Guided Graph Rewriting
Venue: arXiv cs.PL 2018
Year: 2018

In implementing evaluation strategies of the lambda-calculus, both correctness and efficiency of implementation are valid concerns. While the notion of correctness is determined by the evaluation strategy, regarding efficiency there is a larger design space that can be explored, in particular the trade-off between space versus time efficiency. We contributed to the study of this trade-off by the introduction of an abstract machine for call-by-need, inspired by Girard's Geometry of Interaction, a machine combining token passing and graph rewriting. This work presents an extension of the machine, to additionally accommodate left-to-right and right-to-left call-by-value strategies. We show soundness and completeness of the extended machine with respect to each of the call-by-need and two call-by-value strategies. Analysing time cost of its execution classifies the machine as "efficient" in Accattoli's taxonomy of abstract machines.
Compiling Diderot: From Tensor Calculus to C
Venue: arXiv cs.PL 2018
Year: 2018

Diderot is a parallel domain-specific language for analysis and visualization of multidimensional scientific images, such as those produced by CT and MRI scanners. In particular, it supports algorithms where tensor fields (i.e., functions from 3D points to tensor values) are used to represent the underlying physical objects that were scanned by the imaging device. Diderot supports higher-order programming where tensor fields are first-class values and where differential operators and lifted linear-algebra operators can be used to express mathematical reasoning directly in the language. While such lifted field operations are central to the definition and computation of many scientific visualization algorithms, to date they have required extensive manual derivations and laborious implementation. The challenge for the Diderot compiler is to effectively translate the high-level mathematical concepts that are expressible in the surface language to a low-level and efficient implementation in C. This paper describes our approach to this challenge, which is based around the careful design of an intermediate representation (IR), called EIN, and a number of compiler transformations that lower the program from tensor calculus to C while avoiding combinatorial explosion in the size of the IR. We describe the challenges in compiling a language like Diderot, the design of EIN, and the transformation used by the compiler. We also present an evaluation of EIN with respect to both compiler efficiency and quality of generated code.
Goal-Oriented Optimal Design of Experiments for Large-Scale Bayesian Linear Inverse Problems
Venue: arXiv cs.CE 2018
Year: 2018

We develop a framework for goal-oriented optimal design of experiments (GOODE) for large-scale Bayesian linear inverse problems governed by PDEs. This framework differs from classical Bayesian optimal design of experiments (ODE) in the following sense: we seek experimental designs that minimize the posterior uncertainty in the experiment end-goal, e.g., a quantity of interest (QoI), rather than the estimated parameter itself. This is suitable for scenarios in which the solution of an inverse problem is an intermediate step and the estimated parameter is then used to compute a QoI. In such problems, a GOODE approach has two benefits: the designs can avoid wastage of experimental resources by a targeted collection of data, and the resulting design criteria are computationally easier to evaluate due to the often low-dimensionality of the QoIs. We present two modified design criteria, A-GOODE and D-GOODE, which are natural analogues of classical Bayesian A- and D-optimal criteria. We analyze the connections to other ODE criteria, and provide interpretations for the GOODE criteria by using tools from information theory. Then, we develop an efficient gradient-based optimization framework for solving the GOODE optimization problems. Additionally, we present comprehensive numerical experiments testing the various aspects of the presented approach. The driving application is the optimal placement of sensors to identify the source of contaminants in a diffusion and transport problem. We enforce sparsity of the sensor placements using an $\ell_1$-norm penalty approach, and propose a practical strategy for specifying the associated penalty parameter.
Automatic supermartingales acting on sequences
Venue: arXiv cs.FL 2018
Year: 2018

This paper describes a construction of supermartingales realized as automatic functions. A capital of supermartingales is represented using automatic capital groups~(ACG). Properties of these automatic supermartingales are then studied. Automatic supermartingales induce a notion of random infinite binary sequence. We show that the class of random sequences coincide with that of disjunctive sequences.
Implementing distributed λ-calculus interpreter
Venue: arXiv cs.PL 2018
Year: 2018

This paper describes how one can implement distributed λ-calculus interpreter from scratch. At first, we describe how to implement a monadic parser, than the Krivine Machine is introduced for the interpretation part and as for distribution, the actor model is used. In this work we are not providing general solution for parallelism, but we consider particular patterns, which always can be parallelized. As a result, the basic extensible implementation of call-by-name distributed machine is introduced and prototype is presented. We achieved computation speed improvement in some cases, but efficient distributed version is not achieved, problems are discussed in evaluation section. This work provides a foundation for further research, completing the implementation it is possible to add concurrency for non-determinism, improve the interpreter using call-by-need semantic or study optimal auto parallelization to generalize what could be done efficiently in parallel.
Deep Residual Network for Joint Demosaicing and Super-Resolution
Venue: arXiv cs.CV 2018
Year: 2018

In digital photography, two image restoration tasks have been studied extensively and resolved independently: demosaicing and super-resolution. Both these tasks are related to resolution limitations of the camera. Performing super-resolution on a demosaiced images simply exacerbates the artifacts introduced by demosaicing. In this paper, we show that such accumulation of errors can be easily averted by jointly performing demosaicing and super-resolution. To this end, we propose a deep residual network for learning an end-to-end mapping between Bayer images and high-resolution images. By training on high-quality samples, our deep residual demosaicing and super-resolution network is able to recover high-quality super-resolved images from low-resolution Bayer mosaics in a single step without producing the artifacts common to such processing when the two operations are done separately. We perform extensive experiments to show that our deep residual network achieves demosaiced and super-resolved images that are superior to the state-of-the-art both qualitatively and in terms of PSNR and SSIM metrics.
A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
Venue: arXiv cs.DS 2018
Year: 2018

\emph{Sampling} constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology. A central class of sampling algorithms is the \emph{Markov Chain Monte Carlo} method, based on the construction of a Markov chain with the desired sampling distribution as its stationary distribution. Many of the traditional Markov chains, such as the \emph{Glauber dynamics}, do not scale well with increasing dimension. To address this shortcoming, we propose a simple local update rule based on the Glauber dynamics that leads to efficient parallel and distributed algorithms for sampling from Gibbs distributions. Concretely, we present a Markov chain that mixes in $O(\log n)$ rounds when Dobrushin's condition for the Gibbs distribution is satisfied. This improves over the \emph{LubyGlauber} algorithm by Feng, Sun, and Yin [PODC'17], which needs $O(Δ\log n)$ rounds, and their \emph{LocalMetropolis} algorithm, which converges in $O(\log n)$ rounds but requires a considerably stronger mixing condition. Here, $n$ denotes the number of nodes in the graphical model inducing the Gibbs distribution, and $Δ$ its maximum degree. In particular, our method can sample a uniform proper coloring with $αΔ$ colors in $O(\log n)$ rounds for any $α>2$, which almost matches the threshold of the sequential Glauber dynamics and improves on the $α>2 +\sqrt{2}$ threshold of Feng et al.
Deep Echo State Networks for Diagnosis of Parkinson's Disease
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we introduce a novel approach for diagnosis of Parkinson's Disease (PD) based on deep Echo State Networks (ESNs). The identification of PD is performed by analyzing the whole time-series collected from a tablet device during the sketching of spiral tests, without the need for feature extraction and data preprocessing. We evaluated the proposed approach on a public dataset of spiral tests. The results of experimental analysis show that DeepESNs perform significantly better than shallow ESN model. Overall, the proposed approach obtains state-of-the-art results in the identification of PD on this kind of temporal data.
The problem of the development ontology-driven architecture of intellectual software systems
Venue: arXiv cs.AI 2018
Year: 2018

The paper describes the architecture of the intelligence system for automated design of ontological knowledge bases of domain areas and the software model of the management GUI (Graphical User Interface) subsystem
Principles of design and software development models of ontological-driven computer systems
Venue: arXiv cs.AI 2018
Year: 2018

This paper describes the design principles of methodology of knowledge-oriented information systems based on ontological approach. Such systems implement technology subject-oriented extraction of knowledge from the set of natural language texts and their formal and logical presentation and application processing
Formal Analysis of Galois Field Arithmetics - Parallel Verification and Reverse Engineering
Venue: arXiv cs.SC 2018
Year: 2018

Galois field (GF) arithmetic circuits find numerous applications in communications, signal processing, and security engineering. Formal verification techniques of GF circuits are scarce and limited to circuits with known bit positions of the primary inputs and outputs. They also require knowledge of the irreducible polynomial $P(x)$, which affects final hardware implementation. This paper presents a computer algebra technique that performs verification and reverse engineering of GF($2^m$) multipliers directly from the gate-level implementation. The approach is based on extracting a unique irreducible polynomial in a parallel fashion and proceeds in three steps: 1) determine the bit position of the output bits; 2) determine the bit position of the input bits; and 3) extract the irreducible polynomial used in the design. We demonstrate that this method is able to reverse engineer GF($2^m$) multipliers in \textit{m} threads. Experiments performed on synthesized \textit{Mastrovito} and \textit{Montgomery} multipliers with different $P(x)$, including NIST-recommended polynomials, demonstrate high efficiency of the proposed method.
Fourier Policy Gradients
Venue: arXiv cs.LG 2018
Year: 2018

We propose a new way of deriving policy gradient updates for reinforcement learning. Our technique, based on Fourier analysis, recasts integrals that arise with expected policy gradients as convolutions and turns them into multiplications. The obtained analytical solutions allow us to capture the low variance benefits of EPG in a broad range of settings. For the critic, we treat trigonometric and radial basis functions, two function families with the universal approximation property. The choice of policy can be almost arbitrary, including mixtures or hybrid continuous-discrete probability distributions. Moreover, we derive a general family of sample-based estimators for stochastic policy gradients, which unifies existing results on sample-based approximation. We believe that this technique has the potential to shape the next generation of policy gradient approaches, powered by analytical results.
Caching-Aided Collaborative D2D Operation for Predictive Data Dissemination in Industrial IoT
Venue: arXiv cs.NI 2018
Year: 2018

Industrial automation deployments constitute challenging environments where moving IoT machines may produce high-definition video and other heavy sensor data during surveying and inspection operations. Transporting massive contents to the edge network infrastructure and then eventually to the remote human operator requires reliable and high-rate radio links supported by intelligent data caching and delivery mechanisms. In this work, we address the challenges of contents dissemination in characteristic factory automation scenarios by proposing to engage moving industrial machines as device-to-device (D2D) caching helpers. With the goal to improve reliability of high-rate millimeter-wave (mmWave) data connections, we introduce the alternative contents dissemination modes and then construct a novel mobility-aware methodology that helps develop predictive mode selection strategies based on the anticipated radio link conditions. We also conduct a thorough system-level evaluation of representative data dissemination strategies to confirm the benefits of predictive solutions that employ D2D-enabled collaborative caching at the wireless edge to lower contents delivery latency and improve data acquisition reliability.