OpenRaiser/Intern-Atlas huggingface dataset:
Application of Wrench based Feasibility Analysis to the Online Trajectory Optimization of Legged Robots
Venue: arXiv cs.RO 2018
Year: 2018

Motion planning in multi-contact scenarios has recently gathered interest within the legged robotics community, however actuator force/torque limits are rarely considered. We believe that these limits gain paramount importance when the complexity of the terrains to be traversed increases. We build on previous research from the field of robotic grasping to propose two new six-dimensional bounded polytopes named the Actuation Wrench Polytope (AWP) and the Feasible Wrench Polytope (FWP). We define the AWP as the set of all the wrenches that a robot can generate while considering its actuation limits. This considers the admissible contact forces that the robot can generate given its current configuration and actuation capabilities. The Contact Wrench Cone (CWC), instead, includes features of the environment such as the contact normal or the friction coefficient. The intersection of the AWP and of the CWC results in a convex polytope, the FWP, which turns out to be more descriptive of the real robot capabilities than existing simplified models, while maintaining the same compact representation. We explain how to efficiently compute the vertex-description of the FWP that is then used to evaluate a feasibility factor that we adapted from the field of robotic grasping. This allows us to optimize for robustness to external disturbance wrenches. Based on this, we present an implementation of a motion planner for our quadruped robot HyQ that provides online Center of Mass (CoM) trajectories that are guaranteed to be statically stable and actuation consistent.
Cross-language Framework for Word Recognition and Spotting of Indic Scripts
Venue: arXiv cs.CV 2018
Year: 2018

Handwritten word recognition and spotting of low-resource scripts are difficult as sufficient training data is not available and it is often expensive for collecting data of such scripts. This paper presents a novel cross language platform for handwritten word recognition and spotting for such low-resource scripts where training is performed with a sufficiently large dataset of an available script (considered as source script) and testing is done on other scripts (considered as target script). Training with one source script and testing with another script to have a reasonable result is not easy in handwriting domain due to the complex nature of handwriting variability among scripts. Also it is difficult in mapping between source and target characters when they appear in cursive word images. The proposed Indic cross language framework exploits a large resource of dataset for training and uses it for recognizing and spotting text of other target scripts where sufficient amount of training data is not available. Since, Indic scripts are mostly written in 3 zones, namely, upper, middle and lower, we employ zone-wise character (or component) mapping for efficient learning purpose. The performance of our cross-language framework depends on the extent of similarity between the source and target scripts. Hence, we devise an entropy based script similarity score using source to target character mapping that will provide a feasibility of cross language transcription. We have tested our approach in three Indic scripts, namely, Bangla, Devanagari and Gurumukhi, and the corresponding results are reported.
Scale-Space Anisotropic Total Variation for Limited Angle Tomography
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses streak reduction in limited angle tomography. Although the iterative reweighted total variation (wTV) algorithm reduces small streaks well, it is rather inept at eliminating large ones since total variation (TV) regularization is scale-dependent and may regard these streaks as homogeneous areas. Hence, the main purpose of this paper is to reduce streak artifacts at various scales. We propose the scale-space anisotropic total variation (ssaTV) algorithm in two different implementations. The first implementation (ssaTV-1) utilizes an anisotropic gradient-like operator which uses 2s neighboring pixels along the streaks' normal direction at each scale s. The second implementation (ssaTV-2) makes use of anisotropic down-sampling and up-sampling operations, similarly oriented along the streaks' normal direction, to apply TV regularization at various scales. Experiments on numerical and clinical data demonstrate that both ssaTV algorithms reduce streak artifacts more effectively and efficiently than wTV, particularly when using multiple scales.
Unsupervised Word Mapping Using Structural Similarities in Monolingual Embeddings
Venue: arXiv cs.CL 2018
Year: 2018

Most existing methods for automatic bilingual dictionary induction rely on prior alignments between the source and target languages, such as parallel corpora or seed dictionaries. For many language pairs, such supervised alignments are not readily available. We propose an unsupervised approach for learning a bilingual dictionary for a pair of languages given their independently-learned monolingual word embeddings. The proposed method exploits local and global structures in monolingual vector spaces to align them such that similar words are mapped to each other. We show empirically that the performance of bilingual correspondents learned using our proposed unsupervised method is comparable to that of using supervised bilingual correspondents from a seed dictionary.
Enumerating maximal cliques in link streams with durations
Venue: arXiv cs.DS 2018
Year: 2018

