OpenRaiser/Intern-Atlas huggingface dataset:
Making a Science of Model Search
Venue: arXiv cs.CV 2012
Year: 2012

Many computer vision algorithms depend on a variety of parameter choices and settings that are typically hand-tuned in the course of evaluating the algorithm. While such parameter tuning is often presented as being incidental to the algorithm, correctly setting these parameter choices is frequently critical to evaluating a method's full potential. Compounding matters, these parameters often must be re-tuned when the algorithm is applied to a new problem domain, and the tuning process itself often depends on personal experience and intuition in ways that are hard to describe. Since the performance of a given technique depends on both the fundamental quality of the algorithm and the details of its tuning, it can be difficult to determine whether a given technique is genuinely better, or simply better tuned. In this work, we propose a meta-modeling approach to support automated hyper parameter optimization, with the goal of providing practical tools to replace hand-tuning with a reproducible and unbiased optimization process. Our approach is to expose the underlying expression graph of how a performance metric (e.g. classification accuracy on validation examples) is computed from parameters that govern not only how individual processing steps are applied, but even which processing steps are included. A hyper parameter optimization algorithm transforms this graph into a program for optimizing that performance metric. Our approach yields state of the art results on three disparate computer vision problems: a face-matching verification task (LFW), a face identification task (PubFig83) and an object recognition task (CIFAR-10), using a single algorithm. More broadly, we argue that the formalization of a meta-model supports more objective, reproducible, and quantitative evaluation of computer vision algorithms, and that it can serve as a valuable tool for guiding algorithm development.
On Move Pattern Trends in a Large Go Games Corpus
Venue: arXiv cs.AI 2012
Year: 2012

We process a large corpus of game records of the board game of Go and propose a way of extracting summary information on played moves. We then apply several basic data-mining methods on the summary information to identify the most differentiating features within the summary information, and discuss their correspondence with traditional Go knowledge. We show statistically significant mappings of the features to player attributes such as playing strength or informally perceived "playing style" (e.g. territoriality or aggressivity), describe accurate classifiers for these attributes, and propose applications including seeding real-work ranks of internet players, aiding in Go study and tuning of Go-playing programs, or contribution to Go-theoretical discussion on the scope of "playing style".
Packing identical simple polygons is NP-hard
Venue: arXiv cs.CG 2012
Year: 2012

Given a small polygon S, a big simple polygon B and a positive integer k, it is shown to be NP-hard to determine whether k copies of the small polygon (allowing translation and rotation) can be placed in the big polygon without overlap. Previous NP-hardness results were only known in the case where the big polygon is allowed to be non-simple. A novel reduction from Planar-Circuit-SAT is presented where a small polygon is constructed to encode the entire circuit.
BPRS: Belief Propagation Based Iterative Recommender System
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we introduce the first application of the Belief Propagation (BP) algorithm in the design of recommender systems. We formulate the recommendation problem as an inference problem and aim to compute the marginal probability distributions of the variables which represent the ratings to be predicted. However, computing these marginal probability functions is computationally prohibitive for large-scale systems. Therefore, we utilize the BP algorithm to efficiently compute these functions. Recommendations for each active user are then iteratively computed by probabilistic message passing. As opposed to the previous recommender algorithms, BPRS does not require solving the recommendation problem for all the users if it wishes to update the recommendations for only a single active. Further, BPRS computes the recommendations for each user with linear complexity and without requiring a training period. Via computer simulations (using the 100K MovieLens dataset), we verify that BPRS iteratively reduces the error in the predicted ratings of the users until it converges. Finally, we confirm that BPRS is comparable to the state of art methods such as Correlation-based neighborhood model (CorNgbr) and Singular Value Decomposition (SVD) in terms of rating and precision accuracy. Therefore, we believe that the BP-based recommendation algorithm is a new promising approach which offers a significant advantage on scalability while providing competitive accuracy for the recommender systems.
Mobile Location Update using Distance Method
Venue: arXiv cs.NI 2012
Year: 2012

General Packet Radio Service (GPRS) is a complex data network which upgrades current second generation GSM networks, offering true high-speed internet (IP) and network connectivity over existing GSM cellular networks. The increasing population of mobile users leads to congestion problems in these systems, and motivates the development of more efficient management schemes. This project deals with radio resource and mobility management such as location management and handoff management using distance method in GPRS networks. A simulator based on MATLAB which can study the location updating is used in this GPRS system.
KIMAP: Key-Insulated Mutual Authentication Protocol for RFID
Venue: arXiv cs.CR 2012
Year: 2012

