OpenRaiser/Intern-Atlas huggingface dataset:
Semantic Composition and Decomposition: From Recognition to Generation
Venue: arXiv cs.CL 2014
Year: 2014

Semantic composition is the task of understanding the meaning of text by composing the meanings of the individual words in the text. Semantic decomposition is the task of understanding the meaning of an individual word by decomposing it into various aspects (factors, constituents, components) that are latent in the meaning of the word. We take a distributional approach to semantics, in which a word is represented by a context vector. Much recent work has considered the problem of recognizing compositions and decompositions, but we tackle the more difficult generation problem. For simplicity, we focus on noun-modifier bigrams and noun unigrams. A test for semantic composition is, given context vectors for the noun and modifier in a noun-modifier bigram ("red salmon"), generate a noun unigram that is synonymous with the given bigram ("sockeye"). A test for semantic decomposition is, given a context vector for a noun unigram ("snifter"), generate a noun-modifier bigram that is synonymous with the given unigram ("brandy glass"). With a vocabulary of about 73,000 unigrams from WordNet, there are 73,000 candidate unigram compositions for a bigram and 5,300,000,000 (73,000 squared) candidate bigram decompositions for a unigram. We generate ranked lists of potential solutions in two passes. A fast unsupervised learning algorithm generates an initial list of candidates and then a slower supervised learning algorithm refines the list. We evaluate the candidate solutions by comparing them to WordNet synonym sets. For decomposition (unigram to bigram), the top 100 most highly ranked bigrams include a WordNet synonym of the given unigram 50.7% of the time. For composition (bigram to unigram), the top 100 most highly ranked unigrams include a WordNet synonym of the given bigram 77.8% of the time.
Optimal CUR Matrix Decompositions
Venue: arXiv cs.DS 2014
Year: 2014

The CUR decomposition of an $m \times n$ matrix $A$ finds an $m \times c$ matrix $C$ with a subset of $c < n$ columns of $A,$ together with an $r \times n$ matrix $R$ with a subset of $r < m$ rows of $A,$ as well as a $c \times r$ low-rank matrix $U$ such that the matrix $C U R$ approximates the matrix $A,$ that is, $ || A - CUR ||_F^2 \le (1+ε) || A - A_k||_F^2$, where $||.||_F$ denotes the Frobenius norm and $A_k$ is the best $m \times n$ matrix of rank $k$ constructed via the SVD. We present input-sparsity-time and deterministic algorithms for constructing such a CUR decomposition where $c=O(k/ε)$ and $r=O(k/ε)$ and rank$(U) = k$. Up to constant factors, our algorithms are simultaneously optimal in $c, r,$ and rank$(U)$.
How to Compute Worst-Case Execution Time by Optimization Modulo Theory and a Clever Encoding of Program Semantics
Venue: arXiv cs.PL 2014
Year: 2014

In systems with hard real-time constraints, it is necessary to compute upper bounds on the worst-case execution time (WCET) of programs; the closer the bound to the real WCET, the better. This is especially the case of synchronous reactive control loops with a fixed clock; the WCET of the loop body must not exceed the clock period. We compute the WCET (or at least a close upper bound thereof) as the solution of an optimization modulo theory problem that takes into account the semantics of the program, in contrast to other methods that compute the longest path whether or not it is feasible according to these semantics. Optimization modulo theory extends satisfiability modulo theory (SMT) to maximization problems. Immediate encodings of WCET problems into SMT yield formulas intractable for all current production-grade solvers; this is inherent to the DPLL(T) approach to SMT implemented in these solvers. By conjoining some appropriate "cuts" to these formulas, we considerably reduce the computation time of the SMT-solver. We experimented our approach on a variety of control programs, using the OTAWA analyzer both as baseline and as underlying microarchitectural analysis for our analysis, and show notable improvement on the WCET bound on a variety of benchmarks and control programs.
Comparing and Combining Sentiment Analysis Methods
Venue: arXiv cs.CL 2014
Year: 2014

