OpenRaiser/Intern-Atlas huggingface dataset:
Eliminating the unit constant in the Lambek calculus with brackets
Venue: arXiv cs.LO 2017
Year: 2017

We present a translation of the Lambek calculus with brackets and the unit constant, $\mathbf{Lb}^{\boldsymbol{*}}_{\mathbf{1}}$, into the Lambek calculus with brackets allowing empty antecedents, but without the unit constant, $\mathbf{Lb}^{\boldsymbol{*}}$. Using this translation, we extend previously known results for $\mathbf{Lb}^{\boldsymbol{*}}$ to $\mathbf{Lb}^{\boldsymbol{*}}_{\mathbf{1}}$: (1) languages generated by categorial grammars based on the Lambek calculus with brackets are context-free (Kanazawa 2017); (2) the polynomial-time algorithm for deciding derivability of bounded depth sequents (Kanovich et al. 2017).
Exploring the Use of Shatter for AllSAT Through Ramsey-Type Problems
Venue: arXiv cs.AI 2017
Year: 2017

In the context of SAT solvers, Shatter is a popular tool for symmetry breaking on CNF formulas. Nevertheless, little has been said about its use in the context of AllSAT problems: problems where we are interested in listing all the models of a Boolean formula. AllSAT has gained much popularity in recent years due to its many applications in domains like model checking, data mining, etc. One example of a particularly transparent application of AllSAT to other fields of computer science is computational Ramsey theory. In this paper we study the effect of incorporating Shatter to the workflow of using Boolean formulas to generate all possible edge colorings of a graph avoiding prescribed monochromatic subgraphs. Generating complete sets of colorings is an important building block in computational Ramsey theory. We identify two drawbacks in the naïve use of Shatter to break the symmetries of Boolean formulas encoding Ramsey-type problems for graphs: a "blow-up" in the number of models and the generation of incomplete sets of colorings. The issues presented in this work are not intended to discourage the use of Shatter as a preprocessing tool for AllSAT problems in combinatorial computing but to help researchers properly use this tool by avoiding these potential pitfalls. To this end, we provide strategies and additional tools to cope with the negative effects of using Shatter for AllSAT. While the specific application addressed in this paper is that of Ramsey-type problems, the analysis we carry out applies to many other areas in which highly-symmetrical Boolean formulas arise and we wish to find all of their models.
Optimal Index Codes via a Duality between Index Coding and Network Coding
Venue: arXiv cs.IT 2017
Year: 2017

In Index Coding, the goal is to use a broadcast channel as efficiently as possible to communicate information from a source to multiple receivers which can possess some of the information symbols at the source as side-information. In this work, we present a duality relationship between index coding (IC) and multiple-unicast network coding (NC). It is known that the IC problem can be represented using a side-information graph $G$ (with number of vertices $n$ equal to the number of source symbols). The size of the maximum acyclic induced subgraph, denoted by $MAIS$ is a lower bound on the \textit{broadcast rate}. For IC problems with $MAIS=n-1$ and $MAIS=n-2$, prior work has shown that binary (over ${\mathbb F}_2$) linear index codes achieve the $MAIS$ lower bound for the broadcast rate and thus are optimal. In this work, we use the the duality relationship between NC and IC to show that for a class of IC problems with $MAIS=n-3$, binary linear index codes achieve the $MAIS$ lower bound on the broadcast rate. In contrast, it is known that there exists IC problems with $MAIS=n-3$ and optimal broadcast rate strictly greater than $MAIS$.
Win Prediction in Esports: Mixed-Rank Match Prediction in Multi-player Online Battle Arena Games
Venue: arXiv cs.AI 2017
Year: 2017

