OpenRaiser/Intern-Atlas huggingface dataset:
Toward an Integrated Framework for Automated Development and Optimization of Online Advertising Campaigns
Venue: arXiv cs.IR 2012
Year: 2012

Creating and monitoring competitive and cost-effective pay-per-click advertisement campaigns through the web-search channel is a resource demanding task in terms of expertise and effort. Assisting or even automating the work of an advertising specialist will have an unrivaled commercial value. In this paper we propose a methodology, an architecture, and a fully functional framework for semi- and fully- automated creation, monitoring, and optimization of cost-efficient pay-per-click campaigns with budget constraints. The campaign creation module generates automatically keywords based on the content of the web page to be advertised extended with corresponding ad-texts. These keywords are used to create automatically the campaigns fully equipped with the appropriate values set. The campaigns are uploaded to the auctioneer platform and start running. The optimization module focuses on the learning process from existing campaign statistics and also from applied strategies of previous periods in order to invest optimally in the next period. The objective is to maximize the performance (i.e. clicks, actions) under the current budget constraint. The fully functional prototype is experimentally evaluated on real world Google AdWords campaigns and presents a promising behavior with regards to campaign performance statistics as it outperforms systematically the competing manually maintained campaigns.
One Permutation Hashing for Efficient Search and Learning
Venue: arXiv cs.LG 2012
Year: 2012

Recently, the method of b-bit minwise hashing has been applied to large-scale linear learning and sublinear time near-neighbor search. The major drawback of minwise hashing is the expensive preprocessing cost, as the method requires applying (e.g.,) k=200 to 500 permutations on the data. The testing time can also be expensive if a new data point (e.g., a new document or image) has not been processed, which might be a significant issue in user-facing applications. We develop a very simple solution based on one permutation hashing. Conceptually, given a massive binary data matrix, we permute the columns only once and divide the permuted columns evenly into k bins; and we simply store, for each data vector, the smallest nonzero location in each bin. The interesting probability analysis (which is validated by experiments) reveals that our one permutation scheme should perform very similarly to the original (k-permutation) minwise hashing. In fact, the one permutation scheme can be even slightly more accurate, due to the "sample-without-replacement" effect. Our experiments with training linear SVM and logistic regression on the webspam dataset demonstrate that this one permutation hashing scheme can achieve the same (or even slightly better) accuracies compared to the original k-permutation scheme. To test the robustness of our method, we also experiment with the small news20 dataset which is very sparse and has merely on average 500 nonzeros in each data vector. Interestingly, our one permutation scheme noticeably outperforms the k-permutation scheme when k is not too small on the news20 dataset. In summary, our method can achieve at least the same accuracy as the original k-permutation scheme, at merely 1/k of the original preprocessing cost.
The Power of Centralized PC Systems of Pushdown Automata
Venue: arXiv cs.FL 2012
Year: 2012

Parallel communicating systems of pushdown automata (PCPA) were introduced in (Csuhaj-Varj{ú} et. al. 2000) and in their centralized variants shown to be able to simulate nondeterministic one-way multi-head pushdown automata. A claimed converse simulation for returning mode (Balan 2009) turned out to be incomplete (Otto 2012) and a language was suggested for separating these PCPA of degree two (number of pushdown automata) from nondeterministic one-way two-head pushdown automata. We show that the suggested language can be accepted by the latter computational model. We present a different example over a single letter alphabet indeed ruling out the possibility of a simulation between the models. The open question about the power of centralized PCPA working in returning mode is then settled by showing them to be universal. Since the construction is possible using systems of degree two, this also improves the previous bound three for generating all recursively enumerable languages. Finally PCPAs are restricted in such a way that a simulation by multi-head automata is possible.
Mechanism Design for Time Critical and Cost Critical Task Execution via Crowdsourcing
Venue: arXiv cs.GT 2012
Year: 2012

An exciting application of crowdsourcing is to use social networks in complex task execution. In this paper, we address the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an {\em atomic task} as well as in recruiting other agents to execute the task. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We identify a set of desirable properties that should ideally be satisfied by a crowdsourcing mechanism. In particular, {\em sybil-proofness} and {\em collapse-proofness} are two complementary properties in our desiderata. We prove that no mechanism can satisfy all the desirable properties simultaneously. This leads us naturally to explore approximate versions of the critical properties. We focus our attention on approximate sybil-proofness and our exploration leads to a parametrized family of payment mechanisms which satisfy collapse-proofness. We characterize the approximate versions of the desirable properties in cost critical and time critical domain.
Guidelines for a Dynamic Ontology - Integrating Tools of Evolution and Versioning in Ontology
Venue: arXiv cs.SE 2012
Year: 2012