RFID tags are heavily constrained in computational and storage capabilities, and raise numerous privacy concerns in everyday life due to their vulnerability to different attacks. Both forward security and backward security are required to maintain the privacy of a tag i.e., exposure of a tag's secret key should not reveal the past or future secret keys of the tag. We envisage the need for a formal model for backward security for RFID protocol designs in shared key settings, since the RFID tags are too resource-constrained to support public key settings. However, there has not been much research on backward security for shared key environment since Serge Vaudenay in his Asiacrypt 2007 paper showed that perfect backward security is impossible to achieve without public key settings. We propose a Key-Insulated Mutual Authentication Protocol for shared key environment, KIMAP, which minimizes the damage caused by secret key exposure using insulated keys. Even if a tag's secret key is exposed during an authentication session, forward security and `restricted' backward security of the tag are preserved under our assumptions. The notion of `restricted' backward security is that the adversary misses the protocol transcripts which are needed to update the compromised secret key. Although our definition does not capture perfect backward security, it is still suitable for effective implementation as the tags are highly mobile in practice. We also provide a formal security model of KIMAP. Our scheme is more efficient than previous proposals from the viewpoint of computational requirements.
SART: Speeding up Query Processing in Sensor Networks with an Autonomous Range Tree Structure
Venue: arXiv cs.DC 2012
Year: 2012

