OpenRaiser/Intern-Atlas huggingface dataset:
Detection is the central problem in real-word spelling correction
Venue: arXiv cs.CL 2014
Year: 2014

Real-word spelling correction differs from non-word spelling correction in its aims and its challenges. Here we show that the central problem in real-word spelling correction is detection. Methods from non-word spelling correction, which focus instead on selection among candidate corrections, do not address detection adequately, because detection is either assumed in advance or heavily constrained. As we demonstrate in this paper, merely discriminating between the intended word and a random close variation of it within the context of a sentence is a task that can be performed with high accuracy using straightforward models. Trigram models are sufficient in almost all cases. The difficulty comes when every word in the sentence is a potential error, with a large set of possible candidate corrections. Despite their strengths, trigram models cannot reliably find true errors without introducing many more, at least not when used in the obvious sequential way without added structure. The detection task exposes weakness not visible in the selection task.
User Profile Relationships using String Similarity Metrics in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

This article reviews the problem of degree of closeness and interaction level in a social network by ranking users based on similarity score. This similarity is measured on the basis of social, geographic, educational, professional, shared interests, pages liked, mutual interested groups or communities and mutual friends. The technique addresses the problem of matching user profiles in its globality by providing a suitable matching framework able to consider all profiles' attributes and finding the similarity by new ways of string metrics. It is able to discover the biggest possible number of profiles that are similar to the target user profile, which the existing techniques are unable to detect. Attributes were assigned weights manually; string and semantic similarity metrics were used to compare attributes values thus predicting the most similar profiles. Profile based similarity show the exact relationship between users and this similarity between user profiles reflects closeness and interaction between users.
Detection and Isolation of Failures in Directed Networks of LTI Systems
Venue: arXiv cs.SY 2014
Year: 2014

We propose a methodology to detect and isolate link failures in a weighted and directed network of identical multi-input multi-output LTI systems when only the output responses of a subset of nodes are available. Our method is based on the observation of jump discontinuities in the output derivatives, which can be explicitly related to the occurrence of link failures. The order of the derivative at which the jump is observed is given by $r(d+1)$, where $r$ is the relative degree of each system's transfer matrix, and $d$ denotes the distance from the location of the failure to the observation point. We then propose detection and isolation strategies based on this relation. Furthermore, we propose an efficient algorithm for sensor placement to detect and isolate any possible link failure using a small number of sensors. Available results from the theory of sub-modular set functions provide us with performance guarantees that bound the size of the chosen sensor set within a logarithmic factor of the smallest feasible set of sensors. These results are illustrated through elaborative examples and supplemented by computer experiments.
The Value of Using Big Data Technologies in Computational Social Science
Venue: arXiv cs.SI 2014
Year: 2014

The discovery of phenomena in social networks has prompted renewed interests in the field. Data in social networks however can be massive, requiring scalable Big Data architecture. Conversely, research in Big Data needs the volume and velocity of social media data for testing its scalability. Not only so, appropriate data processing and mining of acquired datasets involve complex issues in the variety, veracity, and variability of the data, after which visualisation must occur before we can see fruition in our efforts. This article presents topical, multimodal, and longitudinal social media datasets from the integration of various scalable open source technologies. The article details the process that led to the discovery of social information landscapes within the Twitter social network, highlighting the experience of dealing with social media datasets, using a funneling approach so that data becomes manageable. The article demonstrated the feasibility and value of using scalable open source technologies for acquiring massive, connected datasets for research in the social sciences.
Distributed localization of a RF target in NLOS environments
Venue: arXiv cs.IT 2014
Year: 2014

We propose a novel distributed expectation maximization (EM) method for non-cooperative RF device localization using a wireless sensor network. We consider the scenario where few or no sensors receive line-of-sight signals from the target. In the case of non-line-of-sight signals, the signal path consists of a single reflection between the transmitter and receiver. Each sensor is able to measure the time difference of arrival of the target's signal with respect to a reference sensor, as well as the angle of arrival of the target's signal. We derive a distributed EM algorithm where each node makes use of its local information to compute summary statistics, and then shares these statistics with its neighbors to improve its estimate of the target localization. Since all the measurements need not be centralized at a single location, the spectrum usage can be significantly reduced. The distributed algorithm also allows for increased robustness of the sensor network in the case of node failures. We show that our distributed algorithm converges, and simulation results suggest that our method achieves an accuracy close to the centralized EM algorithm. We apply the distributed EM algorithm to a set of experimental measurements with a network of four nodes, which confirm that the algorithm is able to localize a RF target in a realistic non-line-of-sight scenario.
SimLex-999: Evaluating Semantic Models with (Genuine) Similarity Estimation
Venue: arXiv cs.CL 2014
Year: 2014

