OpenRaiser/Intern-Atlas huggingface dataset:
On Calibrated Predictions for Auction Selection Mechanisms
Venue: arXiv cs.GT 2012
Year: 2012

Calibration is a basic property for prediction systems, and algorithms for achieving it are well-studied in both statistics and machine learning. In many applications, however, the predictions are used to make decisions that select which observations are made. This makes calibration difficult, as adjusting predictions to achieve calibration changes future data. We focus on click-through-rate (CTR) prediction for search ad auctions. Here, CTR predictions are used by an auction that determines which ads are shown, and we want to maximize the value generated by the auction. We show that certain natural notions of calibration can be impossible to achieve, depending on the details of the auction. We also show that it can be impossible to maximize auction efficiency while using calibrated predictions. Finally, we give conditions under which calibration is achievable and simultaneously maximizes auction efficiency: roughly speaking, bids and queries must not contain information about CTRs that is not already captured by the predictions.
Intermediate Performance Analysis of Growth Codes
Venue: arXiv cs.IT 2012
Year: 2012

Growth codes are a subclass of Rateless codes that have found interesting applications in data dissemination problems. Compared to other Rateless and conventional channel codes, Growth codes show improved intermediate performance which is particularly useful in applications where performance increases with the number of decoded data units. In this paper, we provide a generic analytical framework for studying the asymptotic performance of Growth codes in different settings. Our analysis based on Wormald method applies to any class of Rateless codes that does not include a precoding step. We evaluate the decoding probability model for short codeblocks and validate our findings by experiments. We then exploit the decoding probability model in an illustrative application of Growth codes to error resilient video transmission. The video transmission problem is cast as a joint source and channel rate allocation problem that is shown to be convex with respect to the channel rate. This application permits to highlight the main advantage of Growth codes that is improved performance (hence distortion in video) in the intermediate loss region.
Network Equivalence in the Presence of an Eavesdropper
Venue: arXiv cs.IT 2012
Year: 2012

We consider networks of noisy degraded wiretap channels in the presence of an eavesdropper. For the case where the eavesdropper can wiretap at most one channel at a time, we show that the secrecy capacity region, for a broad class of channels and any given network topology and communication demands, is equivalent to that of a corresponding network where each noisy wiretap channel is replaced by a noiseless wiretap channel. Thus in this case there is a separation between wiretap channel coding on each channel and secure network coding on the resulting noiseless network. We show with an example that such separation does not hold when the eavesdropper can access multiple channels at the same time, for which case we provide upper and lower bounding noiseless networks.
Cost-sensitive C4.5 with post-pruning and competition
Venue: arXiv cs.AI 2012
Year: 2012

Decision tree is an effective classification approach in data mining and machine learning. In applications, test costs and misclassification costs should be considered while inducing decision trees. Recently, some cost-sensitive learning algorithms based on ID3 such as CS-ID3, IDX, λ-ID3 have been proposed to deal with the issue. These algorithms deal with only symbolic data. In this paper, we develop a decision tree algorithm inspired by C4.5 for numeric data. There are two major issues for our algorithm. First, we develop the test cost weighted information gain ratio as the heuristic information. According to this heuristic information, our algorithm is to pick the attribute that provides more gain ratio and costs less for each selection. Second, we design a post-pruning strategy through considering the tradeoff between test costs and misclassification costs of the generated decision tree. In this way, the total cost is reduced. Experimental results indicate that (1) our algorithm is stable and effective; (2) the post-pruning technique reduces the total cost significantly; (3) the competition strategy is effective to obtain a cost-sensitive decision tree with low cost.
On the Pareto-Optimal Beam Structure and Design for Multi-User MIMO Interference Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, the Pareto-optimal beam structure for multi-user multiple-input multiple-output (MIMO) interference channels is investigated and a necessary condition for any Pareto-optimal transmit signal covariance matrix is presented for the K-pair Gaussian (N,M_1,...,M_K) interference channel. It is shown that any Pareto-optimal transmit signal covariance matrix at a transmitter should have its column space contained in the union of the eigen-spaces of the channel matrices from the transmitter to all receivers. Based on this necessary condition, an efficient parameterization for the beam search space is proposed. The proposed parameterization is given by the product manifold of a Stiefel manifold and a subset of a hyperplane and enables us to construct a very efficient beam design algorithm by exploiting its rich geometrical structure and existing tools for optimization on Stiefel manifolds. Reduction in the beam search space dimension and computational complexity by the proposed parameterization and the proposed beam design approach is significant when the number of transmit antennas is larger than the sum of the numbers of receive antennas, as in upcoming cellular networks adopting massive MIMO technologies. Numerical results validate the proposed parameterization and the proposed cooperative beam design method based on the parameterization for MIMO interference channels.
On Achievable Schemes of Interference Alignment in Constant Channels via Finite Amplify-and-Forward Relays
Venue: arXiv cs.IT 2012
Year: 2012