We consider the problem of constructing efficient P2P overlays for sensornets providing "Energy-Level Application and Services". The method presented in \cite{SOPXM09} presents a novel P2P overlay for Energy Level discovery in a sensornet. However, this solution is not dynamic, since requires periodical restructuring. In particular, it is not able to support neither join of sensor\_nodes with energy level out of the ranges supported by the existing p2p overlay nor leave of \emph{empty} overlay\_peers to which no sensor\_nodes are currently associated. On this purpose and based on the efficient P2P method presented in \cite{SPSTMT10}, we design a dynamic P2P overlay for Energy Level discovery in a sensornet, the so-called SART (Sensors' Autonomous Range Tree). The adaptation of the P2P index presented in \cite{SPSTMT10} guarantees the best-known dynamic query performance of the above operation. We experimentally verify this performance, via the D-P2P-Sim simulator (D-P2P-Sim is publicly available at http://code.google.com/p/d-p2p-sim/).
Automatic Electric Meter Reading System: A Cost-Feasible Alternative Approach In Meter Reading For Bangladesh Perspective Using Low-Cost Digital Wattmeter And Wimax Technology
Venue: arXiv cs.OH 2012
Year: 2012

Energy meter reading is a monotonous and an expensive task. Now the meter reader people goes to each meter and take the meter reading manually to issue the bill which will later be entered in the billing software for billing and payment automation. If the manual meter reading and bill data entry process can be automated then it would reduced the laborious task and financial wastage. "Automatic Electric Meter Reading (AMR) System" is a metering system that is to be used for data collecting from the meter and processing the collected data for billing and other decision purposes. In this paper we have proposed an automatic meter reading system which is low cost, high performance, highest data rate, highest coverage area and most appropriate for Bangladesh perspective. In this AMR system there are four basic units. They are reading unit, communication unit, data receiving and processing unit and billing system. For reading unit we identified the disk rotation of the energy meter and stored the data in microcontroller. So it is not required to change the current analog energy meter. An external module will be added with the current energy meter. In the communication unit Wimax transceiver was used for wireless communication between meter end and the server end because of its wide coverage area. In the data receiving and processing unit meter reading will be collected from the transceiver which is controlled by another microcontroller. There will be a computer application that will take the data from the microcontroller. This will also help to avoid any tampering or break down of energy meter. There are various AMR system exists all over the world. Those systems were analyzed and we found they are not feasible for Bangladesh.
Relation matroid and its relationship with generalized rough set based on relation
Venue: arXiv cs.AI 2012
Year: 2012

Recently, the relationship between matroids and generalized rough sets based on relations has been studied from the viewpoint of linear independence of matrices. In this paper, we reveal more relationships by the predecessor and successor neighborhoods from relations. First, through these two neighborhoods, we propose a pair of matroids, namely predecessor relation matroid and successor relation matroid, respectively. Basic characteristics of this pair of matroids, such as dependent sets, circuits, the rank function and the closure operator, are described by the predecessor and successor neighborhoods from relations. Second, we induce a relation from a matroid through the circuits of the matroid. We prove that the induced relation is always an equivalence relation. With these two inductions, a relation induces a relation matroid, and the relation matroid induces an equivalence relation, then the connection between the original relation and the induced equivalence relation is studied. Moreover, the relationships between the upper approximation operator in generalized rough sets and the closure operator in matroids are investigated.
Matroidal structure of generalized rough sets based on symmetric and transitive relations
Venue: arXiv cs.AI 2012
Year: 2012

Rough sets are efficient for data pre-process in data mining. Lower and upper approximations are two core concepts of rough sets. This paper studies generalized rough sets based on symmetric and transitive relations from the operator-oriented view by matroidal approaches. We firstly construct a matroidal structure of generalized rough sets based on symmetric and transitive relations, and provide an approach to study the matroid induced by a symmetric and transitive relation. Secondly, this paper establishes a close relationship between matroids and generalized rough sets. Approximation quality and roughness of generalized rough sets can be computed by the circuit of matroid theory. At last, a symmetric and transitive relation can be constructed by a matroid with some special properties.
Supervised Blockmodelling
Venue: arXiv cs.LG 2012
Year: 2012

Collective classification models attempt to improve classification performance by taking into account the class labels of related instances. However, they tend not to learn patterns of interactions between classes and/or make the assumption that instances of the same class link to each other (assortativity assumption). Blockmodels provide a solution to these issues, being capable of modelling assortative and disassortative interactions, and learning the pattern of interactions in the form of a summary network. The Supervised Blockmodel provides good classification performance using link structure alone, whilst simultaneously providing an interpretable summary of network interactions to allow a better understanding of the data. This work explores three variants of supervised blockmodels of varying complexity and tests them on four structurally different real world networks.
Feasible Sampling of Non-strict Turnstile Data Streams
Venue: arXiv cs.DS 2012
Year: 2012

We present the first feasible method for sampling a dynamic data stream with deletions, where the sample consists of pairs $(k,C_k)$ of a value $k$ and its exact total count $C_k$. Our algorithms are for both Strict Turnstile data streams and the most general Non-strict Turnstile data streams, where each element may have a negative total count. Our method improves by an order of magnitude the known processing time of each element in the stream, which is extremely crucial for data stream applications. For example, for a sample of size $O(ε^{-2} \log{(1/δ)})$ in Non-strict streams, our solution requires $O((\log\log(1/ε))^2 + (\log\log(1/δ)) ^ 2)$ operations per stream element, whereas the best previous solution requires $O(ε^{-2} \log^2(1/δ))$ evaluations of a fully independent hash function per element. Here $1-δ$ is the success probability and $ε$ is the additive approximation error. We achieve this improvement by constructing a single data structure from which multiple elements can be extracted with very high success probability. The sample we generate is useful for calculating both forward and inverse distribution statistics, within an additive error, with provable guarantees on the success probability. Furthermore, our algorithms can run on distributed systems and extract statistics on the union or difference between data streams. They can be used to calculate the Jaccard similarity coefficient as well.
Lattice structures of fixed points of the lower approximations of two types of covering-based rough sets
Venue: arXiv cs.AI 2012
Year: 2012

Covering is a common type of data structure and covering-based rough set theory is an efficient tool to process this data. Lattice is an important algebraic structure and used extensively in investigating some types of generalized rough sets. In this paper, we propose two family of sets and study the conditions that these two sets become some lattice structures. These two sets are consisted by the fixed point of the lower approximations of the first type and the sixth type of covering-based rough sets, respectively. These two sets are called the fixed point set of neighborhoods and the fixed point set of covering, respectively. First, for any covering, the fixed point set of neighborhoods is a complete and distributive lattice, at the same time, it is also a double p-algebra. Especially, when the neighborhood forms a partition of the universe, the fixed point set of neighborhoods is both a boolean lattice and a double Stone algebra. Second, for any covering, the fixed point set of covering is a complete lattice.When the covering is unary, the fixed point set of covering becomes a distributive lattice and a double p-algebra. a distributive lattice and a double p-algebra when the covering is unary. Especially, when the reduction of the covering forms a partition of the universe, the fixed point set of covering is both a boolean lattice and a double Stone algebra.
Faster Deterministic Fully-Dynamic Graph Connectivity
Venue: arXiv cs.DS 2012
Year: 2012

We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in $O(\log^2n/\log\log n)$ amortized time and connectivity queries in $O(\log n/\log\log n)$ worst-case time, where $n$ is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J.ACM 2001) and Thorup (STOC 2000) which both have $O(\log^2n)$ amortized update time and $O(\log n/\log\log n)$ worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard $AC^0$ instructions.
Pros & Cons of Model-based Bandwidth Control for Client-assisted Content Delivery
Venue: arXiv cs.NI 2012
Year: 2012