Several messages express opinions about events, products, and services, political views or even their author's emotional state and mood. Sentiment analysis has been used in several applications including analysis of the repercussions of events in social networks, analysis of opinions about products and services, and simply to better understand aspects of social communication in Online Social Networks (OSNs). There are multiple methods for measuring sentiments, including lexical-based approaches and supervised machine learning methods. Despite the wide use and popularity of some methods, it is unclear which method is better for identifying the polarity (i.e., positive or negative) of a message as the current literature does not provide a method of comparison among existing methods. Such a comparison is crucial for understanding the potential limitations, advantages, and disadvantages of popular methods in analyzing the content of OSNs messages. Our study aims at filling this gap by presenting comparisons of eight popular sentiment analysis methods in terms of coverage (i.e., the fraction of messages whose sentiment is identified) and agreement (i.e., the fraction of identified sentiments that are in tune with ground truth). We develop a new method that combines existing approaches, providing the best coverage results and competitive agreement. We also present a free Web service called iFeel, which provides an open API for accessing and comparing results across different sentiment methods for a given text.
A belief-based evolutionarily stable strategy
Venue: arXiv cs.GT 2014
Year: 2014

As an equilibrium refinement of the Nash equilibrium, evolutionarily stable strategy (ESS) is a key concept in evolutionary game theory and has attracted growing interest. An ESS can be either a pure strategy or a mixed strategy. Even though the randomness is allowed in mixed strategy, the selection probability of pure strategy in a mixed strategy may fluctuate due to the impact of many factors. The fluctuation can lead to more uncertainty. In this paper, such uncertainty involved in mixed strategy has been further taken into consideration: a belief strategy is proposed in terms of Dempster-Shafer evidence theory. Furthermore, based on the proposed belief strategy, a belief-based ESS has been developed. The belief strategy and belief-based ESS can reduce to the mixed strategy and mixed ESS, which provide more realistic and powerful tools to describe interactions among agents.
Fast Kötter-Nielsen-Høholdt Interpolation in the Guruswami-Sudan Algorithm
Venue: arXiv cs.IT 2014
Year: 2014

The Kötter-Nielsen-Høholdt algorithm is a popular way to construct the bivariate interpolation polynomial in the Guruswami-Sudan decoding algorithm for Reed-Solomon codes. In this paper, we show how one can use Divide & Conquer techniques to provide an asymptotic speed-up of the algorithm, rendering its complexity quasi-linear in n. Several of our observations can also provide a practical speed-up to the classical version of the algorithm.
On the Galois Lattice of Bipartite Distance Hereditary Graphs
Venue: arXiv cs.DM 2014
Year: 2014

We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois lattice of a bipartite graph is tree-like if and only if the graph is a Bipartite Distance Hereditary graph. By relying on the interplay between bipartite distance hereditary graphs and series-parallel graphs, we show that the lattice can be realized as the containment relation among directed paths in an arborescence. Moreover, a compact encoding of Bipartite Distance Hereditary graphs is proposed, that allows optimal time computation of neighborhood intersections and maximal bicliques.
On the ISAR Image Analysis and Recovery with Unavailable or Heavily Corrupted Data
Venue: arXiv cs.IT 2014
Year: 2014

Common ISAR radar images and signals can be reconstructed from much fewer samples than the sampling theorem requires since they are usually sparse. Unavailable randomly positioned samples can result from heavily corrupted parts of the signal. Since these samples can be omitted and declared as unavailable, the application of the compressive sensing methods in the recovery of heavily corrupted signal and radar images is possible. A\ simple direct method for the recovery of unavailable signal samples and the calculation of the restored ISAR image is reviewed. An analysis of the noise influence is performed. For fast maneuvering ISAR targets the sparsity property is lost since the ISAR image is blurred. A nonparametric quadratic time-frequency representations based method is used to restore the ISAR image sparsity. However, the linear relation between the signal and the sparsity domain transformation is lost. A recently proposed gradient recovery algorithm is adapted for this kind of analysis. It does not require the linear relation of the signal and its sparsity domain transformation in the process of unavailable data recovery. The presented methods and results are tested on several numerical examples proving the expected accuracy and improvements.
Holistic Measures for Evaluating Prediction Models in Smart Grids
Venue: arXiv cs.LG 2014
Year: 2014