We present SimLex-999, a gold standard resource for evaluating distributional semantic models that improves on existing resources in several important ways. First, in contrast to gold standards such as WordSim-353 and MEN, it explicitly quantifies similarity rather than association or relatedness, so that pairs of entities that are associated but not actually similar [Freud, psychology] have a low rating. We show that, via this focus on similarity, SimLex-999 incentivizes the development of models with a different, and arguably wider range of applications than those which reflect conceptual association. Second, SimLex-999 contains a range of concrete and abstract adjective, noun and verb pairs, together with an independent rating of concreteness and (free) association strength for each pair. This diversity enables fine-grained analyses of the performance of models on concepts of different types, and consequently greater insight into how architectures can be improved. Further, unlike existing gold standard evaluations, for which automatic approaches have reached or surpassed the inter-annotator agreement ceiling, state-of-the-art models perform well below this ceiling on SimLex-999. There is therefore plenty of scope for SimLex-999 to quantify future improvements to distributional semantic models, guiding the development of the next generation of representation-learning architectures.
Solving Polynomial Equations with Equation Constraints: the Zero-dimensional Case
Venue: arXiv cs.SC 2014
Year: 2014

A zero-dimensional polynomial ideal may have a lot of complex zeros. But sometimes, only some of them are needed. In this paper, for a zero-dimensional ideal $I$, we study its complex zeros that locate in another variety $\textbf{V}(J)$ where $J$ is an arbitrary ideal. The main problem is that for a point in $\textbf{V}(I) \cap \textbf{V}(J)=\textbf{V}(I+J)$, its multiplicities w.r.t. $I$ and $I+J$ may be different. Therefore, we cannot get the multiplicity of this point w.r.t. $I$ by studying $I + J$. A straightforward way is that first compute the points of $\textbf{V}(I + J)$, then study their multiplicities w.r.t. $I$. But the former step is difficult to realize exactly. In this paper, we propose a natural geometric explanation of the localization of a polynomial ring corresponding to a semigroup order. Then, based on this view, using the standard basis method and the border basis method, we introduce a way to compute the complex zeros of $I$ in $\textbf{V}(J)$ with their multiplicities w.r.t. $I$. As an application, we compute the sum of Milnor numbers of the singular points on a polynomial hypersurface and work out all the singular points on the hypersurface with their Milnor numbers.
Partially-Distributed Resource Allocation in Small-Cell Networks
Venue: arXiv cs.NI 2014
Year: 2014

We propose a four-stage hierarchical resource allocation scheme for the downlink of a large-scale small-cell network in the context of orthogonal frequency-division multiple access (OFDMA). Since interference limits the capabilities of such networks, resource allocation and interference management are crucial. However, obtaining the globally optimum resource allocation is exponentially complex and mathematically intractable. Here, we develop a partially decentralized algorithm to obtain an effective solution. The three major advantages of our work are: 1) as opposed to a fixed resource allocation, we consider load demand at each access point (AP) when allocating spectrum; 2) to prevent overloaded APs, our scheme is dynamic in the sense that as the users move from one AP to the other, so do the allocated resources, if necessary, and such considerations generally result in huge computational complexity, which brings us to the third advantage: 3) we tackle complexity by introducing a hierarchical scheme comprising four phases: user association, load estimation, interference management via graph coloring, and scheduling. We provide mathematical analysis for the first three steps modeling the user and AP locations as Poisson point processes. Finally, we provide results of numerical simulations to illustrate the efficacy of our scheme.
Long-term causal effects of economic mechanisms on agent incentives
Venue: arXiv cs.GT 2014
Year: 2014

Economic mechanisms administer the allocation of resources to interested agents based on their self-reported types. One objective in mechanism design is to design a strategyproof process so that no agent will have an incentive to misreport its type. However, typical analyses of the incentives properties of mechanisms operate under strong, usually untestable assumptions. Empirical, data-oriented approaches are, at best, under-developed. Furthermore, mechanism/policy evaluation methods usually ignore the dynamic nature of a multi-agent system and are thus inappropriate for estimating long-term effects. We introduce the problem of estimating the causal effects of mechanisms on incentives and frame it under the Rubin causal framework \citep{rubin74, rubin78}. This raises unique technical challenges since the outcome of interest (agent truthfulness) is confounded with strategic interactions and, interestingly, is typically never observed under any mechanism. We develop a methodology to estimate such causal effects that using a prior that is based on a strategic equilibrium model. Working on the domain of kidney exchanges, we show how to apply our methodology to estimate causal effects of kidney allocation mechanisms on hospitals' incentives. Our results demonstrate that the use of game-theoretic prior captures the dynamic nature of the kidney exchange multiagent system and shrinks the estimates towards long-term effects, thus improving upon typical methods that completely ignore agents' strategic behavior.
Opinion mining of movie reviews at document level
Venue: arXiv cs.IR 2014
Year: 2014