Ontologies are built on systems that conceptually evolve over time. In addition, techniques and languages for building ontologies evolve too. This has led to numerous studies in the field of ontology versioning and ontology evolution. This paper presents a new way to manage the lifecycle of an ontology incorporating both versioning tools and evolution process. This solution, called VersionGraph, is integrated in the source ontology since its creation in order to make it possible to evolve and to be versioned. Change management is strongly related to the model in which the ontology is represented. Therefore, we focus on the OWL language in order to take into account the impact of the changes on the logical consistency of the ontology like specified in OWL DL.
Operator formalism for optical neural network based on the parametrical four-wave mixing process
Venue: arXiv cs.ET 2012
Year: 2012

In this paper we develop a formalism allowing us to describe operating of a network based on the parametrical four-wave mixing process that is well-known in nonlinear optics. The recognition power of a network using parametric neurons operating with q different frequencies is considered. It is shown that the storage capacity of such a network is higher compared with the Potts-glass models.
Metric Learning across Heterogeneous Domains by Respectively Aligning Both Priors and Posteriors
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we attempts to learn a single metric across two heterogeneous domains where source domain is fully labeled and has many samples while target domain has only a few labeled samples but abundant unlabeled samples. To the best of our knowledge, this task is seldom touched. The proposed learning model has a simple underlying motivation: all the samples in both the source and the target domains are mapped into a common space, where both their priors P(sample)s and their posteriors P(label|sample)s are forced to be respectively aligned as much as possible. We show that the two mappings, from both the source domain and the target domain to the common space, can be reparameterized into a single positive semi-definite(PSD) matrix. Then we develop an efficient Bregman Projection algorithm to optimize the PDS matrix over which a LogDet function is used to regularize. Furthermore, we also show that this model can be easily kernelized and verify its effectiveness in crosslanguage retrieval task and cross-domain object recognition task.
Performance and Detection of M-ary Frequency Shift Keying in Triple Layer Wireless Sensor Network
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes an innovative triple layer Wireless Sensor Network (WSN) system, which monitors M-ary events like temperature, pressure, humidity, etc. with the help of geographically distributed sensors. The sensors convey signals to the fusion centre using M-ary Frequency Shift Keying (MFSK)modulation scheme over independent Rayleigh fading channels. At the fusion centre, detection takes place with the help of Selection Combining (SC) diversity scheme, which assures a simple and economical receiver circuitry. With the aid of various simulations, the performance and efficacy of the system has been analyzed by varying modulation levels, number of local sensors and probability of correct detection by the sensors. The study endeavors to prove that triple layer WSN system is an economical and dependable system capable of correct detection of M-ary events by integrating frequency diversity together with antenna diversity.
A Survey on Authentication and Key Agreement Protocols in Heterogeneous Networks
Venue: arXiv cs.CR 2012
Year: 2012

Unlike current closed systems such as 2nd and 3rd generations where the core network is controlled by a sole network operator, multiple network operators will coexist and manage the core network in Next Generation Networks (NGNs). This open architecture and the collaboration between different network operators will support ubiquitous connectivity and thus enhances users' experience. However, this brings to the fore certain security issues which must be addressed, the most important of which is the initial Authentication and Key Agreement (AKA) to identify and authorize mobile nodes on these various networks. This paper looks at how existing research efforts the HOKEY WG, Mobile Ethernet and 3GPP frameworks respond to this new environment and provide security mechanisms. The analysis shows that most of the research had realized the openness of the core network and tried to deal with it using different methods. These methods will be extensively analysed in order to highlight their strengths and weaknesses.
Algorithmic Simplicity and Relevance
Venue: arXiv cs.AI 2012
Year: 2012

The human mind is known to be sensitive to complexity. For instance, the visual system reconstructs hidden parts of objects following a principle of maximum simplicity. We suggest here that higher cognitive processes, such as the selection of relevant situations, are sensitive to variations of complexity. Situations are relevant to human beings when they appear simpler to describe than to generate. This definition offers a predictive (i.e. falsifiable) model for the selection of situations worth reporting (interestingness) and for what individuals consider an appropriate move in conversation.
CrowdER: Crowdsourcing Entity Resolution
Venue: arXiv cs.DB 2012
Year: 2012

