OpenRaiser/Intern-Atlas huggingface dataset:
Relation Classification via Recurrent Neural Network
Venue: arXiv cs.CL 2015
Year: 2015

Deep learning has gained much success in sentence-level relation classification. For example, convolutional neural networks (CNN) have delivered competitive performance without much effort on feature engineering as the conventional pattern-based methods. Thus a lot of works have been produced based on CNN structures. However, a key issue that has not been well addressed by the CNN-based method is the lack of capability to learn temporal features, especially long-distance dependency between nominal pairs. In this paper, we propose a simple framework based on recurrent neural networks (RNN) and compare it with CNN-based model. To show the limitation of popular used SemEval-2010 Task 8 dataset, we introduce another dataset refined from MIMLRE(Angeli et al., 2014). Experiments on two different datasets strongly indicates that the RNN-based model can deliver better performance on relation classification, and it is particularly capable of learning long-distance relation patterns. This makes it suitable for real-world applications where complicated expressions are often involved.
Learning from LDA using Deep Neural Networks
Venue: arXiv cs.LG 2015
Year: 2015

Latent Dirichlet Allocation (LDA) is a three-level hierarchical Bayesian model for topic inference. In spite of its great success, inferring the latent topic distribution with LDA is time-consuming. Motivated by the transfer learning approach proposed by~\newcite{hinton2015distilling}, we present a novel method that uses LDA to supervise the training of a deep neural network (DNN), so that the DNN can approximate the costly LDA inference with less computation. Our experiments on a document classification task show that a simple DNN can learn the LDA behavior pretty well, while the inference is speeded up tens or hundreds of times.
Improved Constructions of Two-Source Extractors
Venue: arXiv cs.CC 2015
Year: 2015

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{Ω(1)}$, while the error remains $n^{-Ω(1)}$. Our improvement is obtained by giving a better extractor for $(q, t, γ)$ non-oblivious bit-fixing sources, which can output $t^{Ω(1)}$ bits instead of one bit as in \cite{CZ15}.
Design Patterns for Self Adaptive Systems Engineering
Venue: arXiv cs.SE 2015
Year: 2015

Self adaptation has been proposed to overcome the complexity of today's software systems which results from the uncertainty issue. Aspects of uncertainty include changing systems goals, changing resource availability and dynamic operating conditions. Feedback control loops have been recognized as vital elements for engineering self-adaptive systems. However, despite their importance, there is still a lack of systematic way of the design of the interactions between the different components comprising one particular feedback control loop as well as the interactions between components from different control loops . Most existing approaches are either domain specific or too abstract to be useful. In addition, the issue of multiple control loops is often neglected and consequently self adaptive systems are often designed around a single loop. In this paper we propose a set of design patterns for modeling and designing self adaptive software systems based on MAPE-K Control loop of IBM architecture blueprint which takes into account the multiple control loops issue. A case study is presented to illustrate the applicability of the proposed design patterns.
Universal Approximation of Edge Density in Large Graphs
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we present a novel way to summarize the structure of large graphs, based on non-parametric estimation of edge density in directed multigraphs. Following coclustering approach, we use a clustering of the vertices, with a piecewise constant estimation of the density of the edges across the clusters, and address the problem of automatically and reliably inferring the number of clusters, which is the granularity of the coclustering. We use a model selection technique with data-dependent prior and obtain an exact evaluation criterion for the posterior probability of edge density estimation models. We demonstrate, both theoretically and empirically, that our data-dependent modeling technique is consistent, resilient to noise, valid non asymptotically and asymptotically behaves as an universal approximator of the true edge density in directed multigraphs. We evaluate our method using artificial graphs and present its practical interest on real world graphs. The method is both robust and scalable. It is able to extract insightful patterns in the unsupervised learning setting and to provide state of the art accuracy when used as a preparation step for supervised learning.
Word sense disambiguation: a survey
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we made a survey on Word Sense Disambiguation (WSD). Near about in all major languages around the world, research in WSD has been conducted upto different extents. In this paper, we have gone through a survey regarding the different approaches adopted in different research works, the State of the Art in the performance in this domain, recent works in different Indian languages and finally a survey in Bengali language. We have made a survey on different competitions in this field and the bench mark results, obtained from those competitions.
An O(1)-Approximation for Minimum Spanning Tree Interdiction
Venue: arXiv cs.DS 2015
Year: 2015