The performance of prediction models is often based on "abstract metrics" that estimate the model's ability to limit residual errors between the observed and predicted values. However, meaningful evaluation and selection of prediction models for end-user domains requires holistic and application-sensitive performance measures. Inspired by energy consumption prediction models used in the emerging "big data" domain of Smart Power Grids, we propose a suite of performance measures to rationally compare models along the dimensions of scale independence, reliability, volatility and cost. We include both application independent and dependent measures, the latter parameterized to allow customization by domain experts to fit their scenario. While our measures are generalizable to other domains, we offer an empirical analysis using real energy use data for three Smart Grid applications: planning, customer education and demand response, which are relevant for energy sustainability. Our results underscore the value of the proposed measures to offer a deeper insight into models' behavior and their impact on real applications, which benefit both data mining researchers and practitioners.
Joint PIC and relay selection based on greedy techniques for cooperative DS-CDMA systems
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we propose a cross-layer design strategy based on the parallel interference cancellation (PIC) detection technique and a multi-relay selection algorithm for the uplink of cooperative direct-sequence code-division multiple access (DS-CDMA) systems. We devise a low-cost greedy list-based PIC (GL-PIC) strategy with RAKE receivers as the front-end that can approach the maximum likelihood detector performance. We also present a low-complexity multi-relay selection algorithm based on greedy techniques that can approach the performance of an exhaustive search. Simulations show an excellent bit error rate performance of the proposed detection and relay selection algorithms as compared to existing techniques.
Extended Generalized DoF Optimality Regime of Treating Interference as Noise in the X Channel
Venue: arXiv cs.IT 2014
Year: 2014

The simple scheme of treating interference as noise (TIN) is studied in this paper for the 3 x 2 X channel. A new sum-capacity upper bound is derived. This upper bound is transformed into a generalized degrees-of-freedom (GDoF) upper bound, and is shown to coincide with the achievable GDoF of scheme that combines TDMA and TIN for some conditions on the channel parameters. These conditions specify a noisy interference regime which extends noisy interference regimes available in literature. As a by-product, the sum-capacity of the 3 x 2 X channel is characterized within a constant gap in the given noisy interference regime.
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
Venue: arXiv cs.CR 2014
Year: 2014

Goldreich suggested candidates of one-way functions and pseudorandom generators included in $\mathsf{NC}^0$. It is known that randomly generated Goldreich's generator using $(r-1)$-wise independent predicates with $n$ input variables and $m=C n^{r/2}$ output variables is not pseudorandom generator with high probability for sufficiently large constant $C$. Most of the previous works assume that the alphabet is binary and use techniques available only for the binary alphabet. In this paper, we deal with non-binary generalization of Goldreich's generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreich's generators. We assume that $u(n)\in ω(1)\cap o(n)$ input variables are known. In that case, we show that when $r\ge 3$, there is an exact threshold $μ_\mathrm{c}(k,r):=\binom{k}{r}^{-1}\frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=μ\frac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreich's generator if $μ>μ_\mathrm{c}(k,r)$, and that the LP relaxation cannot determine $\frac1{r-2} u(n)$ input variables of Goldreich's generator if $μ<μ_\mathrm{c}(k,r)$. This paper uses characterization of LP solutions by combinatorial structures called stopping sets on a bipartite graph, which is related to a simple algorithm called peeling algorithm.
Optimizing the flash-RAM energy trade-off in deeply embedded systems
Venue: arXiv cs.OH 2014
Year: 2014

