OpenRaiser/Intern-Atlas huggingface dataset:
Text Coherence Analysis Based on Deep Neural Network
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we propose a novel deep coherence model (DCM) using a convolutional neural network architecture to capture the text coherence. The text coherence problem is investigated with a new perspective of learning sentence distributional representation and text coherence modeling simultaneously. In particular, the model captures the interactions between sentences by computing the similarities of their distributional representations. Further, it can be easily trained in an end-to-end fashion. The proposed model is evaluated on a standard Sentence Ordering task. The experimental results demonstrate its effectiveness and promise in coherence assessment showing a significant improvement over the state-of-the-art by a wide margin.
A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity
Venue: arXiv cs.LG 2017
Year: 2017

SGD (Stochastic Gradient Descent) is a popular algorithm for large scale optimization problems due to its low iterative cost. However, SGD can not achieve linear convergence rate as FGD (Full Gradient Descent) because of the inherent gradient variance. To attack the problem, mini-batch SGD was proposed to get a trade-off in terms of convergence rate and iteration cost. In this paper, a general CVI (Convergence-Variance Inequality) equation is presented to state formally the interaction of convergence rate and gradient variance. Then a novel algorithm named SSAG (Stochastic Stratified Average Gradient) is introduced to reduce gradient variance based on two techniques, stratified sampling and averaging over iterations that is a key idea in SAG (Stochastic Average Gradient). Furthermore, SSAG can achieve linear convergence rate of $\mathcal {O}((1-\fracμ{8CL})^k)$ at smaller storage and iterative costs, where $C\geq 2$ is the category number of training data. This convergence rate depends mainly on the variance between classes, but not on the variance within the classes. In the case of $C\ll N$ ($N$ is the training data size), SSAG's convergence rate is much better than SAG's convergence rate of $\mathcal {O}((1-\fracμ{8NL})^k)$. Our experimental results show SSAG outperforms SAG and many other algorithms.
Performance Analysis of Millimeter-Wave Relaying: Impacts of Beamwidth and Self-Interference
Venue: arXiv cs.NI 2017
Year: 2017

We study the maximum achievable rate of a two-hop amplified-and-forward (AF) relaying millimeter-wave (mm-wave) system, where two AF relaying schemes, i.e., half-duplex (HD) and full-duplex (FD) are discussed. By considering the two-ray mm-wave channel and the Gaussian-type directional antenna, jointly, the impacts of the beamwidth and the self-interference coefficient on maximum achievable rates are investigated. Results show that, under a sum-power constraint, the rate of FD-AF mm-wave relaying outperforms its HD counterpart only when antennas with narrower beamwidth and smaller self-interference coefficient are applied. However, when the sum-power budget is sufficiently high or the beamwidth of directional antenna is sufficiently small, direct transmission becomes the best strategy, rather than the AF relaying schemes. For both relaying schemes, we show that the rates of both AF relaying schemes scale as $ \mathcal{O}\left(\min\left\lbraceθ_m^{-1},θ_m^{-2}\right\rbrace\right) $ with respect to beamwidth $ θ_ m $, and the rate of FD-AF relaying scales as $ \mathcal{O}\left(μ^{-\frac{1}{2}}\right) $ with respect to self-interference coefficient $ μ$. Besides, we show that, ground reflections may significantly affect the performance of mm-wave communications, constructively or destructively. Thus, the impact of ground reflections deserves careful considerations for analyzing or designing future mm-wave wireless networks.
Superposed Episodic and Semantic Memory via Sparse Distributed Representation
Venue: arXiv cs.NE 2017
Year: 2017