Link streams model interactions over time, and a clique in a link stream is defined as a set of nodes and a time interval such that all pairs of nodes in this set interact permanently during this time interval. This notion was introduced recently in the case where interactions are instantaneous. We generalize it to the case of interactions with durations and show that the instantaneous case actually is a particular case of the case with durations. We propose an algorithm to detect maximal cliques that improves our previous one for instantaneous link streams, and performs better than the state of the art algorithms in several cases of interest.
Codes Correcting Two Deletions
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we investigate the problem of constructing codes capable of correcting two deletions. In particular, we construct a code that requires redundancy approximately 8 log n + O(log log n) bits of redundancy, where n is the length of the code. To the best of the author's knowledge, this represents the best known construction in that it requires the lowest number of redundant bits for a code correcting two deletions.
Dataflow Matrix Machines and V-values: a Bridge between Programs and Neural Nets
Venue: arXiv cs.NE 2018
Year: 2018

1) Dataflow matrix machines (DMMs) generalize neural nets by replacing streams of numbers with linear streams (streams supporting linear combinations), allowing arbitrary input and output arities for activation functions, countable-sized networks with finite dynamically changeable active part capable of unbounded growth, and a very expressive self-referential mechanism. 2) DMMs are suitable for general-purpose programming, while retaining the key property of recurrent neural networks: programs are expressed via matrices of real numbers, and continuous changes to those matrices produce arbitrarily small variations in the associated programs. 3) Spaces of V-values (vector-like elements based on nested maps) are particularly useful, enabling DMMs with variadic activation functions and conveniently representing conventional data structures.
Transaction Propagation on Permissionless Blockchains: Incentive and Routing Mechanisms
Venue: arXiv cs.CR 2018
Year: 2018

Existing permissionless blockchain solutions rely on peer-to-peer propagation mechanisms, where nodes in a network transfer transaction they received to their neighbors. Unfortunately, there is no explicit incentive for such transaction propagation. Therefore, existing propagation mechanisms will not be sustainable in a fully decentralized blockchain with rational nodes. In this work, we formally define the problem of incentivizing nodes for transaction propagation. We propose an incentive mechanism where each node involved in the propagation of a transaction receives a share of the transaction fee. We also show that our proposal is Sybil-proof. Furthermore, we combine the incentive mechanism with smart routing to reduce the communication and storage costs at the same time. The proposed routing mechanism reduces the redundant transaction propagation from the size of the network to a factor of average shortest path length. The routing mechanism is built upon a specific type of consensus protocol where the round leader who creates the transaction block is known in advance. Note that our routing mechanism is a generic one and can be adopted independently from the incentive mechanism.
Inferring User Interests in Microblogging Social Networks: A Survey
Venue: arXiv cs.IR 2018
Year: 2018

With the growing popularity of microblogging services such as Twitter in recent years, an increasing number of users are using these services in their daily lives. The huge volume of information generated by users raises new opportunities in various applications and areas. Inferring user interests plays a significant role in providing personalized recommendations on microblogging services, and also on third-party applications providing social logins via these services, especially in cold-start situations. In this survey, we review user modeling strategies with respect to inferring user interests from previous studies. To this end, we focus on four dimensions of inferring user interest profiles: (1) data collection, (2) representation of user interest profiles, (3) construction and enhancement of user interest profiles, and (4) the evaluation of the constructed profiles. Through this survey, we aim to provide an overview of state-of-the-art user modeling strategies for inferring user interest profiles on microblogging social networks with respect to the four dimensions. For each dimension, we review and summarize previous studies based on specified criteria. Finally, we discuss some challenges and opportunities for future work in this research domain.
Causal Feature Selection for Individual Characteristics Prediction
Venue: arXiv cs.SI 2018
Year: 2018

People can be characterized by their demographic information and personality traits. Characterizing people accurately can help predict their preferences, and aid recommendations and advertising. A growing number of studies infer people's characteristics from behavioral data. However, context factors make behavioral data noisy, making these data harder to use for predictive analytics. In this paper, we demonstrate how to employ causal identification on feature selection and how to predict individuals' characteristics based on these selected features. We use visitors' choice data from a large theme park, combined with personality measurements, to investigate the causal relationship between visitors' characteristics and their choices in the park. We demonstrate the benefit of feature selection based on causal identification in a supervised prediction task for individual characteristics. Based on our evaluation, our models that trained with features selected based on causal identification outperformed existing methods.
Beyond News Contents: The Role of Social Context for Fake News Detection
Venue: arXiv cs.SI 2018
Year: 2018