Deeply embedded systems often have the tightest constraints on energy consumption, requiring that they consume tiny amounts of current and run on batteries for years. However, they typically execute code directly from flash, instead of the more energy efficient RAM. We implement a novel compiler optimization that exploits the relative efficiency of RAM by statically moving carefully selected basic blocks from flash to RAM. Our technique uses integer linear programming, with an energy cost model to select a good set of basic blocks to place into RAM, without impacting stack or data storage. We evaluate our optimization on a common ARM microcontroller and succeed in reducing the average power consumption by up to 41% and reducing energy consumption by up to 22%, while increasing execution time. A case study is presented, where an application executes code then sleeps for a period of time. For this example we show that our optimization could allow the application to run on battery for up to 32% longer. We also show that for this scenario the total application energy can be reduced, even if the optimization increases the execution time of the code.
Software-Defined Networking: A Comprehensive Survey
Venue: arXiv cs.NI 2014
Year: 2014

Software-Defined Networking (SDN) is an emerging paradigm that promises to change this state of affairs, by breaking vertical integration, separating the network's control logic from the underlying routers and switches, promoting (logical) centralization of network control, and introducing the ability to program the network. The separation of concerns introduced between the definition of network policies, their implementation in switching hardware, and the forwarding of traffic, is key to the desired flexibility: by breaking the network control problem into tractable pieces, SDN makes it easier to create and introduce new abstractions in networking, simplifying network management and facilitating network evolution. In this paper we present a comprehensive survey on SDN. We start by introducing the motivation for SDN, explain its main concepts and how it differs from traditional networking, its roots, and the standardization activities regarding this novel paradigm. Next, we present the key building blocks of an SDN infrastructure using a bottom-up, layered approach. We provide an in-depth analysis of the hardware infrastructure, southbound and northbound APIs, network virtualization layers, network operating systems (SDN controllers), network programming languages, and network applications. We also look at cross-layer problems such as debugging and troubleshooting. In an effort to anticipate the future evolution of this new paradigm, we discuss the main ongoing research efforts and challenges of SDN. In particular, we address the design of switches and control platforms -- with a focus on aspects such as resiliency, scalability, performance, security and dependability -- as well as new opportunities for carrier transport networks and cloud providers. Last but not least, we analyze the position of SDN as a key enabler of a software-defined environment.
Buyer to Seller Recommendation under Constraints
Venue: arXiv cs.SI 2014
Year: 2014

The majority of recommender systems are designed to recommend items (such as movies and products) to users. We focus on the problem of recommending buyers to sellers which comes with new challenges: (1) constraints on the number of recommendations buyers are part of before they become overwhelmed, (2) constraints on the number of recommendations sellers receive within their budget, and (3) constraints on the set of buyers that sellers want to receive (e.g., no more than two people from the same household). We propose the following critical problems of recommending buyers to sellers: Constrained Recommendation (C-REC) capturing the first two challenges, and Conflict-Aware Constrained Recommendation (CAC-REC) capturing all three challenges at the same time. We show that C-REC can be modeled using linear programming and can be efficiently solved using modern solvers. On the other hand, we show that CAC-REC is NP-hard. We propose two approximate algorithms to solve CAC-REC and show that they achieve close to optimal solutions via comprehensive experiments using real-world datasets.
Extensions of Configuration Structures
Venue: arXiv cs.DC 2014
Year: 2014

The present paper defines ST-structures (and an extension of these, called STC-structures). The main purpose is to provide concrete relationships between highly expressive concurrency models coming from two different schools of thought: the higher dimensional automata, a \textit{state-based} approach of Pratt and van Glabbeek; and the configuration structures and (in)pure event structures, an \textit{event-based} approach of van Glabbeek and Plotkin. In this respect we make comparative studies of the expressive power of ST-structures relative to the above models. Moreover, standard notions from other concurrency models are defined for ST(C)-structures, like steps and paths, bisimilarities, and action refinement, and related results are given. These investigations of ST(C)-structures are intended to provide a better understanding of the \textit{state-event duality} described by Pratt, and also of the (a)cyclic structures of higher dimensional automata.
Pentapods with Mobility 2
Venue: arXiv cs.RO 2014
Year: 2014