A key challenge in \cacd\ is determining how to allocate limited server bandwidth across a large number of files being concurrently served so as to optimize global performance and cost objectives. In this paper, we present a comprehensive experimental evaluation of strategies to control server bandwidth allocation. As part of this effort, we introduce a new {\em model-based} control approach that relies on an accurate yet concise "cheat sheet" based on a priori offline measurement to predict swarm performance as a function of the server bandwidth and other swarm parameters. Our evaluation using a prototype system, \cs, instantiating static, dynamic, and model-based controllers shows that static and dynamic controllers can both be suboptimal due to different reasons. In comparison, a model-based approach consistently outperforms both static and dynamic approaches provided it has access to detailed measurements in the regime of interest. Nevertheless, the broad applicability of a model-based approach may be limited in practice because of the overhead of developing and maintaining a comprehensive measurement-based model of swarm performance in each regime of interest.
Nonbinary Spatially-Coupled LDPC Codes on the Binary Erasure Channel
Venue: arXiv cs.IT 2012
Year: 2012

We analyze the asymptotic performance of nonbinary spatially-coupled low-density parity-check (SC-LDPC) codes built on the general linear group, when the transmission takes place over the binary erasure channel. We propose an efficient method to derive an upper bound to the maximum a posteriori probability (MAP) threshold for nonbinary LDPC codes, and observe that the MAP performance of regular LDPC codes improves with the alphabet size. We then consider nonbinary SC-LDPC codes. We show that the same threshold saturation effect experienced by binary SC-LDPC codes occurs for the nonbinary codes, hence we conjecture that the BP threshold for large termination length approaches the MAP threshold of the underlying regular ensemble.
Cognitive Radio Simultaneous Spectrum Access/ One-shot Game Modelling
Venue: arXiv cs.GT 2012
Year: 2012

The aim of this work is to asses simultaneous spectrum access situations that may occur in Cognitive Radio (CR) environments. The approach is that of one shot, noncooperative games describing CR interactions. Open spectrum access scenarios are modelled based on continuous and discrete reformulations of the Cournot game theoretical model. CR interaction situations are described by Nash and Pareto equilibria. Also, the heterogeneity of players is captured by the new concept of joint Nash-Pareto equilibrium, allowing CRs to be biased toward different types of equilibrium. Numerical simulations reveal equilibrium situations that may be reached in simultaneous access scenarios of two and three users.
Lessons Learned from Evaluating MDE Abstractions in an Industry Case Study
Venue: arXiv cs.SE 2012
Year: 2012

In a recent empirical study we found that evaluating abstractions of Model-Driven Engineering (MDE) is not as straight forward as it might seem. In this paper, we report on the challenges that we as researchers faced when we conducted the aforementioned field study. In our study we found that modeling happens within a complex ecosystem of different people working in different roles. An empirical evaluation should thus mind the ecosystem, that is, focus on both technical and human factors. In the following, we present and discuss five lessons learnt from our recent work.
A polynomial time λ-calculus with multithreading and side effects
Venue: arXiv cs.PL 2012
Year: 2012

The framework of Light Logics has been extensively studied to control the complexity of higher-order functional programs. We propose an extension of this framework to multithreaded programs with side effects, focusing on the case of polynomial time. After introducing a modal λ-calculus with parallel composition and regions, we prove that a realistic call-by-value evaluation strategy can be computed in polynomial time for a class of well-formed programs. The result relies on the simulation of call-by-value by a polynomial shallow-first strategy which preserves the evaluation order of side effects. Then, we provide a polynomial type system that guarantees that well-typed programs do not go wrong. Finally, we illustrate the expressivity of the type system by giving a programming example of concurrent iteration producing side effects over an inductive data structure.
Efficient Natural Evolution Strategies
Venue: arXiv cs.AI 2012
Year: 2012

Efficient Natural Evolution Strategies (eNES) is a novel alternative to conventional evolutionary algorithms, using the natural gradient to adapt the mutation distribution. Unlike previous methods based on natural gradients, eNES uses a fast algorithm to calculate the inverse of the exact Fisher information matrix, thus increasing both robustness and performance of its evolution gradient estimation, even in higher dimensions. Additional novel aspects of eNES include optimal fitness baselines and importance mixing (a procedure for updating the population with very few fitness evaluations). The algorithm yields competitive results on both unimodal and multimodal benchmarks.
Subset Selection for Gaussian Markov Random Fields
Venue: arXiv cs.LG 2012
Year: 2012

Given a Gaussian Markov random field, we consider the problem of selecting a subset of variables to observe which minimizes the total expected squared prediction error of the unobserved variables. We first show that finding an exact solution is NP-hard even for a restricted class of Gaussian Markov random fields, called Gaussian free fields, which arise in semi-supervised learning and computer vision. We then give a simple greedy approximation algorithm for Gaussian free fields on arbitrary graphs. Finally, we give a message passing algorithm for general Gaussian Markov random fields on bounded tree-width graphs.