OpenRaiser/Intern-Atlas huggingface dataset:
Counterfactual Estimation and Optimization of Click Metrics for Search Engines
Venue: arXiv cs.LG 2014
Year: 2014

Optimizing an interactive system against a predefined online metric is particularly challenging, when the metric is computed from user feedback such as clicks and payments. The key challenge is the counterfactual nature: in the case of Web search, any change to a component of the search engine may result in a different search result page for the same query, but we normally cannot infer reliably from search log how users would react to the new result page. Consequently, it appears impossible to accurately estimate online metrics that depend on user feedback, unless the new engine is run to serve users and compared with a baseline in an A/B test. This approach, while valid and successful, is unfortunately expensive and time-consuming. In this paper, we propose to address this problem using causal inference techniques, under the contextual-bandit framework. This approach effectively allows one to run (potentially infinitely) many A/B tests offline from search log, making it possible to estimate and optimize online metrics quickly and inexpensively. Focusing on an important component in a commercial search engine, we show how these ideas can be instantiated and applied, and obtain very promising results that suggest the wide applicability of these techniques.
Online Mechanism Design for Cloud Computing
Venue: arXiv cs.GT 2014
Year: 2014

In this work, we study the problem of online mechanism design for resources allocation and pricing in cloud computing (RAPCC). We show that in general the allocation problems in RAPCC are NP-hard, and therefore we focus on designing dominant-strategy incentive compatible (DSIC) mechanisms with good competitive ratios compared to the offline optimal allocation (with the prior knowledge about the future jobs). We propose two kinds of DSIC online mechanisms. The first mechanism, which is based on a greedy allocation rule and leverages a priority function for allocation, is very fast and has a tight competitive bound. We discuss several priority functions including exponential and linear priority functions, and show that the former one has a better competitive ratio. The second mechanism, which is based on a dynamic program for allocation, also has a tight competitive ratio and performs better than the first one when the maximum demand of cloud customers is close to the capacity of the cloud provider.
Candy Crush is NP-hard
Venue: arXiv cs.CC 2014
Year: 2014

We prove that playing Candy Crush to achieve a given score in a fixed number of swaps is NP-hard.
The Unambiguous Distance in a Phase-based Ranging System with Hopping Frequencies
Venue: arXiv cs.OH 2014
Year: 2014

It is a challenge to specify unambiguous distance (UD) in a phase-based ranging system with hopping frequencies (PRSHF). In this letter, we propose to characterize the UD in a PRSHF by the probability that it takes on its maximum value. We obtain a very simple and elegant expression of the probability with growth estimation techniques from analytic number theory. It is revealed that the UD in a PRSHF usually takes on the maximum value with as few as 10 frequencies in measurement, almost independent of the specific distribution of available bandwidth.
Elicitation and Modeling Non-Functional Requirements - A POS Case Study
Venue: arXiv cs.SE 2014
Year: 2014

Proper management of requirements is crucial to successful development software within limited time and cost. Nonfunctional requirements (NFR) are one of the key criteria to derive a comparison among various software systems. In most of software development NFR have be specified as an additional requirement of software. NFRs such as performance, reliability, maintainability, security, accuracy etc. have to be considered at the early stage of software development as functional requirement (FR). However, identifying NFR is not an easy task. Although there are well developed techniques for eliciting functional requirement, there is a lack of elicitation mechanism for NFR and there is no proper consensus regarding NFR elicitation techniques. Eliciting NFRs are considered to be one of the challenging jobs in requirement analysis. This paper proposes a UML use case based questionary approach to identifying and classifying NFR of a system. The proposed approach is illustrated by using a Point of Sale (POS) case study
Multi-label ensemble based on variable pairwise constraint projection
Venue: arXiv cs.LG 2014
Year: 2014

Multi-label classification has attracted an increasing amount of attention in recent years. To this end, many algorithms have been developed to classify multi-label data in an effective manner. However, they usually do not consider the pairwise relations indicated by sample labels, which actually play important roles in multi-label classification. Inspired by this, we naturally extend the traditional pairwise constraints to the multi-label scenario via a flexible thresholding scheme. Moreover, to improve the generalization ability of the classifier, we adopt a boosting-like strategy to construct a multi-label ensemble from a group of base classifiers. To achieve these goals, this paper presents a novel multi-label classification framework named Variable Pairwise Constraint projection for Multi-label Ensemble (VPCME). Specifically, we take advantage of the variable pairwise constraint projection to learn a lower-dimensional data representation, which preserves the correlations between samples and labels. Thereafter, the base classifiers are trained in the new data space. For the boosting-like strategy, we employ both the variable pairwise constraints and the bootstrap steps to diversify the base classifiers. Empirical studies have shown the superiority of the proposed method in comparison with other approaches.
Combination of PCA with SMOTE Resampling to Boost the Prediction Rate in Lung Cancer Dataset
Venue: arXiv cs.LG 2014
Year: 2014