Network interdiction problems are a natural way to study the sensitivity of a network optimization problem with respect to the removal of a limited set of edges or vertices. One of the oldest and best-studied interdiction problems is minimum spanning tree (MST) interdiction. Here, an undirected multigraph with nonnegative edge weights and positive interdiction costs on its edges is given, together with a positive budget B. The goal is to find a subset of edges R, whose total interdiction cost does not exceed B, such that removing R leads to a graph where the weight of an MST is as large as possible. Frederickson and Solis-Oba (SODA 1996) presented an O(log m)-approximation for MST interdiction, where m is the number of edges. Since then, no further progress has been made regarding approximations, and the question whether MST interdiction admits an O(1)-approximation remained open. We answer this question in the affirmative, by presenting a 14-approximation that overcomes two main hurdles that hindered further progress so far. Moreover, based on a well-known 2-approximation for the metric traveling salesman problem (TSP), we show that our O(1)-approximation for MST interdiction implies an O(1)-approximation for a natural interdiction version of metric TSP.
Energy Efficient Medium Access with Interference Mitigation in LTE Femtocell Networks
Venue: arXiv cs.NI 2015
Year: 2015

With the rapidly increasing number of deployed LTE femtocell base stations (FBS), energy consumption of femtocell networks has become a serious environmental issue. Therefore, energy-efficient protocols are needed to balance the trade-off between energy saving and bandwidth utilization. The key component of the desired protocol to prevent both energy and bandwidth waste is interference mitigation, which, nevertheless, most previous work has failed to properly consider. To this end, in this paper, we manipulate user equipment (UE) association and OFDMA scheduling with a combination of interference mitigation. Recognizing the NP-hardness of the problem, we propose two distributed algorithms with guaranteed convergence. Extensive simulations show that our algorithms outperform the alternative algorithms in multiple metrics such as utility, power consumption, and convergence speed.
Distributed Resource Allocation for Relay-Aided Device-to-Device Communication Under Channel Uncertainties: A Stable Matching Approach
Venue: arXiv cs.NI 2015
Year: 2015

Wireless device-to-device (D2D) communication underlaying cellular network is a promising concept to improve user experience and resource utilization. Unlike traditional D2D communication where two mobile devices in the proximity establish a direct local link bypassing the base station, in this work we focus on relay-aided D2D communication. Relay-aided transmission could enhance the performance of D2D communication when D2D user equipments (UEs) are far apart from each other and/or the quality of D2D link is not good enough for direct communication. Considering the uncertainties in wireless links, we model and analyze the performance of a relay-aided D2D communication network, where the relay nodes serve both the cellular and D2D users. In particular, we formulate the radio resource allocation problem in a two-hop network to guarantee the data rate of the UEs while protecting other receiving nodes from interference. Utilizing time sharing strategy, we provide a centralized solution under bounded channel uncertainty. With a view to reducing the computational burden at relay nodes, we propose a distributed solution approach using stable matching to allocate radio resources in an efficient and computationally inexpensive way. Numerical results show that the performance of the proposed method is close to the centralized optimal solution and there is a distance margin beyond which relaying of D2D traffic improves network performance.
Theoretical and Empirical Analysis of a Parallel Boosting Algorithm
Venue: arXiv cs.LG 2015
Year: 2015

Many real-world problems involve massive amounts of data. Under these circumstances learning algorithms often become prohibitively expensive, making scalability a pressing issue to be addressed. A common approach is to perform sampling to reduce the size of the dataset and enable efficient learning. Alternatively, one customizes learning algorithms to achieve scalability. In either case, the key challenge is to obtain algorithmic efficiency without compromising the quality of the results. In this paper we discuss a meta-learning algorithm (PSBML) which combines features of parallel algorithms with concepts from ensemble and boosting methodologies to achieve the desired scalability property. We present both theoretical and empirical analyses which show that PSBML preserves a critical property of boosting, specifically, convergence to a distribution centered around the margin. We then present additional empirical analyses showing that this meta-level algorithm provides a general and effective framework that can be used in combination with a variety of learning classifiers. We perform extensive experiments to investigate the tradeoff achieved between scalability and accuracy, and robustness to noise, on both synthetic and real-world data. These empirical results corroborate our theoretical analysis, and demonstrate the potential of PSBML in achieving scalability without sacrificing accuracy.
On generating the ring of matrix semi-invariants
Venue: arXiv cs.CC 2015
Year: 2015

For a field $\mathbb{F}$, let $R(n, m)$ be the ring of invariant polynomials for the action of $\mathrm{SL}(n, \mathbb{F}) \times \mathrm{SL}(n, \mathbb{F})$ on tuples of matrices -- $(A, C)\in\mathrm{SL}(n, \mathbb{F}) \times \mathrm{SL}(n, \mathbb{F})$ sends $(B_1, \dots, B_m)\in M(n, \mathbb{F})^{\oplus m}$ to $(AB_1C^{-1}, \dots, AB_mC^{-1})$. In this paper we call $R(n, m)$ the \emph{ring of matrix semi-invariants}. Let $β(R(n, m))$ be the smallest $D$ s.t. matrix semi-invariants of degree $\leq D$ generate $R(n, m)$. Guided by the Procesi-Razmyslov-Formanek approach of proving a strong degree bound for generating matrix invariants, we exhibit several interesting structural results for the ring of matrix semi-invariants $R(n, m)$ over fields of characteristic $0$. Using these results, we prove that $β(R(n, m))=Ω(n^{3/2})$, and $β(R(2, m))\leq 4$.
Places205-VGGNet Models for Scene Recognition
Venue: arXiv cs.CV 2015
Year: 2015

