OpenRaiser/Intern-Atlas huggingface dataset:
Extending Weakly-Sticky Datalog+/-: Query-Answering Tractability and Optimizations
Venue: arXiv cs.DB 2016
Year: 2016

Weakly-sticky (WS) Datalog+/- is an expressive member of the family of Datalog+/- programs that is based on the syntactic notions of stickiness and weak-acyclicity. Query answering over the WS programs has been investigated, but there is still much work to do on the design and implementation of practical query answering (QA) algorithms and their optimizations. Here, we study sticky and WS programs from the point of view of the behavior of the chase procedure, extending the stickiness property of the chase to that of generalized stickiness of the chase (gsch-property). With this property we specify the semantic class of GSCh programs, which includes sticky and WS programs, and other syntactic subclasses that we identify. In particular, we introduce joint-weakly-sticky (JWS) programs, that include WS programs. We also propose a bottom-up QA algorithm for a range of subclasses of GSCh. The algorithm runs in polynomial time (in data) for JWS programs. Unlike the WS class, JWS is closed under a general magic-sets rewriting procedure for the optimization of programs with existential rules. We apply the magic-sets rewriting in combination with the proposed QA algorithm for the optimization of QA over JWS programs.
Intra-layer Nonuniform Quantization for Deep Convolutional Neural Network
Venue: arXiv cs.CV 2016
Year: 2016

Deep convolutional neural network (DCNN) has achieved remarkable performance on object detection and speech recognition in recent years. However, the excellent performance of a DCNN incurs high computational complexity and large memory requirement. In this paper, an equal distance nonuniform quantization (ENQ) scheme and a K-means clustering nonuniform quantization (KNQ) scheme are proposed to reduce the required memory storage when low complexity hardware or software implementations are considered. For the VGG-16 and the AlexNet, the proposed nonuniform quantization schemes reduce the number of required memory storage by approximately 50\% while achieving almost the same or even better classification accuracy compared to the state-of-the-art quantization method. Compared to the ENQ scheme, the proposed KNQ scheme provides a better tradeoff when higher accuracy is required.
Applied Lyapunov Stability on Output Tracking Problem for a Class of Discrete-Time Linear Systems
Venue: arXiv cs.SY 2016
Year: 2016

The robust tracking and model following problem of linear discrete-time systems is investigated in this paper. An approach to design robust tracking controllers is proposed. The system is controlled to track dynamic inputs generated from a reference model. By using the solution of the Lyapunov equation, the convergence of the tracking error to the origin, is proved. The proposed approach employs linear controllers rather than nonlinear ones. Therefore, the designing method is simple for use and the resulting controller is easy to implement. An application of the proposed approach for a class of perturbed systems is also considered. Finally, numerical examples are given to demonstrate the validity of the results.
Open Information Extraction
Venue: arXiv cs.CL 2016
Year: 2016

Open Information Extraction (Open IE) systems aim to obtain relation tuples with highly scalable extraction in portable across domain by identifying a variety of relation phrases and their arguments in arbitrary sentences. The first generation of Open IE learns linear chain models based on unlexicalized features such as Part-of-Speech (POS) or shallow tags to label the intermediate words between pair of potential arguments for identifying extractable relations. Open IE currently is developed in the second generation that is able to extract instances of the most frequently observed relation types such as Verb, Noun and Prep, Verb and Prep, and Infinitive with deep linguistic analysis. They expose simple yet principled ways in which verbs express relationships in linguistics such as verb phrase-based extraction or clause-based extraction. They obtain a significantly higher performance over previous systems in the first generation. In this paper, we describe an overview of two Open IE generations including strengths, weaknesses and application areas.
The Benefits of Word Embeddings Features for Active Learning in Clinical Information Extraction
Venue: arXiv cs.CL 2016
Year: 2016

This study investigates the use of unsupervised word embeddings and sequence features for sample representation in an active learning framework built to extract clinical concepts from clinical free text. The objective is to further reduce the manual annotation effort while achieving higher effectiveness compared to a set of baseline features. Unsupervised features are derived from skip-gram word embeddings and a sequence representation approach. The comparative performance of unsupervised features and baseline hand-crafted features in an active learning framework are investigated using a wide range of selection criteria including least confidence, information diversity, information density and diversity, and domain knowledge informativeness. Two clinical datasets are used for evaluation: the i2b2/VA 2010 NLP challenge and the ShARe/CLEF 2013 eHealth Evaluation Lab. Our results demonstrate significant improvements in terms of effectiveness as well as annotation effort savings across both datasets. Using unsupervised features along with baseline features for sample representation lead to further savings of up to 9% and 10% of the token and concept annotation rates, respectively.
Tight Lower Bounds for Multiplicative Weights Algorithmic Families
Venue: arXiv cs.LG 2016
Year: 2016