Classification algorithms are unable to make reliable models on the datasets with huge sizes. These datasets contain many irrelevant and redundant features that mislead the classifiers. Furthermore, many huge datasets have imbalanced class distribution which leads to bias over majority class in the classification process. In this paper combination of unsupervised dimensionality reduction methods with resampling is proposed and the results are tested on Lung-Cancer dataset. In the first step PCA is applied on Lung-Cancer dataset to compact the dataset and eliminate irrelevant features and in the second step SMOTE resampling is carried out to balance the class distribution and increase the variety of sample domain. Finally, Naive Bayes classifier is applied on the resulting dataset and the results are compared and evaluation metrics are calculated. The experiments show the effectiveness of the proposed method across four evaluation metrics: Overall accuracy, False Positive Rate, Precision, Recall.
EEG Compression of Scalp Recordings based on Dipole Fitting
Venue: arXiv cs.IT 2014
Year: 2014

A novel technique for Electroencephalogram (EEG) compression is proposed in this article. This technique models the intrinsic dependency inherent between the different EEG channels. It is based on dipole fitting that is usually used in order to find a solution to the classic problems in EEG analysis: inverse and forward problems. The suggested compression system uses dipole fitting as a first building block to provide an approximation of the recorded signals. Then, (based on a smoothness factor,) appropriate coding techniques are suggested to compress the residuals of the fitting process. Results show that this technique works well for different types of recordings and is even able to provide near- lossless compression for event-related potentials.
Natural Language Feature Selection via Cooccurrence
Venue: arXiv cs.CL 2014
Year: 2014

Specificity is important for extracting collocations, keyphrases, multi-word and index terms [Newman et al. 2012]. It is also useful for tagging, ontology construction [Ryu and Choi 2006], and automatic summarization of documents [Louis and Nenkova 2011, Chali and Hassan 2012]. Term frequency and inverse-document frequency (TF-IDF) are typically used to do this, but fail to take advantage of the semantic relationships between terms [Church and Gale 1995]. The result is that general idiomatic terms are mistaken for specific terms. We demonstrate use of relational data for estimation of term specificity. The specificity of a term can be learned from its distribution of relations with other terms. This technique is useful for identifying relevant words or terms for other natural language processing tasks.
Texture Defect Detection in Gradient Space
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we propose a machine vision algorithm for automatically detecting defects in patterned textures with the help of gradient space and its energy. Experiments on real fabric images with defects show that the proposed method can be used for automatic detection of fabric defects in textile industries.
Straightforward Bibliography Management in R with the RefManageR Package
Venue: arXiv cs.DL 2014
Year: 2014

This work introduces the R package RefManageR, which provides tools for importing and working with bibliographic references. It extends the bibentry class in R in a number of useful ways, including providing R with previously unavailable support for BibLaTeX. BibLaTeX provides a superset of the functionality of BibTeX, including full Unicode support, no memory limitations, additional fields and entry types, and more sophisticated sorting of references. RefManageR provides functions for citing and generating a bibliography with hyperlinks for documents prepared with RMarkdown or RHTML. Existing .bib files can be read into R and converted from BibTeX to BibLaTeX and vice versa. References can also be imported via queries to NCBI's Entrez, Zotero libraries, Google Scholar, and CrossRef. Additionally, references can be created by reading PDFs stored on the user's machine with the help of Poppler. Entries stored in the reference manager can be easily searched by any field, by date ranges, and by various formats for name lists (author by last names, translator by full names, etc.). Entries can also be updated, combined, sorted, printed in a number of styles, and exported.
Implementation of an efficient RBAC in Cloud Computing using .NET environment
Venue: arXiv cs.DC 2014
Year: 2014

Cloud Computing is flourishing day by day and it will continue in developing phase until computers and internet era is in existence. While dealing with cloud computing, a number of security and traffic related issues are confronted. Load Balancing is one of the answers to these issues. RBAC deals with such an answer. The proposed technique involves the hybrid of FCFS with RBAC technique. RBAC will assign roles to the clients and clients with a particular role can only access the particular document. Hence identity management and access management are fully implemented using this technique.
Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
Venue: arXiv cs.FL 2014
Year: 2014

We solve two open problems concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a left ideal or a suffix-closed language with $n$ left quotients (that is, with state complexity $n$) is at most $n^{n-1}+n-1$, and that of a two-sided ideal or a factor-closed language is at most $n^{n-2}+(n-2)2^{n-2}+1$. Since these bounds are known to be reachable, this settles the problems.
Determinants of Patent Citations in Biotechnology: An Analysis of Patent Influence Across the Industrial and Organizational Boundaries
Venue: arXiv cs.DL 2014
Year: 2014