In this paper we give a full classification of all pentapods with mobility 2, where neither all platform anchor points nor all base anchor points are located on a line. Therefore this paper solves the famous Borel-Bricard problem for 2-dimensional motions beside the excluded case of five collinear points with spherical trajectories. But even for this special case we present three new types as a side-result. Based on our study of pentapods, we also give a complete list of all non-architecturally singular hexapods with 2-dimensional self-motions.
A Game-theoretic Machine Learning Approach for Revenue Maximization in Sponsored Search
Venue: arXiv cs.GT 2014
Year: 2014

Sponsored search is an important monetization channel for search engines, in which an auction mechanism is used to select the ads shown to users and determine the prices charged from advertisers. There have been several pieces of work in the literature that investigate how to design an auction mechanism in order to optimize the revenue of the search engine. However, due to some unrealistic assumptions used, the practical values of these studies are not very clear. In this paper, we propose a novel \emph{game-theoretic machine learning} approach, which naturally combines machine learning and game theory, and learns the auction mechanism using a bilevel optimization framework. In particular, we first learn a Markov model from historical data to describe how advertisers change their bids in response to an auction mechanism, and then for any given auction mechanism, we use the learnt model to predict its corresponding future bid sequences. Next we learn the auction mechanism through empirical revenue maximization on the predicted bid sequences. We show that the empirical revenue will converge when the prediction period approaches infinity, and a Genetic Programming algorithm can effectively optimize this empirical revenue. Our experiments indicate that the proposed approach is able to produce a much more effective auction mechanism than several baselines.
McCammond's normal forms for free aperiodic semigroups revisited
Venue: arXiv cs.FL 2014
Year: 2014

This paper revisits the solution of the word problem for $ω$-terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCammond's algorithm, based on normal forms for such terms, uses McCammond's solution of the word problem for certain Burnside semigroups. In this paper, we establish a new, simpler, correctness proof of McCammond's algorithm, based on properties of certain regular languages associated with the normal forms. This method leads to new applications.
Beyond $χ^2$ Difference: Learning Optimal Metric for Boundary Detection
Venue: arXiv cs.CV 2014
Year: 2014

This letter focuses on solving the challenging problem of detecting natural image boundaries. A boundary usually refers to the border between two regions with different semantic meanings. Therefore, a measurement of dissimilarity between image regions plays a pivotal role in boundary detection of natural images. To improve the performance of boundary detection, a Learning-based Boundary Metric (LBM) is proposed to replace $χ^2$ difference adopted by the classical algorithm mPb. Compared with $χ^2$ difference, LBM is composed of a single layer neural network and an RBF kernel, and is fine-tuned by supervised learning rather than human-crafted. It is more effective in describing the dissimilarity between natural image regions while tolerating large variance of image data. After substituting $χ^2$ difference with LBM, the F-measure metric of mPb on the BSDS500 benchmark is increased from 0.69 to 0.71. Moreover, when image features are computed on a single scale, the proposed LBM algorithm still achieves competitive results compared with \emph{mPb}, which makes use of multi-scale image features.
Comfortability of a Team in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

There are many indexes (measures or metrics) in Social Network Analysis (SNA), like density, cohesion, etc. We have defined a new SNA index called "comfortability". In this paper, core comfortable team of a social network is defined based on graph theoretic concepts and some of their structural properties are analyzed. Comfortability is one of the important attributes (characteristics) for a successful team work. So, it is necessary to find a comfortable and successful team in any given social network. It is proved that forming core comfortable team in any network is NP-Complete using the concepts of domination in graph theory. Next, we give two polynomial-time approximation algorithms for finding such a core comfortable team in any given network with performance ratio O(ln Δ), where Δis the maximum degree of a given network (graph). The time complexity of the algorithm is proved to be O(n^{3}), where n is the number of persons (vertices) in the network (graph). It is also proved that the algorithms give good results in scale-free networks.