Esports has emerged as a popular genre for players as well as spectators, supporting a global entertainment industry. Esports analytics has evolved to address the requirement for data-driven feedback, and is focused on cyber-athlete evaluation, strategy and prediction. Towards the latter, previous work has used match data from a variety of player ranks from hobbyist to professional players. However, professional players have been shown to behave differently than lower ranked players. Given the comparatively limited supply of professional data, a key question is thus whether mixed-rank match datasets can be used to create data-driven models which predict winners in professional matches and provide a simple in-game statistic for viewers and broadcasters. Here we show that, although there is a slightly reduced accuracy, mixed-rank datasets can be used to predict the outcome of professional matches, with suitably optimized configurations.
Detecting hip fractures with radiologist-level performance using deep neural networks
Venue: arXiv cs.CV 2017
Year: 2017

We developed an automated deep learning system to detect hip fractures from frontal pelvic x-rays, an important and common radiological task. Our system was trained on a decade of clinical x-rays (~53,000 studies) and can be applied to clinical data, automatically excluding inappropriate and technically unsatisfactory studies. We demonstrate diagnostic performance equivalent to a human radiologist and an area under the ROC curve of 0.994. Translated to clinical practice, such a system has the potential to increase the efficiency of diagnosis, reduce the need for expensive additional testing, expand access to expert level medical image interpretation, and improve overall patient outcomes.
Classification of postoperative surgical site infections from blood measurements with missing data using recurrent neural networks
Venue: arXiv cs.NE 2017
Year: 2017

Clinical measurements that can be represented as time series constitute an important fraction of the electronic health records and are often both uncertain and incomplete. Recurrent neural networks are a special class of neural networks that are particularly suitable to process time series data but, in their original formulation, cannot explicitly deal with missing data. In this paper, we explore imputation strategies for handling missing values in classifiers based on recurrent neural network (RNN) and apply a recently proposed recurrent architecture, the Gated Recurrent Unit with Decay, specifically designed to handle missing data. We focus on the problem of detecting surgical site infection in patients by analyzing time series of their blood sample measurements and we compare the results obtained with different RNN-based classifiers.
Graph Clustering using Effective Resistance
Venue: arXiv cs.DS 2017
Year: 2017

$ \def\vecc#1{\boldsymbol{#1}} $We design a polynomial time algorithm that for any weighted undirected graph $G = (V, E,\vecc w)$ and sufficiently large $δ> 1$, partitions $V$ into subsets $V_1, \ldots, V_h$ for some $h\geq 1$, such that $\bullet$ at most $δ^{-1}$ fraction of the weights are between clusters, i.e. \[ w(E - \cup_{i = 1}^h E(V_i)) \lesssim \frac{w(E)}δ;\] $\bullet$ the effective resistance diameter of each of the induced subgraphs $G[V_i]$ is at most $δ^3$ times the average weighted degree, i.e. \[ \max_{u, v \in V_i} \mathsf{Reff}_{G[V_i]}(u, v) \lesssim δ^3 \cdot \frac{|V|}{w(E)} \quad \text{ for all } i=1, \ldots, h.\] In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices $u$ and $v$ is large, then there must be a low conductance cut separating $u$ from $v$. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
Depth Assisted Full Resolution Network for Single Image-based View Synthesis
Venue: arXiv cs.CV 2017
Year: 2017

Researches in novel viewpoint synthesis majorly focus on interpolation from multi-view input images. In this paper, we focus on a more challenging and ill-posed problem that is to synthesize novel viewpoints from one single input image. To achieve this goal, we propose a novel deep learning-based technique. We design a full resolution network that extracts local image features with the same resolution of the input, which contributes to derive high resolution and prevent blurry artifacts in the final synthesized images. We also involve a pre-trained depth estimation network into our system, and thus 3D information is able to be utilized to infer the flow field between the input and the target image. Since the depth network is trained by depth order information between arbitrary pairs of points in the scene, global image features are also involved into our system. Finally, a synthesis layer is used to not only warp the observed pixels to the desired positions but also hallucinate the missing pixels with recorded pixels. Experiments show that our technique performs well on images of various scenes, and outperforms the state-of-the-art techniques.
ATRank: An Attention-Based User Behavior Modeling Framework for Recommendation
Venue: arXiv cs.AI 2017
Year: 2017