The whole world is changed rapidly and using the current technologies Internet becomes an essential need for everyone. Web is used in every field. Most of the people use web for a common purpose like online shopping, chatting etc. During an online shopping large number of reviews/opinions are given by the users that reflect whether the product is good or bad. These reviews need to be explored, analyse and organized for better decision making. Opinion Mining is a natural language processing task that deals with finding orientation of opinion in a piece of text with respect to a topic. In this paper a document based opinion mining system is proposed that classify the documents as positive, negative and neutral. Negation is also handled in the proposed system. Experimental results using reviews of movies show the effectiveness of the system.
Cone Crusher Model Identification Using Block-Oriented Systems with Orthonormal Basis Functions
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, block-oriented systems with linear parts based on Laguerre functions is used to approximation of a cone crusher dynamics. Adaptive recursive least squares algorithm is used to identification of Laguerre model. Various structures of Hammerstein, Wiener, Hammerstein-Wiener models are tested and the MATLAB simulation results are compared. The mean square error is used for models validation. It has been found that Hammerstein-Wiener with orthonormal basis functions improves the quality of approximation plant dynamics. The mean square error for this model is 11% on average throughout the considered range of the external disturbances amplitude. The analysis also showed that Wiener model cannot provide sufficient approximation accuracy of the cone crusher dynamics. During the process it is unstable due to the high sensitivity to disturbances on the output. The Hammerstein-Wiener model will be used to the design nonlinear model predictive control application.
Facts, myths and fights about the KLJN classical physical key exchanger
Venue: arXiv cs.ET 2014
Year: 2014

This paper deals with the Kirchhoff-law-Johnson-noise (KLJN) classical statistical physical key exchange method and surveys criticism - often stemming from a lack of understanding of its underlying premises or from other errors - and our related responses against these, often unphysical, claims. Some of the attacks are valid, however, an extended KLJN system remains protected against all of them, implying that its unconditional security is not impacted.
Searching with Measurement Dependent Noise
Venue: arXiv cs.IT 2014
Year: 2014

Consider a target moving with a constant velocity on a unit-circumference circle, starting from an arbitrary location. To acquire the target, any region of the circle can be probed for its presence, but the associated measurement noise increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity, we characterize the optimal tradeoff between time and resolution (i.e., maximal rate), and show that in contrast to the case of constant measurement noise, measurement dependent noise incurs a multiplicative gap between adaptive search and non-adaptive search. Moreover, our adaptive scheme attains the optimal rate-reliability tradeoff. We further show that for optimal non-adaptive search, accounting for an unknown velocity incurs a factor of two in rate.
Efficient Online Strategies for Renting Servers in the Cloud
Venue: arXiv cs.DS 2014
Year: 2014