We study the fundamental problem of prediction with expert advice and develop regret lower bounds for a large family of algorithms for this problem. We develop simple adversarial primitives, that lend themselves to various combinations leading to sharp lower bounds for many algorithmic families. We use these primitives to show that the classic Multiplicative Weights Algorithm (MWA) has a regret of $\sqrt{\frac{T \ln k}{2}}$, there by completely closing the gap between upper and lower bounds. We further show a regret lower bound of $\frac{2}{3}\sqrt{\frac{T\ln k}{2}}$ for a much more general family of algorithms than MWA, where the learning rate can be arbitrarily varied over time, or even picked from arbitrary distributions over time. We also use our primitives to construct adversaries in the geometric horizon setting for MWA to precisely characterize the regret at $\frac{0.391}{\sqrtδ}$ for the case of $2$ experts and a lower bound of $\frac{1}{2}\sqrt{\frac{\ln k}{2δ}}$ for the case of arbitrary number of experts $k$.
sk_p: a neural program corrector for MOOCs
Venue: arXiv cs.PL 2016
Year: 2016

We present a novel technique for automatic program correction in MOOCs, capable of fixing both syntactic and semantic errors without manual, problem specific correction strategies. Given an incorrect student program, it generates candidate programs from a distribution of likely corrections, and checks each candidate for correctness against a test suite. The key observation is that in MOOCs many programs share similar code fragments, and the seq2seq neural network model, used in the natural-language processing task of machine translation, can be modified and trained to recover these fragments. Experiment shows our scheme can correct 29% of all incorrect submissions and out-performs state of the art approach which requires manual, problem specific correction strategies.
Stable Matching with Uncertain Linear Preferences
Venue: arXiv cs.GT 2016
Year: 2016

We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model --- in which for each agent, there is a probability distribution over linear preferences, (2) compact indifference model --- for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model --- there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.
Local feature hierarchy for face recognition across pose and illumination
Venue: arXiv cs.CV 2016
Year: 2016

Even though face recognition in frontal view and normal lighting condition works very well, the performance degenerates sharply in extreme conditions. Recently there are many work dealing with pose and illumination problems, respectively. However both the lighting and pose variation will always be encountered at the same time. Accordingly we propose an end-to-end face recognition method to deal with pose and illumination simultaneously based on convolutional networks where the discriminative nonlinear features that are invariant to pose and illumination are extracted. Normally the global structure for images taken in different views is quite diverse. Therefore we propose to use the 1*1 convolutional kernel to extract the local features. Furthermore the parallel multi-stream multi-layer 1*1 convolution network is developed to extract multi-hierarchy features. In the experiments we obtained the average face recognition rate of 96.9% on multiPIE dataset,which improves the state-of-the-art of face recognition across poses and illumination by 7.5%. Especially for profile-wise positions, the average recognition rate of our proposed network is 97.8%, which increases the state-of-the-art recognition rate by 19%.
A Machine learning approach for Shape From Shading
Venue: arXiv cs.CV 2016
Year: 2016

The aim of Shape From Shading (SFS) problem is to reconstruct the relief of an object from a single gray level image. In this paper we present a new method to solve the problem of SFS using Machine learning method. Our approach belongs to Local resolution category. The orientation of each part of the object is represented by the perpendicular vector to the surface (Normal Vector), this vector is defined by two angles SLANT and TILT, such as the TILT is the angle between the normal vector and Z-axis, and the SLANT is the angle between the the X-axis and the projection of the normal to the plane. The TILT can be determined from the gray level, the unknown is the SLANT. To calculate the normal of each part of the surface (pixel) a supervised Machine learning method has been proposed. This method divided into three steps: the first step is the preparation of the training data from 3D mathematical functions and synthetic objects. The second step is the creation of database of examples from 3D objects (off-line process). The third step is the application of test images (on-line process). The idea is to find for each pixel of the test image the most similar element in the examples database using a similarity value.
Boundary conditions for Shape from Shading
Venue: arXiv cs.CV 2016
Year: 2016

The Shape From Shading is one of a computer vision field. It studies the 3D reconstruction of an object from a single grayscale image. The difficulty of this field can be expressed in the local ambiguity (convex / concave). J.Shi and Q.Zhu have proposed a method (Global View) to solve the local ambiguity. This method based on the graph theory and the relationship between the singular points. In this work we will show that the use of singular points is not sufficient and requires further information on the object to resolve this ambiguity.
Quadboost: A Scalable Concurrent Quadtree
Venue: arXiv cs.DS 2016
Year: 2016