A user can be represented as what he/she does along the history. A common way to deal with the user modeling problem is to manually extract all kinds of aggregated features over the heterogeneous behaviors, which may fail to fully represent the data itself due to limited human instinct. Recent works usually use RNN-based methods to give an overall embedding of a behavior sequence, which then could be exploited by the downstream applications. However, this can only preserve very limited information, or aggregated memories of a person. When a downstream application requires to facilitate the modeled user features, it may lose the integrity of the specific highly correlated behavior of the user, and introduce noises derived from unrelated behaviors. This paper proposes an attention based user behavior modeling framework called ATRank, which we mainly use for recommendation tasks. Heterogeneous user behaviors are considered in our model that we project all types of behaviors into multiple latent semantic spaces, where influence can be made among the behaviors via self-attention. Downstream applications then can use the user behavior vectors via vanilla attention. Experiments show that ATRank can achieve better performance and faster training process. We further explore ATRank to use one unified model to predict different types of user behaviors at the same time, showing a comparable performance with the highly optimized individual models.
Phonological (un)certainty weights lexical activation
Venue: arXiv cs.CL 2017
Year: 2017

Spoken word recognition involves at least two basic computations. First is matching acoustic input to phonological categories (e.g. /b/, /p/, /d/). Second is activating words consistent with those phonological categories. Here we test the hypothesis that the listener's probability distribution over lexical items is weighted by the outcome of both computations: uncertainty about phonological discretisation and the frequency of the selected word(s). To test this, we record neural responses in auditory cortex using magnetoencephalography, and model this activity as a function of the size and relative activation of lexical candidates. Our findings indicate that towards the beginning of a word, the processing system indeed weights lexical candidates by both phonological certainty and lexical frequency; however, later into the word, activation is weighted by frequency alone.
Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints
Venue: arXiv cs.GT 2017
Year: 2017

We study a problem of optimal information gathering from multiple data providers that need to be incentivized to provide accurate information. This problem arises in many real world applications that rely on crowdsourced data sets, but where the process of obtaining data is costly. A notable example of such a scenario is crowd sensing. To this end, we formulate the problem of optimal information gathering as maximization of a submodular function under a budget constraint, where the budget represents the total expected payment to data providers. Contrary to the existing approaches, we base our payments on incentives for accuracy and truthfulness, in particular, {\em peer-prediction} methods that score each of the selected data providers against its best peer, while ensuring that the minimum expected payment is above a given threshold. We first show that the problem at hand is hard to approximate within a constant factor that is not dependent on the properties of the payment function. However, for given topological and analytical properties of the instance, we construct two greedy algorithms, respectively called PPCGreedy and PPCGreedyIter, and establish theoretical bounds on their performance w.r.t. the optimal solution. Finally, we evaluate our methods using a realistic crowd sensing testbed.
Algorithms and Data Structures to Accelerate Network Analysis
Venue: arXiv cs.NI 2017
Year: 2017

As the sheer amount of computer generated data continues to grow exponentially, new bottlenecks are unveiled that require rethinking our traditional software and hardware architectures. In this paper we present five algorithms and data structures (long queue emulation, lockless bimodal queues, tail early dropping, LFN tables, and multiresolution priority queues) designed to optimize the process of analyzing network traffic. We integrated these optimizations on R-Scope, a high performance network appliance that runs the Bro network analyzer, and present benchmarks showcasing performance speed ups of 5X at traffic rates of 10 Gbps.
Mitigating Read-disturbance Errors in STT-RAM Caches by Using Data Compression
Venue: arXiv cs.AR 2017
Year: 2017