In Cloud systems, we often deal with jobs that arrive and depart in an online manner. Upon its arrival, a job should be assigned to a server. Each job has a size which defines the amount of resources that it needs. Servers have uniform capacity and, at all times, the total size of jobs assigned to a server should not exceed the capacity. This setting is closely related to the classic bin packing problem. The difference is that, in bin packing, the objective is to minimize the total number of used servers. In the Cloud, however, the charge for each server is proportional to the length of the time interval it is rented for, and the goal is to minimize the cost involved in renting all used servers. Recently, certain bin packing strategies were considered for renting servers in the Cloud [Li et al. SPAA'14]. There, it is proved that all Any-Fit bin packing strategy has a competitive ratio of at least $μ$, where $μ$ is the max/min interval length ratio of jobs. It is also shown that First Fit has a competitive ratio of $2μ+ 13$ while Best Fit is not competitive at all. We observe that the lower bound of $μ$ extends to all online algorithms. We also prove that, surprisingly, Next Fit algorithm has competitive ratio of at most $2 μ+1$. We also show that a variant of Next Fit achieves a competitive ratio of $K \times max\{1,μ/(K-1)\}+1$, where $K$ is a parameter of the algorithm. In particular, if the value of $μ$ is known, the algorithm has a competitive ratio of $μ+2$; this improves upon the existing upper bound of $μ+8$. Finally, we introduce a simple algorithm called Move To Front (MTF) which has a competitive ratio of at most $6μ+ 7$ and also promising average-case performance. We experimentally study the average-case performance of different algorithms and observe that the typical behaviour of MTF is distinctively better than other algorithms.
Unsupervised Parallel Extraction based Texture for Efficient Image Representation
Venue: arXiv cs.CV 2014
Year: 2014

SOM is a type of unsupervised learning where the goal is to discover some underlying structure of the data. In this paper, a new extraction method based on the main idea of Concurrent Self-Organizing Maps (CSOM), representing a winner-takes-all collection of small SOM networks is proposed. Each SOM of the system is trained individually to provide best results for one class only. The experiments confirm that the proposed features based CSOM is capable to represent image content better than extracted features based on a single big SOM and these proposed features improve the final decision of the CAD. Experiments held on Mammographic Image Analysis Society (MIAS) dataset.
Searchers Seeking: What Happens When you Frustrate Searchers?
Venue: arXiv cs.IR 2014
Year: 2014

People searching for information occasionally experience difficulties finding what they want on the Web. This might happen if they cannot quite come up with the right search terms. What do searchers do when this happens? Intuitively one imagines that they will try a number of associated search terms to zero in on their intended search target. Certainly the provision of spelling suggestions and related search terms assume that frustrated searchers will use these to implement this strategy. Is this assumption correct? What do people really do? We ran an experiment where we asked people to find some relevant links, but we prevented them from using the most obvious search terms, which we termed taboo words. To make the experiment more interesting we also provided the traditional forms of assistance: spelling suggestions and related search suggestions. We assigned participants using a magic square to get no assistance, one kind of assistance, or both. Forty eight people participated in the experiment. What emerged from the analysis was that when people are frustrated in their searching attempts, a minority soldier on, attempting to find other terms, but the majority will stick with their original query term and simply progress from page to page in a vain attempt to find something relevant. This confirms findings by other researchers about the difficulties of query re-formulation. Our finding will serve to inform the developers of user interfaces to search engines, since it would be helpful if we could find a better way of supporting frustrated searchers.
A NLLS Based Sub-Nyquist Rate Spectrum Sensing for Wideband Cognitive Radio
Venue: arXiv cs.IT 2014
Year: 2014

For systems and devices, such as cognitive radio and networks, that need to be aware of available frequency bands, spectrum sensing has an important role. A major challenge in this area is the requirement of a high sampling rate in the sensing of a wideband signal. In this paper a wideband spectrum sensing method is presented that utilizes a sub-Nyquist sampling scheme to bring substantial savings in terms of the sampling rate. The correlation matrix of a finite number of noisy samples is computed and used by a non-linear least square (NLLS) estimator to detect the occupied and vacant channels of the spectrum. We provide an expression for the detection threshold as a function of sampling parameters and noise power. Also, a sequential forward selection algorithm is presented to find the occupied channels with low complexity. The method can be applied to both correlated and uncorrelated wideband multichannel signals. A comparison with conventional energy detection using Nyquist-rate sampling shows that the proposed scheme can yield similar performance for SNR above 4 dB with a factor of 3 smaller sampling rate.
Developer Belief vs. Reality: The Case of the Commit Size Distribution
Venue: arXiv cs.SE 2014
Year: 2014

The design of software development tools follows from what the developers of such tools believe is true about software development. A key aspect of such beliefs is the size of code contributions (commits) to a software project. In this paper, we show that what tool developers think is true about the size of code contributions is different by more than an order of magnitude from reality. We present this reality, called the commit size distribution, for a large sample of open source and selected closed source projects. We suggest that these new empirical insights will help improve software development tools by aligning underlying design assumptions closer with reality.
Conic Multi-Task Classification
Venue: arXiv cs.LG 2014
Year: 2014

Traditionally, Multi-task Learning (MTL) models optimize the average of task-related objective functions, which is an intuitive approach and which we will be referring to as Average MTL. However, a more general framework, referred to as Conic MTL, can be formulated by considering conic combinations of the objective functions instead; in this framework, Average MTL arises as a special case, when all combination coefficients equal 1. Although the advantage of Conic MTL over Average MTL has been shown experimentally in previous works, no theoretical justification has been provided to date. In this paper, we derive a generalization bound for the Conic MTL method, and demonstrate that the tightest bound is not necessarily achieved, when all combination coefficients equal 1; hence, Average MTL may not always be the optimal choice, and it is important to consider Conic MTL. As a byproduct of the generalization bound, it also theoretically explains the good experimental results of previous relevant works. Finally, we propose a new Conic MTL model, whose conic combination coefficients minimize the generalization bound, instead of choosing them heuristically as has been done in previous methods. The rationale and advantage of our model is demonstrated and verified via a series of experiments by comparing with several other methods.