The abilities to perceive, learn, and use generalities, similarities, classes, i.e., semantic memory (SM), is central to cognition. Machine learning (ML), neural network, and AI research has been primarily driven by tasks requiring such abilities. However, another central facet of cognition, single-trial formation of permanent memories of experiences, i.e., episodic memory (EM), has had relatively little focus. Only recently has EM-like functionality been added to Deep Learning (DL) models, e.g., Neural Turing Machine, Memory Networks. However, in these cases: a) EM is implemented as a separate module, which entails substantial data movement (and so, time and power) between the DL net itself and EM; and b) individual items are stored localistically within the EM, precluding realizing the exponential representational efficiency of distributed over localist coding. We describe Sparsey, an unsupervised, hierarchical, spatial/spatiotemporal associative memory model differing fundamentally from mainstream ML models, most crucially, in its use of sparse distributed representations (SDRs), or, cell assemblies, which admits an extremely efficient, single-trial learning algorithm that maps input similarity into code space similarity (measured as intersection). SDRs of individual inputs are stored in superposition and because similarity is preserved, the patterns of intersections over the assigned codes reflect the similarity, i.e., statistical, structure, of all orders, not simply pairwise, over the inputs. Thus, SM, i.e., a generative model, is built as a computationally free side effect of the act of storing episodic memory traces of individual inputs, either spatial patterns or sequences. We report initial results on MNIST and on the Weizmann video event recognition benchmarks. While we have not yet attained SOTA class accuracy, learning takes only minutes on a single CPU.
Seamless Paxos Coordinators
Venue: arXiv cs.DC 2017
Year: 2017

The Paxos algorithm requires a single correct coordinator process to operate. After a failure, the replacement of the coordinator may lead to a temporary unavailability of the application implemented atop Paxos. So far, this unavailability has been addressed by reducing the coordinator replacement rate through the use of stable coordinator selection algorithms. We have observed that the cost of recovery of the newly elected coordinator's state is at the core of this unavailability problem. In this paper we present a new technique to manage coordinator replacement that allows the recovery to occur concurrently with new consensus rounds. Experimental results show that our seamless approach effectively solves the temporary unavailability problem, its adoption entails uninterrupted execution of the application. Our solution removes the restriction that the occurrence of coordinator replacements is something to be avoided, allowing the decoupling of the application execution from the accuracy of the mechanism used to choose a coordinator. This result increases the performance of the application even in the presence of failures, it is of special importance to the autonomous operation of replicated applications that have to adapt to varying network conditions and partial failures.
On the Duality of Fractional Repetition Codes
Venue: arXiv cs.IT 2017
Year: 2017

Erasure codes have emerged as an efficient technology for providing data redundancy in distributed storage systems. However, it is a challenging task to repair the failed storage nodes in erasure-coded storage systems, which requires large quantities of network resources. In this paper, we study fractional repetition (FR) codes, which enable the minimal repair complexity and also minimum repair bandwidth during node repair. We focus on the duality of FR codes, and investigate the relationship between the supported file size of an FR code and its dual code. Furthermore, we present a dual bound on the supported file size of FR codes.
Joint Pilot Allocation and Robust Transmission Design for Ultra-dense User-centric TDD C-RAN with Imperfect CSI
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the unavailability of complete channel state information (CSI) in ultra-dense cloud radio access networks (C-RANs). The user-centric cluster is adopted to reduce the computational complexity, while the incomplete CSI is considered to reduce the heavy channel training overhead, where only large-scale inter-cluster CSI is available. Channel estimation for intra-cluster CSI is also considered, where we formulate a joint pilot allocation and user equipment (UE) selection problem to maximize the number of admitted UEs with fixed number of pilots. A novel pilot allocation algorithm is proposed by considering the multi-UE pilot interference. Then, we consider robust beam-vector optimization problem subject to UEs' data rate requirements and fronthaul capacity constraints, where the channel estimation error and incomplete inter-cluster CSI are considered. The exact data rate is difficult to obtain in closed form, and instead we conservatively replace it with its lower-bound. The resulting problem is non-convex, combinatorial, and even infeasible. A practical algorithm, based on UE selection, successive convex approximation (SCA) and semi-definite relaxation approach, is proposed to solve this problem with guaranteed convergence. We strictly prove that semidefinite relaxation is tight with probability 1. Finally, extensive simulation results are presented to show the fast convergence of our proposed algorithm and demonstrate its superiority over the existing algorithms.
A Multi-Bit Neuromorphic Weight Cell using Ferroelectric FETs, suitable for SoC Integration
Venue: arXiv cs.ET 2017
Year: 2017