Due to its high density and close-to-SRAM read latency, spin transfer torque RAM (STT-RAM) is considered one of the most-promising emerging memory technologies for designing large last level caches (LLCs). However, in deep sub-micron region, STT-RAM shows read-disturbance error (RDE) whereby a read operation may modify the stored data value and this presents a severe threat to performance and reliability of STT-RAM caches. In this paper, we present a technique, named SHIELD, to mitigate RDE in STT-RAM LLCs. SHIELD uses data compression to reduce number of read operations from STT-RAM blocks to avoid RDE and also to reduce the number of bits written to cache during both write and restore operations. Experimental results have shown that SHIELD provides significant improvement in performance and energy efficiency. SHIELD consumes smaller energy than two previous RDE-mitigation techniques, namely high-current restore required read (HCRR, also called restore-after-read) and low-current long latency read (LCLL) and even an ideal RDE-free STT-RAM cache.
Co-attending Free-form Regions and Detections with Multi-modal Multiplicative Feature Embedding for Visual Question Answering
Venue: arXiv cs.CV 2017
Year: 2017

Recently, the Visual Question Answering (VQA) task has gained increasing attention in artificial intelligence. Existing VQA methods mainly adopt the visual attention mechanism to associate the input question with corresponding image regions for effective question answering. The free-form region based and the detection-based visual attention mechanisms are mostly investigated, with the former ones attending free-form image regions and the latter ones attending pre-specified detection-box regions. We argue that the two attention mechanisms are able to provide complementary information and should be effectively integrated to better solve the VQA problem. In this paper, we propose a novel deep neural network for VQA that integrates both attention mechanisms. Our proposed framework effectively fuses features from free-form image regions, detection boxes, and question representations via a multi-modal multiplicative feature embedding scheme to jointly attend question-related free-form image regions and detection boxes for more accurate question answering. The proposed method is extensively evaluated on two publicly available datasets, COCO-QA and VQA, and outperforms state-of-the-art approaches. Source code is available at https://github.com/lupantech/dual-mfa-vqa.
Robotic frameworks, architectures and middleware comparison
Venue: arXiv cs.RO 2017
Year: 2017

Nowadays, the construction of a complex robotic system requires a high level of specialization in a large number of diverse scientific areas. It is reasonable that a single researcher cannot create from scratch the entirety of this system, as it is impossible for him to have the necessary skills in the necessary fields. This obstacle is being surpassed with the existent robotic frameworks. This paper tries to give an extensive review of the most famous robotic frameworks and middleware, as well as to provide the means to effortlessly compare them. Additionally, we try to investigate the differences between the definitions of a robotic framework, a robotic middleware and a robotic architecture.
Learning Dynamics and the Co-Evolution of Competing Sexual Species
Venue: arXiv cs.GT 2017
Year: 2017

We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model of Livnat \etal~\cite{evolfocs14} the fitness of an individual depends on whether the truth assignments on $n$ variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an evolutionary race with the parasite enjoying the advantage if the value of its Boolean function matches its host, and the host wishing to mismatch its parasite. Surprisingly, this model makes a simple and robust behavioral prediction. The typical system behavior is \textit{periodic}. These cycles stay bounded away from the boundary and thus, \textit{learning-dynamics competition between sexual species can provide an explanation for genetic diversity.} This explanation is due solely to the natural selection process. No mutations, environmental changes, etc., need be invoked. The game played at the gene level may have many Nash equilibria with widely diverse fitness levels. Nevertheless, sexual evolution leads to gene coordination that implements an optimal strategy, i.e., an optimal population mixture, at the species level. Namely, the play of the many "selfish genes" implements a time-averaged correlated equilibrium where the average fitness of each species is exactly equal to its value in the two species zero-sum competition. Our analysis combines tools from game theory, dynamical systems and Boolean functions to establish a novel class of conservative dynamical systems.
Enhanced Group Sparse Beamforming for Green Cloud-RAN: A Random Matrix Approach
Venue: arXiv cs.IT 2017
Year: 2017