Entity resolution is central to data integration and data cleaning. Algorithmic approaches have been improving in quality, but remain far from perfect. Crowdsourcing platforms offer a more accurate but expensive (and slow) way to bring human insight into the process. Previous work has proposed batching verification tasks for presentation to human workers but even with batching, a human-only approach is infeasible for data sets of even moderate size, due to the large numbers of matches to be tested. Instead, we propose a hybrid human-machine approach in which machines are used to do an initial, coarse pass over all the data, and people are used to verify only the most likely matching pairs. We show that for such a hybrid system, generating the minimum number of verification tasks of a given size is NP-Hard, but we develop a novel two-tiered heuristic approach for creating batched tasks. We describe this method, and present the results of extensive experiments on real data sets using a popular crowdsourcing platform. The experiments show that our hybrid approach achieves both good efficiency and high accuracy compared to machine-only or human-only alternatives.
Uncertain Time-Series Similarity: Return to the Basics
Venue: arXiv cs.DB 2012
Year: 2012

In the last years there has been a considerable increase in the availability of continuous sensor measurements in a wide range of application domains, such as Location-Based Services (LBS), medical monitoring systems, manufacturing plants and engineering facilities to ensure efficiency, product quality and safety, hydrologic and geologic observing systems, pollution management, and others. Due to the inherent imprecision of sensor observations, many investigations have recently turned into querying, mining and storing uncertain data. Uncertainty can also be due to data aggregation, privacy-preserving transforms, and error-prone mining algorithms. In this study, we survey the techniques that have been proposed specifically for modeling and processing uncertain time series, an important model for temporal data. We provide an analytical evaluation of the alternatives that have been proposed in the literature, highlighting the advantages and disadvantages of each approach, and further compare these alternatives with two additional techniques that were carefully studied before. We conduct an extensive experimental evaluation with 17 real datasets, and discuss some surprising results, which suggest that a fruitful research direction is to take into account the temporal correlations in the time series. Based on our evaluations, we also provide guidelines useful for the practitioners in the field.
Technical report: CSVM dictionaries
Venue: arXiv cs.CE 2012
Year: 2012

CSVM (CSV with Metadata) is a simple file format for tabular data. The possible application domain is the same as typical spreadsheets files, but CSVM is well suited for long term storage and the inter-conversion of RAW data. CSVM embeds different levels for data, metadata and annotations in human readable format and flat ASCII files. As a proof of concept, Perl and Python toolkits were designed in order to handle CSVM data and objects in workflows. These parsers can process CSVM files independently of data types, so it is possible to use same data format and parser for a lot of scientific purposes. CSVM-1 is the first version of CSVM specification, an extension of CSVM-1 for implementing a translation system between CSVM files is presented in this paper. The necessary data used to make the translation are also coded in another CSVM file. This particular kind of CSVM is called a CSVM dictionary, it is also readable by the current CSVM parser and it is fully supported by the Python toolkit. This report presents a proposal for CSVM dictionaries, a working example in chemistry, and some elements of Python toolkit usable to handle these files.
Comparison of different T-norm operators in classification problems
Venue: arXiv cs.AI 2012
Year: 2012

Fuzzy rule based classification systems are one of the most popular fuzzy modeling systems used in pattern classification problems. This paper investigates the effect of applying nine different T-norms in fuzzy rule based classification systems. In the recent researches, fuzzy versions of confidence and support merits from the field of data mining have been widely used for both rules selecting and weighting in the construction of fuzzy rule based classification systems. For calculating these merits the product has been usually used as a T-norm. In this paper different T-norms have been used for calculating the confidence and support measures. Therefore, the calculations in rule selection and rule weighting steps (in the process of constructing the fuzzy rule based classification systems) are modified by employing these T-norms. Consequently, these changes in calculation results in altering the overall accuracy of rule based classification systems. Experimental results obtained on some well-known data sets show that the best performance is produced by employing the Aczel-Alsina operator in terms of the classification accuracy, the second best operator is Dubois-Prade and the third best operator is Dombi. In experiments, we have used 12 data sets with numerical attributes from the University of California, Irvine machine learning repository (UCI).
Tag Spotting at the Interference Range
Venue: arXiv cs.NI 2012
Year: 2012