VGGNets have turned out to be effective for object recognition in still images. However, it is unable to yield good performance by directly adapting the VGGNet models trained on the ImageNet dataset for scene recognition. This report describes our implementation of training the VGGNets on the large-scale Places205 dataset. Specifically, we train three VGGNet models, namely VGGNet-11, VGGNet-13, and VGGNet-16, by using a Multi-GPU extension of Caffe toolbox with high computational efficiency. We verify the performance of trained Places205-VGGNet models on three datasets: MIT67, SUN397, and Places205. Our trained models achieve the state-of-the-art performance on these datasets and are made public available.
Modeling mutual feedback between users and recommender systems
Venue: arXiv cs.IR 2015
Year: 2015

Recommender systems daily influence our decisions on the Internet. While considerable attention has been given to issues such as recommendation accuracy and user privacy, the long-term mutual feedback between a recommender system and the decisions of its users has been neglected so far. We propose here a model of network evolution which allows us to study the complex dynamics induced by this feedback, including the hysteresis effect which is typical for systems with non-linear dynamics. Despite the popular belief that recommendation helps users to discover new things, we find that the long-term use of recommendation can contribute to the rise of extremely popular items and thus ultimately narrow the user choice. These results are supported by measurements of the time evolution of item popularity inequality in real systems. We show that this adverse effect of recommendation can be tamed by sacrificing part of short-term recommendation accuracy.
Stochastic Language Generation in Dialogue using Recurrent Neural Networks with Convolutional Sentence Reranking
Venue: arXiv cs.CL 2015
Year: 2015

The natural language generation (NLG) component of a spoken dialogue system (SDS) usually needs a substantial amount of handcrafting or a well-labeled dataset to be trained on. These limitations add significantly to development costs and make cross-domain, multi-lingual dialogue systems intractable. Moreover, human languages are context-aware. The most natural response should be directly learned from data rather than depending on predefined syntaxes or rules. This paper presents a statistical language generator based on a joint recurrent and convolutional neural network structure which can be trained on dialogue act-utterance pairs without any semantic alignments or predefined grammar trees. Objective metrics suggest that this new model outperforms previous methods under the same experimental conditions. Results of an evaluation by human judges indicate that it produces not only high quality but linguistically varied utterances which are preferred compared to n-gram and rule-based systems.
Alleviating Merge Conflicts with Fine-grained Visual Awareness
Venue: arXiv cs.SE 2015
Year: 2015

Merge conflicts created by software team members working on the same code can be costly to resolve, and adversely affect productivity. In this work, we suggest the approach of fine-grained merge conflict awareness, where software team members are notified of potential merge conflicts via graphical decoration of the relevant semantic elements, in near real-time. The novelty of this approach is that it allows software developers to pinpoint the element in conflict, such as a method's body, parameter, return value, and so on, promoting communication about conflicting changes soon after they take place and on a semantic level. We have also conducted a preliminary qualitative evaluation of our approach, the results of which we report in this paper.
Incorporating Inductions and Game Semantics into Logic Programming
Venue: arXiv cs.LO 2015
Year: 2015

Inductions and game semantics are two useful extensions to traditional logic programming. To be specific, inductions can capture a wider class of provable formulas in logic programming. Adopting game semantics can make logic programming more interactive. In this paper, we propose an execution model for a logic language with these features. This execution model follows closely the reasoning process in real life.
On cyclic DNA codes over the Ring $\Z_4 + u \Z_4$
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the theory for constructing DNA cyclic codes of odd length over $\Z_4[u]/\langle u^2 \rangle$ which play an important role in DNA computing. Cyclic codes of odd length over $\Z_4 + u \Z_4$ satisfy the reverse constraint and the reverse-complement constraint are studied in this paper. The structure and existence of such codes are also studied. The paper concludes with some DNA example obtained via the family of cyclic codes.
Preprint Virtual Reality Based GIS Analysis Platform
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on ICONIP2015. The proposed platform supports the integrated VRGIS functions including 3D spatial analysis functions, 3D visualization for spatial process and serves for 3D globe and digital city. The 3D analysis and visualization of the concerned city massive information are conducted in the platform. The amount of information that can be visualized with this platform is overwhelming, and the GIS based navigational scheme allows to have great flexibility to access the different available data sources.
What Is Software Engineering?
Venue: arXiv cs.SE 2015
Year: 2015