Group sparse beamforming is a general framework to minimize the network power consumption for cloud radio access networks (Cloud-RANs), which, however, suffers high computational complexity. In particular, a complex optimization problem needs to be solved to obtain the remote radio head (RRH) ordering criterion in each transmission block, which will help to determine the active RRHs and the associated fronthaul links. In this paper, we propose innovative approaches to reduce the complexity of this key step in group sparse beamforming. Specifically, we first develop a smoothed $\ell_p$-minimization approach with the iterative reweighted-$\ell_2$ algorithm to return a Karush-Kuhn-Tucker (KKT) point solution, as well as enhancing the capability of inducing group sparsity in the beamforming vectors. By leveraging the Lagrangian duality theory, we obtain closed-form solutions at each iteration to reduce the computational complexity. The well-structured solutions provide the opportunities to apply the large-dimensional random matrix theory to derive deterministic approximations for the RRH ordering criterion. Such an approach helps to guide the RRH selection only based on the statistical channel state information (CSI), which does not require frequent update, thereby significantly reducing the computation overhead. Simulation results shall demonstrate the performance gains of the proposed $\ell_p$-minimization approach, as well as the effectiveness of the large system analysis based framework for computing RRH ordering criterion.
Two-level schemes for the advection equation
Venue: arXiv cs.NA 2017
Year: 2017

The advection equation is the basis for mathematical models of continuum mechanics. In the approximate solution of nonstationary problems it is necessary to inherit main properties of the conservatism and monotonicity of the solution. In this paper, the advection equation is written in the symmetric form, where the advection operator is the half-sum of advection operators in conservative (divergent) and non-conservative (characteristic) forms. The advection operator is skew-symmetric. Standard finite element approximations in space are used. The standart explicit two-level scheme for the advection equation is absolutly unstable. New conditionally stable regularized schemes are constructed, on the basis of the general theory of stability (well-posedness) of operator-difference schemes, the stability conditions of the explicit Lax-Wendroff scheme are established. Unconditionally stable and conservative schemes are implicit schemes of the second (Crank-Nicolson scheme) and fourth order. The conditionally stable implicit Lax-Wendroff scheme is constructed. The accuracy of the investigated explicit and implicit two-level schemes for an approximate solution of the advection equation is illustrated by the numerical results of a model two-dimensional problem.
The destiny of constant structure discrete time closed semantic systems
Venue: arXiv cs.AI 2017
Year: 2017

Constant structure closed semantic systems are the systems each element of which receives its definition through the correspondent unchangeable set of other elements of the system. Discrete time means here that the definitions of the elements change iteratively and simultaneously based on the "neighbor portraits" from the previous iteration. I prove that the iterative redefinition process in such class of systems will quickly degenerate into a series of pairwise isomorphic states and discuss some directions of further research.
The process of 3D-printed skull models for the anatomy education
Venue: arXiv cs.OH 2017
Year: 2017

Objective The 3D printed medical models can come from virtual digital resources, like CT scanning. Nevertheless, the accuracy of CT scanning technology is limited, which is 1mm. In this situation, the collected data is not exactly the same as the real structure and there might be some errors causing the print to fail. This study presents a common and practical way to process the skull data to make the structures correctly. And then we make a skull model through 3D printing technology, which is useful for medical students to understand the complex structure of skull. Materials and Methods The skull data is collected by the CT scan. To get a corrected medical model, the computer-assisted image processing goes with the combination of five 3D manipulation tools: Mimics, 3ds Max, Geomagic, Mudbox and Meshmixer, to reconstruct the digital model and repair it. Subsequently, we utilize a low-cost desktop 3D printer, Ultimaker2, with polylactide filament (PLA) material to print the model and paint it based on the atlas. Result After the restoration and repairing, we eliminate the errors and repair the model by adding the missing parts of the uploaded data within 6 hours. Then we print it and compare the model with the cadaveric skull from frontal, left, right and anterior views respectively. The printed model can show the same structures and also the details of the skull clearly and is a good alternative of the cadaveric skull.