A multi-bit digital weight cell for high-performance, inference-only non-GPU-like neuromorphic accelerators is presented. The cell is designed with simplicity of peripheral circuitry in mind. Non-volatile storage of weights which eliminates the need for DRAM access is based on FeFETs and is purely digital. The Multiply-and-Accumulate operation is performed using passive resistors, gated by FeFETs. The resulting weight cell offers a high degree of linearity and a large ON/OFF ratio. The key performance tradeoffs are investigated, and the device requirements are elucidated.
On the Coordinator's Rule for Fast Paxos
Venue: arXiv cs.DC 2017
Year: 2017

Fast Paxos is an algorithm for consensus that works by a succession of rounds, where each round tries to decide a value $v$ that is consistent with all past rounds. Rounds are started by a coordinator process and consistency is guaranteed by the rule used by this process for the selection of $v$ and by the properties of process sets called quorums. We show a simplified version of this rule for the specific case where the quorums are defined by the cardinality of these process sets. This rule is of special interest for implementors of the algorithm.
Aggregating Algorithm for Prediction of Packs
Venue: arXiv cs.LG 2017
Year: 2017

This paper formulates the protocol for prediction of packs, which a special case of prediction under delayed feedback. Under this protocol, the learner must make a few predictions without seeing the outcomes and then the outcomes are revealed. We develop the theory of prediction with expert advice for packs. By applying Vovk's Aggregating Algorithm to this problem we obtain a number of algorithms with tight upper bounds. We carry out empirical experiments on housing data.
Design of a Robotic System for Diagnosis and Rehabilitation of Lower Limbs
Venue: arXiv cs.RO 2017
Year: 2017

Currently, lower limb robotic rehabilitation is widely developed, However, the devices used so far seem to not have a uniform criteria for their design, because, on the contrary, each developed mechanism is often presented as if it does not take into account the criteria used in previous designs. On the other hand, the diagnosis of lower limb from robotic devices has been little studied. This chapter presents a guide for the design of robotic devices in diagnosis of lower limbs, taking into account the mobility of the human leg and the techniques used by physiotherapists in the execution of exercises and the rehabilitation of rehabilitation and diagnosis tests, as well as the recommendations made by various authors, among other aspects. The proposed guide is illustrated through a case study based on a parallel robot RPU+3UPS able to make movements that are applied during the processes of rehabilitation and diagnosis. The proposal presents advantages over some existing devices such as its load capacity that can support, and also allows you to restrict the movement in directions required by the rehabilitation and the diagnosis movements.
Generic 3D Representation via Pose Estimation and Matching
Venue: arXiv cs.CV 2017
Year: 2017

Though a large body of computer vision research has investigated developing generic semantic representations, efforts towards developing a similar representation for 3D has been limited. In this paper, we learn a generic 3D representation through solving a set of foundational proxy 3D tasks: object-centric camera pose estimation and wide baseline feature matching. Our method is based upon the premise that by providing supervision over a set of carefully selected foundational tasks, generalization to novel tasks and abstraction capabilities can be achieved. We empirically show that the internal representation of a multi-task ConvNet trained to solve the above core problems generalizes to novel 3D tasks (e.g., scene layout estimation, object pose estimation, surface normal estimation) without the need for fine-tuning and shows traits of abstraction abilities (e.g., cross-modality pose estimation). In the context of the core supervised tasks, we demonstrate our representation achieves state-of-the-art wide baseline feature matching results without requiring apriori rectification (unlike SIFT and the majority of learned features). We also show 6DOF camera pose estimation given a pair local image patches. The accuracy of both supervised tasks come comparable to humans. Finally, we contribute a large-scale dataset composed of object-centric street view scenes along with point correspondences and camera pose information, and conclude with a discussion on the learned representation and open research questions.
Amorphous Dynamic Partial Reconfiguration with Flexible Boundaries to Remove Fragmentation
Venue: arXiv cs.AR 2017
Year: 2017