A later translation (2015) of the article in Russian published in 1990. The article proposes an approach to defining a set of basic notions for subject area of software engineering discipline. The set of notions is intended to serve as a basis for detection and correction of some widespread conceptual mistakes in the efforts aimed at improving the quality and work productivity in creation and operation of software.
Security Games with Ambiguous Beliefs of Agents
Venue: arXiv cs.AI 2015
Year: 2015

Currently the Dempster-Shafer based algorithm and Uniform Random Probability based algorithm are the preferred method of resolving security games, in which defenders are able to identify attackers and only strategy remained ambiguous. However this model is inefficient in situations where resources are limited and both the identity of the attackers and their strategies are ambiguous. The intent of this study is to find a more effective algorithm to guide the defenders in choosing which outside agents with which to cooperate given both ambiguities. We designed an experiment where defenders were compelled to engage with outside agents in order to maximize protection of their targets. We introduced two important notions: the behavior of each agent in target protection and the tolerance threshold in the target protection process. From these, we proposed an algorithm that was applied by each defender to determine the best potential assistant(s) with which to cooperate. Our results showed that our proposed algorithm is safer than the Dempster-Shafer based algorithm.
Facts and Fabrications about Ebola: A Twitter Based Study
Venue: arXiv cs.SI 2015
Year: 2015

Microblogging websites like Twitter have been shown to be immensely useful for spreading information on a global scale within seconds. The detrimental effect, however, of such platforms is that misinformation and rumors are also as likely to spread on the network as credible, verified information. From a public health standpoint, the spread of misinformation creates unnecessary panic for the public. We recently witnessed several such scenarios during the outbreak of Ebola in 2014 [14, 1]. In order to effectively counter the medical misinformation in a timely manner, our goal here is to study the nature of such misinformation and rumors in the United States during fall 2014 when a handful of Ebola cases were confirmed in North America. It is a well known convention on Twitter to use hashtags to give context to a Twitter message (a tweet). In this study, we collected approximately 47M tweets from the Twitter streaming API related to Ebola. Based on hashtags, we propose a method to classify the tweets into two sets: credible and speculative. We analyze these two sets and study how they differ in terms of a number of features extracted from the Twitter API. In conclusion, we infer several interesting differences between the two sets. We outline further potential directions to using this material for monitoring and separating speculative tweets from credible ones, to enable improved public health information.
Kernel Controllers: A Systems-Theoretic Approach for Data-Driven Modeling and Control of Spatiotemporally Evolving Processes
Venue: arXiv cs.SY 2015
Year: 2015

We consider the problem of modeling, estimating, and controlling the latent state of a spatiotemporally evolving continuous function using very few sensor measurements and actuator locations. Our solution to the problem consists of two parts: a predictive model of functional evolution, and feedback based estimator and controllers that can robustly recover the state of the model and drive it to a desired function. We show that layering a dynamical systems prior over temporal evolution of weights of a kernel model is a valid approach to spatiotemporal modeling that leads to systems theoretic, control-usable, predictive models. We provide sufficient conditions on the number of sensors and actuators required to guarantee observability and controllability. The approach is validated on a large real dataset, and in simulation for the control of spatiotemporally evolving function.
Image Representations and New Domains in Neural Image Captioning
Venue: arXiv cs.CL 2015
Year: 2015

We examine the possibility that recent promising results in automatic caption generation are due primarily to language models. By varying image representation quality produced by a convolutional neural network, we find that a state-of-the-art neural captioning algorithm is able to produce quality captions even when provided with surprisingly poor image representations. We replicate this result in a new, fine-grained, transfer learned captioning domain, consisting of 66K recipe image/title pairs. We also provide some experiments regarding the appropriateness of datasets for automatic captioning, and find that having multiple captions per image is beneficial, but not an absolute requirement.
Steady-state Performance of Incremental LMS Strategies For Parameter Estimation Over Fading Wireless Channels
Venue: arXiv cs.SY 2015
Year: 2015

We study the effect of fading in the communication channels between nodes on the performance of the incremental least mean square (ILMS) algorithm. We derive steady-state performance metrics, including the mean-square deviation (MSD), excess mean-square error (EMSE), and mean-square error (MSE). We obtain the sufficient conditions to ensure mean-square convergence, and verify our results through simulations. Simulation results show that our theoretical analysis closely matches the actual steady state performance.
A novel design of hidden web crawler using ontology
Venue: arXiv cs.IR 2015
Year: 2015

Deep Web is content hidden behind HTML forms. Since it represents a large portion of the structured, unstructured and dynamic data on the Web, accessing Deep-Web content has been a long challenge for the database community. This paper describes a crawler for accessing Deep-Web using Ontologies. Performance evaluation of the proposed work showed that this new approach has promising results.