Social media is becoming popular for news consumption due to its fast dissemination, easy access, and low cost. However, it also enables the wide propagation of fake news, i.e., news with intentionally false information. Detecting fake news is an important task, which not only ensures users to receive authentic information but also help maintain a trustworthy news ecosystem. The majority of existing detection algorithms focus on finding clues from news contents, which are generally not effective because fake news is often intentionally written to mislead users by mimicking true news. Therefore, we need to explore auxiliary information to improve detection. The social context during news dissemination process on social media forms the inherent tri-relationship, the relationship among publishers, news pieces, and users, which has potential to improve fake news detection. For example, partisan-biased publishers are more likely to publish fake news, and low-credible users are more likely to share fake news. In this paper, we study the novel problem of exploiting social context for fake news detection. We propose a tri-relationship embedding framework TriFN, which models publisher-news relations and user-news interactions simultaneously for fake news classification. We conduct experiments on two real-world datasets, which demonstrate that the proposed approach significantly outperforms other baseline methods for fake news detection.
Smart, Sparse Contours to Represent and Edit Images
Venue: arXiv cs.CV 2018
Year: 2018

We study the problem of reconstructing an image from information stored at contour locations. We show that high-quality reconstructions with high fidelity to the source image can be obtained from sparse input, e.g., comprising less than $6\%$ of image pixels. This is a significant improvement over existing contour-based reconstruction methods that require much denser input to capture subtle texture information and to ensure image quality. Our model, based on generative adversarial networks, synthesizes texture and details in regions where no input information is provided. The semantic knowledge encoded into our model and the sparsity of the input allows to use contours as an intuitive interface for semantically-aware image manipulation: local edits in contour domain translate to long-range and coherent changes in pixel space. We can perform complex structural changes such as changing facial expression by simple edits of contours. Our experiments demonstrate that humans as well as a face recognition system mostly cannot distinguish between our reconstructions and the source images.
Dropout Feature Ranking for Deep Learning Models
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks (DNNs) achieve state-of-the-art results in a variety of domains. Unfortunately, DNNs are notorious for their non-interpretability, and thus limit their applicability in hypothesis-driven domains such as biology and healthcare. Moreover, in the resource-constraint setting, it is critical to design tests relying on fewer more informative features leading to high accuracy performance within reasonable budget. We aim to close this gap by proposing a new general feature ranking method for deep learning. We show that our simple yet effective method performs on par or compares favorably to eight strawman, classical and deep-learning feature ranking methods in two simulations and five very different datasets on tasks ranging from classification to regression, in both static and time series scenarios. We also illustrate the use of our method on a drug response dataset and show that it identifies genes relevant to the drug-response.
Emo, Love, and God: Making Sense of Urban Dictionary, a Crowd-Sourced Online Dictionary
Venue: arXiv cs.CL 2018
Year: 2018

The Internet facilitates large-scale collaborative projects and the emergence of Web 2.0 platforms, where producers and consumers of content unify, has drastically changed the information market. On the one hand, the promise of the "wisdom of the crowd" has inspired successful projects such as Wikipedia, which has become the primary source of crowd-based information in many languages. On the other hand, the decentralized and often un-monitored environment of such projects may make them susceptible to low quality content. In this work, we focus on Urban Dictionary, a crowd-sourced online dictionary. We combine computational methods with qualitative annotation and shed light on the overall features of Urban Dictionary in terms of growth, coverage and types of content. We measure a high presence of opinion-focused entries, as opposed to the meaning-focused entries that we expect from traditional dictionaries. Furthermore, Urban Dictionary covers many informal, unfamiliar words as well as proper nouns. Urban Dictionary also contains offensive content, but highly offensive content tends to receive lower scores through the dictionary's voting system. The low threshold to include new material in Urban Dictionary enables quick recording of new words and new meanings, but the resulting heterogeneous content can pose challenges in using Urban Dictionary as a source to study language innovation.
Denoising of 3D magnetic resonance images with multi-channel residual learning of convolutional neural network
Venue: arXiv cs.CV 2018
Year: 2018