Dynamic partial reconfiguration (DPR) allows one region of an field-programmable gate array (FPGA) fabric to be reconfigured without affecting the operations on the rest of the fabric. To use an FPGA as a dynamically shared compute resource, one could partition and manage an FPGA fabric as multiple DPR partitions that can be independently reconfigured at runtime with different application function units (AFUs). Unfortunately, dividing a fabric into DPR partitions with fixed boundaries causes the available fabric resources to become fragmented. An AFU of a given size cannot be loaded unless a sufficiently large DPR partition was floorplanned at build time. To overcome this inefficiency, we devised an "amorphous" DPR technique that is compatible with current device and tool support but does not require the DPR partition boundaries to be a priori fixed. A collection of AFU bitstreams can be simultaneously loaded on the fabric if their footprints (the actual area used by an AFU) in the fabric do not overlap. We verified the feasibility of amorphous DPR on Xilinx Zynq System-on-Chip (SoC) FPGAs using Vivado. We evaluated the benefits of amorphous DPR in the context of a dynamically reconfigurable vision processing pipeline framework.
Strategy Preserving Compilation for Parallel Functional Code
Venue: arXiv cs.DC 2017
Year: 2017

Graphics Processing Units (GPUs) and other parallel devices are widely available and have the potential for accelerating a wide class of algorithms. However, expert programming skills are required to achieving maximum performance. hese devices expose low-level hardware details through imperative programming interfaces where programmers explicity encode device-specific optimisation strategies. This inevitably results in non-performance-portable programs delivering suboptimal performance on other devices. Functional programming models have recently seen a renaissance in the systems community as they offer possible solutions for tackling the performance portability challenge. Recent work has shown how to automatically choose high-performance parallelisation strategies for a wide range of hardware architectures encoded in a functional representation. However, the translation of such functional representations to the imperative program expected by the hardware interface is typically performed ad hoc with no correctness guarantees and no guarantees to preserve the intended parallelisation strategy. In this paper, we present a formalised strategy-preserving translation from high-level functional code to low-level data race free parallel imperative code. This translation is formulated and proved correct within a language we call Data Parallel Idealised Algol (DPIA), a dialect of Reynolds' Idealised Algol. Performance results on GPUs and a multicore CPU show that the formalised translation process generates low-level code with performance on a par with code generated from ad hoc approaches.
A Unified Spectral Method for FPDEs with Two-sided Derivatives; A Fast Solver
Venue: arXiv cs.CE 2017
Year: 2017

We develop a unified Petrov-Galerkin spectral method for a class of fractional partial differential equations with two-sided derivatives and constant coefficients of the form $ _{0}{\mathcal{D}}_{t}^{2τ}u^{} + \sum_{i=1}^{d}$ $[c_{l_i}$ $_{a_i}{\mathcal{D}}_{x_i}^{2μ_i} u^{} +c_{r_i}$ $_{x_i}{\mathcal{D}}_{b_i}^{2μ_i}$ $u^{} ] +$ $γ$ $u^{} = \sum_{j=1}^{d} [ κ_{l_j}$ $_{a_j}{\mathcal{D}}_{x_j}^{2ν_j} u^{}$ $+κ_{r_j}$ $_{x_j}{\mathcal{D}}_{b_j}^{2ν_j}$ $u^{} ]$ $+ f$, where $2τ\in (0,2)$, $2μ_i \in (0,1)$ and $2ν_j \in (1,2)$, in a ($1+d$)-dimensional \textit{space-time} hypercube, $d = 1, 2, 3, \cdots$, subject to homogeneous Dirichlet initial/boundary conditions. We employ the eigenfunctions of the fractional Sturm-Liouville eigen-problems of the first kind in \cite{zayernouri2013fractional}, called \textit{Jacobi poly-fractonomial}s, as temporal bases, and the eigen-functions of the boundary-value problem of the second kind as temporal test functions. Next, we construct our spatial basis/test functions using Legendre polynomials, yielding mass matrices being independent of the spatial fractional orders ($μ_i, \, ν_j, \, i, \,j=1,2,\cdots,d$). Furthermore, we formulate a novel unified fast linear solver for the resulting high-dimensional linear system based on the solution of generalized eigen-problem of spatial mass matrices with respect to the corresponding stiffness matrices, hence, making the complexity of the problem optimal, i.e., $\mathcal{O}(N^{d+2})$. We carry out several numerical test cases to examine the CPU time and convergence rate of the method. The corresponding stability and error analysis of the Petrov-Galerkin method are carried out in \cite{samiee2016Unified2}.
An FPT Algorithm Beating 2-Approximation for $k$-Cut
Venue: arXiv cs.DS 2017
Year: 2017