Building concurrent spatial trees is more complicated than binary search trees since a space hierarchy should be preserved during modifications. We present a non-blocking quadtree-quadboost-that supports concurrent insert, remove, move, and contain operations. To increase its concurrency, we propose a decoupling approach that separates physical adjustment from logical removal within the remove operation. In addition, we design a continuous find mechanism to reduce its search cost. The move operation combines the searches for different keys together and modifies different positions with atomicity. The experimental results show that quadboost scales well on a multi-core system with 32 hardware threads. More than that, it outperforms existing concurrent trees in retrieving two-dimensional keys with up to 109% improvement when the number of threads is large. The move operation proved to perform better than the best-known algorithm, with up to 47%.
An Automatic Identification System (AIS) Database for Maritime Trajectory Prediction and Data Mining
Venue: arXiv cs.DB 2016
Year: 2016

In recent years, maritime safety and efficiency become more and more important across the world. Automatic Identification System (AIS) tracks vessel movement by onboard transceiver and terrestrial and/or satellite base station. The data collected by AIS contains broadcast kinematic information and static information. Both of them are useful for anomaly detection and route prediction which are key techniques in intelligent maritime research area. This paper is devoted to construct a standard AIS database for maritime trajectory learning, prediction and data mining. A path prediction algorithm is tested on this AIS database and the testing results show this database can be used as a standardized training resource for different trajectory prediction algorithms and other AIS data mining algorithms.
RGBD Salient Object Detection via Deep Fusion
Venue: arXiv cs.CV 2016
Year: 2016

Numerous efforts have been made to design different low level saliency cues for the RGBD saliency detection, such as color or depth contrast features, background and color compactness priors. However, how these saliency cues interact with each other and how to incorporate these low level saliency cues effectively to generate a master saliency map remain a challenging problem. In this paper, we design a new convolutional neural network (CNN) to fuse different low level saliency cues into hierarchical features for automatically detecting salient objects in RGBD images. In contrast to the existing works that directly feed raw image pixels to the CNN, the proposed method takes advantage of the knowledge in traditional saliency detection by adopting various meaningful and well-designed saliency feature vectors as input. This can guide the training of CNN towards detecting salient object more effectively due to the reduced learning ambiguity. We then integrate a Laplacian propagation framework with the learned CNN to extract a spatially consistent saliency map by exploiting the intrinsic structure of the input image. Extensive quantitative and qualitative experimental evaluations on three datasets demonstrate that the proposed method consistently outperforms state-of-the-art methods.
Secrecy and Energy Efficiency in Massive MIMO Aided Heterogeneous C-RAN: A New Look at Interference
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we investigate the potential benefits of the massive multiple-input multiple-output (MIMO) enabled heterogeneous cloud radio access network (C-RAN) in terms of the secrecy and energy efficiency (EE). In this network, both remote radio heads (RRHs) and massive MIMO macrocell base stations (BSs) are deployed and soft fractional frequency reuse (S-FFR) is adopted to mitigate the inter-tier interference. We first examine the physical layer security by deriving the area ergodic secrecy rate and secrecy outage probability. Our results reveal that the use of massive MIMO and C-RAN can greatly improve the secrecy performance. For C-RAN, a large number of RRHs achieves high area ergodic secrecy rate and low secrecy outage probability, due to its powerful interference management. We find that for massive MIMO aided macrocells, having more antennas and serving more users improves secrecy performance. Then we derive the EE of the heterogeneous C-RAN, illustrating that increasing the number of RRHs significantly enhances the network EE. Furthermore, it is indicated that allocating more radio resources to the RRHs can linearly increase the EE of RRH tier and improve the network EE without affecting the EE of the macrocells.
Location-aware ICI Reduction in MIMO-OFDM Downlinks for High-speed Railway Communication Systems
Venue: arXiv cs.IT 2016
Year: 2016

High mobility may destroy the orthogonality of subcarriers in OFDM systems, resulting in inter- carrier interference (ICI), which may greatly reduce the service quantity of high-speed railway (HSR) wireless communications. This paper focuses on ICI mitigation in the HSR downlinks with distributed transmit antennas.For such a system, its key feature is that the ICIs are caused by multiple carrier frequency offsets corresponding to multiple transmit antennas. Meanwhile, the channel of HSR is fast time varying, which is another big challenge in the system design. In order to get a good performance, low complexity real-time ICI reduction is necessary. To this end, we first analyzed the property of the ICI matrix in AWGN and Rician scenarios, respectively. Then, we propose corresponding low complexity ICI reduction methods based on location information. For evaluating the effectiveness of the proposed method, the expectation and variance of remaining interference after ICI reduction is analyzed with respect to Rician K-factor. In addition, the service quantity and the bandwidth and computation cost are also discussed. Numerical results are presented to verify our theoretical analysis and the effectiveness of proposed ICI reduction methods. One important observation is that our proposed ICI mitigation method can achieve almost the same service quantity with that obtained on the case without ICI at 300km/h,that is, ICI has been completely eliminated. Numerical results also show that the scenarios with Rician K-factors over 30dB can be considered as AWGN scenarios, which may provide valuable insights on future system designs.
Parsimonious Mixed-Effects HodgeRank for Crowdsourced Preference Aggregation
Venue: arXiv cs.HC 2016
Year: 2016