The present paper extends the literature investigating key drivers leading certain patents to exert a stronger influence on the subsequent technological developments (inventions) than other ones. We investigated six key determinants, as (i) the use of scientific knowledge, (ii) the breadth of the technological base, (iii) the existence of collaboration in patent development, (iv) the number of claims, (v) the scope, and (vi) the novelty, and how the effect of these determinants varies when patent influence - as measured by the number of forward citations the patent received - is distinguished as within and across the industrial and organizational boundaries. We conducted an empirical analysis on a sample of 5671 patents granted to 293 US biotechnology firms from 1976 to 2003. Results reveal that the contribution of the determinants to patent influence differs across the domains that are identified by the industrial and organizational boundaries. Findings, for example, show that the use of scientific knowledge negatively affects patent influence outside the biotechnology industry, while it positively contributes to make a patent more relevant for the assignee's subsequent technological developments. In addition, the broader the scope of a patent the higher the number of citations the patent receives from subsequent non-biotechnology patents. This relationship is inverted-U shaped when considering the influence of a patent on inventions granted to other organizations than the patent's assignee. Finally, the novelty of a patent is inverted-U related with the influence the patent exerts on the subsequent inventions granted across the industrial and organizational boundaries.
Stateful Security Protocol Verification
Venue: arXiv cs.CR 2014
Year: 2014

A long-standing research problem in security protocol design is how to efficiently verify security protocols with tamper-resistant global states. In this paper, we address this problem by first proposing a protocol specification framework, which explicitly represents protocol execution states and state transformations. Secondly, we develop an algorithm for verifying security properties by utilizing the key ingredients of the first-order reasoning for reachability analysis, while tracking state transformation and checking the validity of newly generated states. Our verification algorithm is proven to be (partially) correct, if it terminates. We have implemented the proposed framework and verification algorithms in a tool named SSPA, and evaluate it using a number of stateful security protocols. The experimental results show that our approach is not only feasible but also practically efficient. In particular, we have found a security flaw on the digital envelope protocol, which could not be detected by existing security protocol verifiers.
Sublinear Models for Graphs
Venue: arXiv cs.LG 2014
Year: 2014

This contribution extends linear models for feature vectors to sublinear models for graphs and analyzes their properties. The results are (i) a geometric interpretation of sublinear classifiers, (ii) a generic learning rule based on the principle of empirical risk minimization, (iii) a convergence theorem for the margin perceptron in the sublinearly separable case, and (iv) the VC-dimension of sublinear functions. Empirical results on graph data show that sublinear models on graphs have similar properties as linear models for feature vectors.
Mean Square Stability for Stochastic Jump Linear Systems via Optimal Transport
Venue: arXiv cs.SY 2014
Year: 2014

In this note, we provide a unified framework for the mean square stability of stochastic jump linear systems via optimal transport. The Wasserstein metric known as an optimal transport, that assesses the distance between probability density functions enables the stability analysis. Without any assumption on the underlying jump process, this Wasserstein distance guarantees the mean square stability for general stochastic jump linear systems, not necessarily for Markovian jump. The validity of the proposed methods are proved by recovering already-known stability conditions under this framework.
Transfer Learning across Networks for Collective Classification
Venue: arXiv cs.LG 2014
Year: 2014

This paper addresses the problem of transferring useful knowledge from a source network to predict node labels in a newly formed target network. While existing transfer learning research has primarily focused on vector-based data, in which the instances are assumed to be independent and identically distributed, how to effectively transfer knowledge across different information networks has not been well studied, mainly because networks may have their distinct node features and link relationships between nodes. In this paper, we propose a new transfer learning algorithm that attempts to transfer common latent structure features across the source and target networks. The proposed algorithm discovers these latent features by constructing label propagation matrices in the source and target networks, and mapping them into a shared latent feature space. The latent features capture common structure patterns shared by two networks, and serve as domain-independent features to be transferred between networks. Together with domain-dependent node features, we thereafter propose an iterative classification algorithm that leverages label correlations to predict node labels in the target network. Experiments on real-world networks demonstrate that our proposed algorithm can successfully achieve knowledge transfer between networks to help improve the accuracy of classifying nodes in the target network.
Answering queries using pairings
Venue: arXiv cs.CR 2014
Year: 2014

Outsourcing data in the cloud has become nowadays very common. Since -- generally speaking -- cloud data storage and management providers cannot be fully trusted, mechanisms providing the confidentiality of the stored data are necessary. A possible solution is to encrypt all the data, but -- of course -- this poses serious problems about the effective usefulness of the stored data. In this work, we propose to apply a well-known attribute-based cryptographic scheme to cope with the problem of querying encrypted data. We have implemented the proposed scheme with a real-world, off-the-shelf RDBMS and we provide several experimental results showing the feasibility of our approach.
Pattern Formation for Asynchronous Robots without Agreement in Chirality
Venue: arXiv cs.DC 2014
Year: 2014