In the $k$-Cut problem, we are given an edge-weighted graph $G$ and an integer $k$, and have to remove a set of edges with minimum total weight so that $G$ has at least $k$ connected components. Prior work on this problem gives, for all $h \in [2,k]$, a $(2-h/k)$-approximation algorithm for $k$-cut that runs in time $n^{O(h)}$. Hence to get a $(2 - \varepsilon)$-approximation algorithm for some absolute constant $\varepsilon$, the best runtime using prior techniques is $n^{O(k\varepsilon)}$. Moreover, it was recently shown that getting a $(2 - \varepsilon)$-approximation for general $k$ is NP-hard, assuming the Small Set Expansion Hypothesis. If we use the size of the cut as the parameter, an FPT algorithm to find the exact $k$-Cut is known, but solving the $k$-Cut problem exactly is $W[1]$-hard if we parameterize only by the natural parameter of $k$. An immediate question is: \emph{can we approximate $k$-Cut better in FPT-time, using $k$ as the parameter?} We answer this question positively. We show that for some absolute constant $\varepsilon > 0$, there exists a $(2 - \varepsilon)$-approximation algorithm that runs in time $2^{O(k^6)} \cdot \widetilde{O} (n^4)$. This is the first FPT algorithm that is parameterized only by $k$ and strictly improves the $2$-approximation.
Interpreting Contextual Effects By Contextual Modeling In Recommender Systems
Venue: arXiv cs.IR 2017
Year: 2017

Recommender systems have been widely applied to assist user's decision making by providing a list of personalized item recommendations. Context-aware recommender systems (CARS) additionally take context information into considering in the recommendation process, since user's tastes on the items may vary from contexts to contexts. Several context-aware recommendation algorithms have been proposed and developed to improve the quality of recommendations. However, there are limited research which explore and discuss the capability of interpreting the contextual effects by the recommendation models. In this paper, we specifically focus on different contextual modeling approaches, reshape the structure of the models, and exploit how to utilize the existing contextual modeling to interpret the contextual effects in the recommender systems. We compare the explanations of contextual effects, as well as the recommendation performance over two-real world data sets in order to examine the quality of interpretations.
Video Labeling for Automatic Video Surveillance in Security Domains
Venue: arXiv cs.CY 2017
Year: 2017

Beyond traditional security methods, unmanned aerial vehicles (UAVs) have become an important surveillance tool used in security domains to collect the required annotated data. However, collecting annotated data from videos taken by UAVs efficiently, and using these data to build datasets that can be used for learning payoffs or adversary behaviors in game-theoretic approaches and security applications, is an under-explored research question. This paper presents VIOLA, a novel labeling application that includes (i) a workload distribution framework to efficiently gather human labels from videos in a secured manner; (ii) a software interface with features designed for labeling videos taken by UAVs in the domain of wildlife security. We also present the evolution of VIOLA and analyze how the changes made in the development process relate to the efficiency of labeling, including when seemingly obvious improvements did not lead to increased efficiency. VIOLA enables collecting massive amounts of data with detailed information from challenging security videos such as those collected aboard UAVs for wildlife security. VIOLA will lead to the development of new approaches that integrate deep learning for real-time detection and response.
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
Venue: arXiv cs.CC 2017
Year: 2017

The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field GF(2). The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.