This paper elaborates on the achievable schemes of interference alignment in constant channels via finite amplify-and-forward (AF) relays. Consider $K$ sources communicating with $K$ destinations without direct links besides the relay connections. The total number of relays is finite. The objective is to achieve interference alignment for all user pairs to obtain half of their interference-free degrees of freedom. In general, two strategies are employed: coding at the edge and coding in the middle, in which relays show different roles. The contributions are that two fundamental and critical elements are captured to enable interference alignment in this network: channel randomness or relativity; subspace dimension suppression.
On the Separability of Targets Using Binary Proximity Sensors
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem where a network of sensors has to detect the presence of targets at any of $n$ possible locations in a finite region. All such locations may not be occupied by a target. The data from sensors is fused to determine the set of locations that have targets. We term this the separability problem. In this paper, we address the separability of an asymptotically large number of static target locations by using binary proximity sensors. Two models for target locations are considered: (i) when target locations lie on a uniformly spaced grid; and, (ii) when target locations are i.i.d. uniformly distributed in the area. Sensor locations are i.i.d uniformly distributed in the same finite region, independent of target locations. We derive conditions on the sensing radius and the number of sensors required to achieve separability. Order-optimal scaling laws, on the number of sensors as a function of the number of target locations, for two types of separability requirements are derived. The robustness or security aspects of the above problem is also addressed. It is shown that in the presence of adversarial sensors, which toggle their sensed reading and inject binary noise, the scaling laws for separability remain unaffected.
Survey on Incremental Approaches for Network Anomaly Detection
Venue: arXiv cs.CR 2012
Year: 2012

As the communication industry has connected distant corners of the globe using advances in network technology, intruders or attackers have also increased attacks on networking infrastructure commensurately. System administrators can attempt to prevent such attacks using intrusion detection tools and systems. There are many commercially available signature-based Intrusion Detection Systems (IDSs). However, most IDSs lack the capability to detect novel or previously unknown attacks. A special type of IDSs, called Anomaly Detection Systems, develop models based on normal system or network behavior, with the goal of detecting both known and unknown attacks. Anomaly detection systems face many problems including high rate of false alarm, ability to work in online mode, and scalability. This paper presents a selective survey of incremental approaches for detecting anomaly in normal system or network traffic. The technological trends, open problems, and challenges over anomaly detection using incremental approach are also discussed.
The crossing number of pancake graph $P_4$ is six
Venue: arXiv cs.DM 2012
Year: 2012

The {\it crossing number} of a graph $G$ is the least number of pairwise crossings of edges among all the drawings of $G$ in the plane. The pancake graph is an important topology for interconnecting processors in parallel computers. In this paper, we prove the exact value of the crossing number of pancake graph $P_4$ is six.
Content based video retrieval
Venue: arXiv cs.MM 2012
Year: 2012

Content based video retrieval is an approach for facilitating the searching and browsing of large image collections over World Wide Web. In this approach, video analysis is conducted on low level visual properties extracted from video frame. We believed that in order to create an effective video retrieval system, visual perception must be taken into account. We conjectured that a technique which employs multiple features for indexing and retrieval would be more effective in the discrimination and search tasks of videos. In order to validate this claim, content based indexing and retrieval systems were implemented using color histogram, various texture features and other approaches. Videos were stored in Oracle 9i Database and a user study measured correctness of response.
IPv6 Prefix Alteration: An Opportunity to Improve Online Privacy
Venue: arXiv cs.CR 2012
Year: 2012

This paper is focused on privacy issues related to the prefix part of IPv6 addresses. Long-lived prefixes may introduce additional tracking opportunities for communication partners and third parties. We outline a number of prefix alteration schemes that may be deployed to maintain the unlinkability of users' activities. While none of the schemes will solve all privacy problems on the Internet on their own, we argue that the development of practical prefix alteration techniques constitutes a worthwile avenue to pursue: They would allow Internet Service Providers to increase the attainable privacy level well above the status quo in today's IPv4 networks.
XSS-FP: Browser Fingerprinting using HTML Parser Quirks
Venue: arXiv cs.CR 2012
Year: 2012