This paper presents a deterministic algorithm for forming a given asymmetric pattern in finite time by a set of autonomous, homogeneous, oblivious mobile robots under the CORDA model. The robots are represented as points on the 2D plane. There is no explicit communication between the robots. The robots coordinate among themselves by observing the positions of the other robots on the plane. Initially all the robots are assumed to be stationary. The robots have local coordinate systems defined by Sense of Direction (SoD), orientation or chirality and scale. Initially the robots are in asymmetric configuration. We show that these robots can form any given asymmetric pattern in finite time.
Erasure codes with simplex locality
Venue: arXiv cs.IT 2014
Year: 2014

We focus on erasure codes for distributed storage. The distributed storage setting imposes locality requirements because of easy repair demands on the decoder. We first establish the characterization of various locality properties in terms of the generator matrix of the code. These lead to bounds on locality and notions of optimality. We then examine the locality properties of a family of non-binary codes with simplex structure. We investigate their optimality and design several easy repair decoding methods. In particular, we show that any correctable erasure pattern can be solved by easy repair.
Bandwidth-Aware Scheduling with SDN in Hadoop: A New Trend for Big Data
Venue: arXiv cs.DC 2014
Year: 2014

Software Defined Networking (SDN) is a revolutionary network architecture that separates out network control functions from the underlying equipment and is an increasingly trend to help enterprises build more manageable data centers where big data processing emerges as an important part of applications. To concurrently process large-scale data, MapReduce with an open source implementation named Hadoop is proposed. In practical Hadoop systems one kind of issue that vitally impacts the overall performance is know as the NP-complete minimum make span problem. One main solution is to assign tasks on data local nodes to avoid link occupation since network bandwidth is a scarce resource. Many methodologies for enhancing data locality are proposed such as the HDS and state-of-the-art scheduler BAR. However, all of them either ignore allocating tasks in a global view or disregard available bandwidth as the basis for scheduling. In this paper we propose a heuristic bandwidth-aware task scheduler BASS to combine Hadoop with SDN. It is not only able to guarantee data locality in a global view but also can efficiently assign tasks in an optimized way. Both examples and experiments demonstrate that BASS has the best performance in terms of job completion time. To our knowledge, BASS is the first to exploit talent of SDN for big data processing and we believe it points out a new trend for large-scale data processing.
Clustering Effects on Wireless Mobile Ad-Hoc Networks Performances
Venue: arXiv cs.NI 2014
Year: 2014

A new era is dawning for wireless mobile ad hoc networks where communication will be done using a group of mobile devices called cluster, hence clustered network. In a clustered network, protocols used by these mobile devices are different from those used in a wired network; which helps to save computation time and resources efficiently. This paper focuses on Cluster-Based Routing Protocol and Dynamic Source Routing. The results presented in this paper illustrates the implementation of Ad-hoc On-Demand Distance Vector routing protocol for enhancing mobile nodes performance and lifetime in a clustered network and to demonstrate how this routing protocol results in time efficient and resource saving in wireless mobile ad hoc networks.
Towards system development methodologies: From software to cyber-physical domain
Venue: arXiv cs.SE 2014
Year: 2014

In many cases, it is more profitable to apply existing methodologies than to develop new ones. This holds, especially, for system development within the cyber-physical domain: until a certain abstraction level we can (re)use the methodologies for the software system development to benefit from the advantages of these techniques.
HPS: a hierarchical Persian stemming method
Venue: arXiv cs.CL 2014
Year: 2014

In this paper, a novel hierarchical Persian stemming approach based on the Part-Of-Speech of the word in a sentence is presented. The implemented stemmer includes hash tables and several deterministic finite automata in its different levels of hierarchy for removing the prefixes and suffixes of the words. We had two intentions in using hash tables in our method. The first one is that the DFA don't support some special words, so hash table can partly solve the addressed problem. the second goal is to speed up the implemented stemmer with omitting the time that deterministic finite automata need. Because of the hierarchical organization, this method is fast and flexible enough. Our experiments on test sets from Hamshahri collection and security news (istna.ir) show that our method has the average accuracy of 95.37% which is even improved in using the method on a test set with common topics.
Consolidated Model of Procedures for Workflow Management
Venue: arXiv cs.SE 2014
Year: 2014

The article presents an approach to automation of business processes by means of a consolidated model describing a class of processes. Rules and examples for building a consolidated model are given. The model is validated through development of a software application called COMPASS-P for monitoring of procedures for evaluation and accreditation of education.