In crowdsourced preference aggregation, it is often assumed that all the annotators are subject to a common preference or utility function which generates their comparison behaviors in experiments. However, in reality annotators are subject to variations due to multi-criteria, abnormal, or a mixture of such behaviors. In this paper, we propose a parsimonious mixed-effects model based on HodgeRank, which takes into account both the fixed effect that the majority of annotators follows a common linear utility model, and the random effect that a small subset of annotators might deviate from the common significantly and exhibits strongly personalized preferences. HodgeRank has been successfully applied to subjective quality evaluation of multimedia and resolves pairwise crowdsourced ranking data into a global consensus ranking and cyclic conflicts of interests. As an extension, our proposed methodology further explores the conflicts of interests through the random effect in annotator specific variations. The key algorithm in this paper establishes a dynamic path from the common utility to individual variations, with different levels of parsimony or sparsity on personalization, based on newly developed Linearized Bregman Algorithms with Inverse Scale Space method. Finally the validity of the methodology are supported by experiments with both simulated examples and three real-world crowdsourcing datasets, which shows that our proposed method exhibits better performance (i.e. smaller test error) compared with HodgeRank due to its parsimonious property.
Bayesian Inference of Bijective Non-Rigid Shape Correspondence
Venue: arXiv cs.CV 2016
Year: 2016

Many algorithms for the computation of correspondences between deformable shapes rely on some variant of nearest neighbor matching in a descriptor space. Such are, for example, various point-wise correspondence recovery algorithms used as a postprocessing stage in the functional correspondence framework. In this paper, we show that such frequently used techniques in practice suffer from lack of accuracy and result in poor surjectivity. We propose an alternative recovery technique guaranteeing a bijective correspondence and producing significantly higher accuracy. We derive the proposed method from a statistical framework of Bayesian inference and demonstrate its performance on several challenging deformable 3D shape matching datasets.
A Survey about Prediction-Based Data Reduction in Wireless Sensor Networks
Venue: arXiv cs.NI 2016
Year: 2016

One of the main characteristics of Wireless Sensor Networks (WSNs) is the constrained energy resources of their wireless sensor nodes. Although this issue has been addressed in several works and got a lot of attention within the years, the most recent advances pointed out that the energy harvesting and wireless charging techniques may offer means to overcome such a limitation. Consequently, an issue that had been put in second place, now emerges: the low availability of spectrum resources. Because of it, the incorporation of the WSNs into the Internet of Things and the exponential growth of the latter may be hindered if no control over the data generation is taken. Alternatively, part of the sensed data can be predicted without triggering transmissions and congesting the wireless medium. In this work, we analyze and categorize existing prediction-based data reduction mechanisms that have been designed for WSNs. Our main contribution is a systematic procedure for selecting a scheme to make predictions in WSNs, based on WSNs' constraints, characteristics of prediction methods and monitored data. Finally, we conclude the paper with a discussion about future challenges and open research directions in the use of prediction methods to support the WSNs' growth.
Coupling proofs are probabilistic product programs
Venue: arXiv cs.PL 2016
Year: 2016

Couplings are a powerful mathematical tool for reasoning about pairs of probabilistic processes. Recent developments in formal verification identify a close connection between couplings and pRHL, a relational program logic motivated by applications to provable security, enabling formal construction of couplings from the probability theory literature. However, existing work using pRHL merely shows existence of a coupling and does not give a way to prove quantitative properties about the coupling, which are need to reason about mixing and convergence of probabilistic processes. Furthermore, pRHL is inherently incomplete, and is not able to capture some advanced forms of couplings such as shift couplings. We address both problems as follows. First, we define an extension of pRHL, called xpRHL, which explicitly constructs the coupling in a pRHL derivation in the form of a probabilistic product program that simulates two correlated runs of the original program. Existing verification tools for probabilistic programs can then be directly applied to the probabilistic product to prove quantitative properties of the coupling. Second, we equip pRHL with a new rule for while loops, where reasoning can freely mix synchronized and unsynchronized loop iterations. Our proof rule can capture examples of shift couplings, and the logic is relatively complete for deterministic programs. We show soundness of xpRHL and use it to analyze two classes of examples. First, we verify rapid mixing using different tools from coupling: standard coupling, shift coupling, and path coupling, a compositional principle for combining local couplings into a global coupling. Second, we verify (approximate) equivalence between a source and an optimized program for several instances of loop optimizations from the literature.