In wireless networks, the presence of interference among wireless links in- troduces dependencies among flows that do not share a single link or node. As a result, when designing a resource allocation scheme, be it a medium access scheduler or a flow rate controller, one needs to consider the interdependence among nodes within interference range of each other. Specifically, control plane information needs to reach nearby nodes which often lie outside the communi- cation range, but within the interference range of a node of interest. But how can one communicate control plane information well beyond the existing communication range? To address this fundamental need we introduce tag spotting. Tag spotting refers to a communication system which allows re- liable control data transmission at SNR values as low as 0 dB. It does this by employing a number of signal encoding techniques including adding redundancy to multitone modulation, shaping the spectrum to reduce inter-carrier interfer- ence, and the use of algebraic coding. Making use of a detection theory-based model we analyze the performance achievable by our modulation as well as the trade-off between the rate of the information transmitted and the likelihood of error. Using real-world experiments on an OFDM system built with software radios, we show that we can transmit data at the target SNR value of 0 dB with a 6% overhead; that is, 6% of our packet is used for our low-SNR decodable tags (which carry up to a couple of bytes of data in our testbed), while the remain- ing 94% is used for traditional header and payload data. We also demonstrate via simulations how tag spotting can be used in implementing fair and efficient rate control and scheduling schemes.
Applying CEGAR to the Petri Net State Equation
Venue: arXiv cs.LO 2012
Year: 2012

We propose a reachability verification technique that combines the Petri net state equation (a linear algebraic overapproximation of the set of reachable states) with the concept of counterexample guided abstraction refinement. In essence, we replace the search through the set of reachable states by a search through the space of solutions of the state equation. We demonstrate the excellent performance of the technique on several real-world examples. The technique is particularly useful in those cases where the reachability query yields a negative result: While state space based techniques need to fully expand the state space in this case, our technique often terminates promptly. In addition, we can derive some diagnostic information in case of unreachability while state space methods can only provide witness paths in the case of reachability.
An approach to describing and analysing bulk biological annotation quality: a case study using UniProtKB
Venue: arXiv cs.CE 2012
Year: 2012

Motivation: Annotations are a key feature of many biological databases, used to convey our knowledge of a sequence to the reader. Ideally, annotations are curated manually, however manual curation is costly, time consuming and requires expert knowledge and training. Given these issues and the exponential increase of data, many databases implement automated annotation pipelines in an attempt to avoid un-annotated entries. Both manual and automated annotations vary in quality between databases and annotators, making assessment of annotation reliability problematic for users. The community lacks a generic measure for determining annotation quality and correctness, which we look at addressing within this article. Specifically we investigate word reuse within bulk textual annotations and relate this to Zipf's Principle of Least Effort. We use UniProt Knowledge Base (UniProtKB) as a case study to demonstrate this approach since it allows us to compare annotation change, both over time and between automated and manually curated annotations. Results: By applying power-law distributions to word reuse in annotation, we show clear trends in UniProtKB over time, which are consistent with existing studies of quality on free text English. Further, we show a clear distinction between manual and automated analysis and investigate cohorts of protein records as they mature. These results suggest that this approach holds distinct promise as a mechanism for judging annotation quality. Availability: Source code is available at the authors website: http://homepages.cs.ncl.ac.uk/m.j.bell1/annotation. Contact: phillip.lord@newcastle.ac.uk
A Large Population Size Can Be Unhelpful in Evolutionary Algorithms
Venue: arXiv cs.NE 2012
Year: 2012

The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002) showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multi-modal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems.
TCP Injections for Fun and Clogging
Venue: arXiv cs.CR 2012
Year: 2012

We present a new type of clogging DoS attacks, with the highest amplification factors achieved by off-path attackers, using only puppets, i.e., sandboxed malware on victim machines. Specifically, we present off-path variants of the Opt-ack, Ack-storm and Coremelt DoS attacks, achieving results comparable to these achieved previously achieved by eavesdropping/MitM attackers and (unrestricted) malware. In contrast to previous off-path attacks, which attacked the client (machine) running the malware, our attacks address a very different goal: large-scale clogging DoS of a third party, or even of backbone connections. Our clogging attacks are based on off-path TCP injections. Indeed, as an additional contribution, we present improved off-path TCP injection attacks. Our new attacks significantly relax the requirements cf. to the known attacks; specifically, our injection attack requires only a Java script in browser sandbox (not 'restricted malware'), does not depend on specific operating system properties, and is efficient even when client's port is determined using recommended algorithm. Our attacks are constructed modularly, allowing reuse of modules for other scenarios and replacing modules as necessary. We present specific defenses, however, this work is further proof to the need to base security on sound foundations, using cryptography to provide security even against MitM attackers.