The denoising of magnetic resonance (MR) images is a task of great importance for improving the acquired image quality. Many methods have been proposed in the literature to retrieve noise free images with good performances. Howerever, the state-of-the-art denoising methods, all needs a time-consuming optimization processes and their performance strongly depend on the estimated noise level parameter. Within this manuscript we propose the idea of denoising MRI Rician noise using a convolutional neural network. The advantage of the proposed methodology is that the learning based model can be directly used in the denosing process without optimization and even without the noise level parameter. Specifically, a ten convolutional layers neural network combined with residual learning and multi-channel strategy was proposed. Two training ways: training on a specific noise level and training on a general level were conducted to demonstrate the capability of our methods. Experimental results over synthetic and real 3D MR data demonstrate our proposed network can achieve superior performance compared with other methods in term of both of the peak signal to noise ratio and the global of structure similarity index. Without noise level parameter, our general noise-applicable model is also better than the other compared methods in two datasets. Furthermore, our training model shows good general applicability.
The tractability frontier of well-designed SPARQL queries
Venue: arXiv cs.DB 2018
Year: 2018

We study the complexity of query evaluation of SPARQL queries. We focus on the fundamental fragment of well-designed SPARQL restricted to the AND, OPTIONAL and UNION operators. Our main result is a structural characterisation of the classes of well-designed queries that can be evaluated in polynomial time. In particular, we introduce a new notion of width called domination width, which relies on the well-known notion of treewidth. We show that, under some complexity theoretic assumptions, the classes of well-designed queries that can be evaluated in polynomial time are precisely those of bounded domination width.
A Survey of FPGA-Based Neural Network Accelerator
Venue: arXiv cs.AR 2018
Year: 2018

Recent researches on neural network have shown significant advantage in machine learning over traditional algorithms based on handcrafted features and models. Neural network is now widely adopted in regions like image, speech and video recognition. But the high computation and storage complexity of neural network inference poses great difficulty on its application. CPU platforms are hard to offer enough computation capacity. GPU platforms are the first choice for neural network process because of its high computation capacity and easy to use development frameworks. On the other hand, FPGA-based neural network inference accelerator is becoming a research topic. With specifically designed hardware, FPGA is the next possible solution to surpass GPU in speed and energy efficiency. Various FPGA-based accelerator designs have been proposed with software and hardware optimization techniques to achieve high speed and energy efficiency. In this paper, we give an overview of previous work on neural network inference accelerators based on FPGA and summarize the main techniques used. An investigation from software to hardware, from circuit level to system level is carried out to complete analysis of FPGA-based neural network inference accelerator design and serves as a guide to future work.
Leveraging Native Language Speech for Accent Identification using Deep Siamese Networks
Venue: arXiv cs.CL 2018
Year: 2018

The problem of automatic accent identification is important for several applications like speaker profiling and recognition as well as for improving speech recognition systems. The accented nature of speech can be primarily attributed to the influence of the speaker's native language on the given speech recording. In this paper, we propose a novel accent identification system whose training exploits speech in native languages along with the accented speech. Specifically, we develop a deep Siamese network-based model which learns the association between accented speech recordings and the native language speech recordings. The Siamese networks are trained with i-vector features extracted from the speech recordings using either an unsupervised Gaussian mixture model (GMM) or a supervised deep neural network (DNN) model. We perform several accent identification experiments using the CSLU Foreign Accented English (FAE) corpus. In these experiments, our proposed approach using deep Siamese networks yield significant relative performance improvements of 15.4 percent on a 10-class accent identification task, over a baseline DNN-based classification system that uses GMM i-vectors. Furthermore, we present a detailed error analysis of the proposed accent identification system.
On the Decision Tree Complexity of String Matching
Venue: arXiv cs.CC 2018
Year: 2018

String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision tree complexity) in a string in order to decide whether this string contains a certain pattern. Rivest showed that for every pattern $p$, in the worst case any deterministic algorithm needs to query at least $n-|p|+1$ characters, where $n$ is the length of the string and $|p|$ is the length of the pattern. He further conjectured that this bound is tight. By using the adversary method, Tuza disproved this conjecture and showed that more than one half of binary patterns are {\em evasive}, i.e. any algorithm needs to query all the characters (see Section 1.1 for more details). In this paper, we give a query algorithm which settles the decision tree complexity of string matching except for a negligible fraction of patterns. Our algorithm shows that Tuza's criteria of evasive patterns are almost complete. Using the algebraic approach of Rivest and Vuillemin, we also give a new sufficient condition for the evasiveness of patterns, which is beyond Tuza's criteria. In addition, our result reveals an interesting connection to \emph{Skolem's Problem} in mathematics.