There are many scenarios in which inferring the type of a client browser is desirable, for instance to fight against session stealing. This is known as browser fingerprinting. This paper presents and evaluates a novel fingerprinting technique to determine the exact nature (browser type and version, eg Firefox 15) of a web-browser, exploiting HTML parser quirks exercised through XSS. Our experiments show that the exact version of a web browser can be determined with 71% of accuracy, and that only 6 tests are sufficient to quickly determine the exact family a web browser belongs to.
Channel Independent Cryptographic Key Distribution
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a method of cryptographic key distribution using an `artificially' noisy channel. This is an important development because, while it is known that a noisy channel can be used to generate unconditional secrecy, there are many circumstances in which it is not possible to have a noisy information exchange, such as in error corrected communication stacks. It is shown that two legitimate parties can simulate a noisy channel by adding local noise onto the communication and that the simulated channel has a secrecy capacity even if the underlying channel does not. A derivation of the secrecy conditions is presented along with numerical simulations of the channel function to show that key exchange is feasible.
Enhanced Contention Resolution Aloha - ECRA
Venue: arXiv cs.IT 2012
Year: 2012

Random Access (RA) Medium Access (MAC) protocols are simple and effective when the nature of the traffic is unpredictable and random. In the following paper, a novel RA protocol called Enhanced Contention Resolution ALOHA (ECRA) is presented. This evolution, based on the previous Contention Resolution ALOHA (CRA) protocol, exploits the nature of the interference in unslotted Aloha-like channels for trying to resolve most of the partial collision that can occur there. In the paper, the idea behind ECRA is presented together with numerical simulations and a mathematical analysis of its performance gain. It is shown that relevant performance increases in both throughput and Packet Error Rate (PER) can be reached by ECRA with respect to CRA. A comparison with Contention Resolution Diversity Slotted ALOHA (CRDSA) is also provided.
Faster Compact Top-k Document Retrieval
Venue: arXiv cs.DS 2012
Year: 2012

An optimal index solving top-k document retrieval [Navarro and Nekrich, SODA12] takes O(m + k) time for a pattern of length m, but its space is at least 80n bytes for a collection of n symbols. We reduce it to 1.5n to 3n bytes, with O(m+(k+log log n) log log n) time, on typical texts. The index is up to 25 times faster than the best previous compressed solutions, and requires at most 5% more space in practice (and in some cases as little as one half). Apart from replacing classical by compressed data structures, our main idea is to replace suffix tree sampling by frequency thresholding to achieve compression.
A hybrid cross entropy algorithm for solving dynamic transit network design problem
Venue: arXiv cs.NI 2012
Year: 2012

This paper proposes a hybrid multiagent learning algorithm for solving the dynamic simulation-based bilevel network design problem. The objective is to determine the op-timal frequency of a multimodal transit network, which minimizes total users' travel cost and operation cost of transit lines. The problem is formulated as a bilevel programming problem with equilibrium constraints describing non-cooperative Nash equilibrium in a dynamic simulation-based transit assignment context. A hybrid algorithm combing the cross entropy multiagent learning algorithm and Hooke-Jeeves algorithm is proposed. Computational results are provided on the Sioux Falls network to illustrate the perform-ance of the proposed algorithm.
Ecosystem-Oriented Distributed Evolutionary Computing
Venue: arXiv cs.NE 2012
Year: 2012

We create a novel optimisation technique inspired by natural ecosystems, where the optimisation works at two levels: a first optimisation, migration of genes which are distributed in a peer-to-peer network, operating continuously in time; this process feeds a second optimisation based on evolutionary computing that operates locally on single peers and is aimed at finding solutions to satisfy locally relevant constraints. We consider from the domain of computer science distributed evolutionary computing, with the relevant theory from the domain of theoretical biology, including the fields of evolutionary and ecological theory, the topological structure of ecosystems, and evolutionary processes within distributed environments. We then define ecosystem- oriented distributed evolutionary computing, imbibed with the properties of self-organisation, scalability and sustainability from natural ecosystems, including a novel form of distributed evolu- tionary computing. Finally, we conclude with a discussion of the apparent compromises resulting from the hybrid model created, such as the network topology.
Bypassing the Combinatorial Explosion: Using Similarity to Generate and Prioritize T-wise Test Suites for Large Software Product Lines
Venue: arXiv cs.SE 2012
Year: 2012

Software Product Lines (SPLs) are families of products whose commonalities and variability can be captured by Feature Models (FMs). T-wise testing aims at finding errors triggered by all interactions amongst t features, thus reducing drastically the number of products to test. T-wise testing approaches for SPLs are limited to small values of t -- which miss faulty interactions -- or limited by the size of the FM. Furthermore, they neither prioritize the products to test nor provide means to finely control the generation process. This paper offers (a) a search-based approach capable of generating products for large SPLs, forming a scalable and flexible alternative to current techniques and (b) prioritization algorithms for any set of products. Experiments conducted on 124 FMs (including large FMs such as the Linux kernel) demonstrate the feasibility and the practicality of our approach.
Theano: new features and speed improvements
Venue: arXiv cs.SC 2012
Year: 2012

Theano is a linear algebra compiler that optimizes a user's symbolically-specified mathematical computations to produce efficient low-level implementations. In this paper, we present new features and efficiency improvements to Theano, and benchmarks demonstrating Theano's performance relative to Torch7, a recently introduced machine learning library, and to RNNLM, a C++ library targeted at recurrent neural networks.
Detection of elliptical shapes via cross-entropy clustering
Venue: arXiv cs.CV 2012
Year: 2012

The problem of finding elliptical shapes in an image will be considered. We discuss the solution which uses cross-entropy clustering. The proposed method allows the search for ellipses with predefined sizes and position in the space. Moreover, it works well for search of ellipsoids in higher dimensions.
Visualization and clustering by 3D cellular automata: Application to unstructured data
Venue: arXiv cs.AI 2012
Year: 2012

Given the limited performance of 2D cellular automata in terms of space when the number of documents increases and in terms of visualization clusters, our motivation was to experiment these cellular automata by increasing the size to view the impact of size on quality of results. The representation of textual data was carried out by a vector model whose components are derived from the overall balancing of the used corpus, Term Frequency Inverse Document Frequency (TF-IDF). The WorldNet thesaurus has been used to address the problem of the lemmatization of the words because the representation used in this study is that of the bags of words. Another independent method of the language was used to represent textual records is that of the n-grams. Several measures of similarity have been tested. To validate the classification we have used two measures of assessment based on the recall and precision (f-measure and entropy). The results are promising and confirm the idea to increase the dimension to the problem of the spatiality of the classes. The results obtained in terms of purity class (i.e. the minimum value of entropy) shows that the number of documents over longer believes the results are better for 3D cellular automata, which was not obvious to the 2D dimension. In terms of spatial navigation, cellular automata provide very good 3D performance visualization than 2D cellular automata.
A bird's-eye view of scientific trading: Dependency relations among fields of science
Venue: arXiv cs.DL 2012
Year: 2012

We use a trading metaphor to study knowledge transfer in the sciences as well as the social sciences. The metaphor comprises four dimensions: (a) Discipline Self-dependence, (b) Knowledge Exports/Imports, (c) Scientific Trading Dynamics, and (d) Scientific Trading Impact. This framework is applied to a dataset of 221 Web of Science subject categories. We find that: (i) the Scientific Trading Impact and Dynamics of Materials Science And Transportation Science have increased; (ii) Biomedical Disciplines, Physics, And Mathematics are significant knowledge exporters, as is Statistics & Probability; (iii) in the social sciences, Economics, Business, Psychology, Management, And Sociology are important knowledge exporters; (iv) Discipline Self-dependence is associated with specialized domains which have ties to professional practice (e.g., Law, Ophthalmology, Dentistry, Oral Surgery & Medicine, Psychology, Psychoanalysis, Veterinary Sciences, And Nursing).
On the Evolution of the Internet Economic Ecosystem
Venue: arXiv cs.NI 2012
Year: 2012

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.
A Methodology to Extract Social Network from the Web Snippet
Venue: arXiv cs.SI 2012
Year: 2012

The Web has been chosen as a basic infrastructure to gain the social structure information, through the social network extraction, from all over the world. However, most of the web documents are unstructured and lack of semantics. Moreover, that network is subject to all kinds of changes and dynamics, and a network can be very complex due to the large number of nodes and links Web contains. In this paper, we discuss a methodology that meant to assists in extracting and modeling the social network from Web snippet. As the manual social network extraction of web documents is impractical and unscalable, and fully automated extraction are still at the very early stage to be implemented, we proposed a (semi)-automatic extraction based on the superficial methods.
Rendezvous of two robots with visible bits
Venue: arXiv cs.MA 2012
Year: 2012

We study the rendezvous problem for two robots moving in the plane (or on a line). Robots are autonomous, anonymous, oblivious, and carry colored lights that are visible to both. We consider deterministic distributed algorithms in which robots do not use distance information, but try to reduce (or increase) their distance by a constant factor, depending on their lights' colors. We give a complete characterization of the number of colors that are necessary to solve the rendezvous problem in every possible model, ranging from fully synchronous to semi-synchronous to asynchronous, rigid and non-rigid, with preset or arbitrary initial configuration. In particular, we show that three colors are sufficient in the non-rigid asynchronous model with arbitrary initial configuration. In contrast, two colors are insufficient in the rigid asynchronous model with arbitrary initial configuration and in the non-rigid asynchronous model with preset initial configuration. Additionally, if the robots are able to distinguish between zero and non-zero distances, we show how they can solve rendezvous and detect termination using only three colors, even in the non-rigid asynchronous model with arbitrary initial configuration.