OpenRaiser/Intern-Atlas huggingface dataset:
Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent
Venue: arXiv cs.LG 2011
Year: 2011

For large scale learning problems, it is desirable if we can obtain the optimal model parameters by going through the data in only one pass. Polyak and Juditsky (1992) showed that asymptotically the test performance of the simple average of the parameters obtained by stochastic gradient descent (SGD) is as good as that of the parameters which minimize the empirical cost. However, to our knowledge, despite its optimal asymptotic convergence rate, averaged SGD (ASGD) received little attention in recent research on large scale learning. One possible reason is that it may take a prohibitively large number of training samples for ASGD to reach its asymptotic region for most real problems. In this paper, we present a finite sample analysis for the method of Polyak and Juditsky (1992). Our analysis shows that it indeed usually takes a huge number of samples for ASGD to reach its asymptotic region for improperly chosen learning rate. More importantly, based on our analysis, we propose a simple way to properly set learning rate so that it takes a reasonable amount of data for ASGD to reach its asymptotic region. We compare ASGD using our proposed learning rate with other well known algorithms for training large scale linear classifiers. The experiments clearly show the superiority of ASGD.
Learning Hypergraph Labeling for Feature Matching
Venue: arXiv cs.CV 2011
Year: 2011

This study poses the feature correspondence problem as a hypergraph node labeling problem. Candidate feature matches and their subsets (usually of size larger than two) are considered to be the nodes and hyperedges of a hypergraph. A hypergraph labeling algorithm, which models the subset-wise interaction by an undirected graphical model, is applied to label the nodes (feature correspondences) as correct or incorrect. We describe a method to learn the cost function of this labeling algorithm from labeled examples using a graphical model training algorithm. The proposed feature matching algorithm is different from the most of the existing learning point matching methods in terms of the form of the objective function, the cost function to be learned and the optimization method applied to minimize it. The results on standard datasets demonstrate how learning over a hypergraph improves the matching performance over existing algorithms, notably one that also uses higher order information without learning.
An IDE to Build and Check Task Flow Models
Venue: arXiv cs.SE 2011
Year: 2011

This paper presents the Eclipse plug-ins for the Task Flow model in the Discovery Method. These plug-ins provide an IDE for the Task Algebra compiler and the model-checking tools. The Task Algebra is the formal representation for the Task Model and it is based on simple and compound tasks. The model-checking techniques were developed to validate Task Models represented in the algebra.
Second moment method for a family of boolean CSP
Venue: arXiv cs.DM 2011
Year: 2011

The estimation of phase transitions in random boolean Constraint Satisfaction Problems (CSP) is based on two fundamental tools: the first and second moment methods. While the first moment method on the number of solutions permits to compute upper bounds on any boolean CSP, the second moment method used for computing lower bounds proves to be more tricky and in most cases gives only the trivial lower bound 0. In this paper, we define a subclass of boolean CSP covering the monotone versions of many known NP-Complete boolean CSPs. We give a method for computing non trivial lower bounds for any member of this subclass. This is achieved thanks to an application of the second moment method to some selected solutions called characteristic solutions that depend on the boolean CSP considered. We apply this method with a finer analysis to establish that the threshold $r_{k}$ (ratio : #constrains/#variables) of monotone 1-in-k-SAT is $\log k/k\leq r_{k}\leq\log^{2}k/k$.
Label-Specific Training Set Construction from Web Resource for Image Annotation
Venue: arXiv cs.MM 2011
Year: 2011

Recently many research efforts have been devoted to image annotation by leveraging on the associated tags/keywords of web images as training labels. A key issue to resolve is the relatively low accuracy of the tags. In this paper, we propose a novel semi-automatic framework to construct a more accurate and effective training set from these web media resources for each label that we want to learn. Experiments conducted on a real-world dataset demonstrate that the constructed training set can result in higher accuracy for image annotation.
Geometric Packing under Non-uniform Constraints
Venue: arXiv cs.CG 2011
Year: 2011

We study the problem of discrete geometric packing. Here, given weighted regions (say in the plane) and points (with capacities), one has to pick a maximum weight subset of the regions such that no point is covered more than its capacity. We provide a general framework and an algorithm for approximating the optimal solution for packing in hypergraphs arising out of such geometric settings. Using this framework we get a flotilla of results on this problem (and also on its dual, where one wants to pick a maximum weight subset of the points when the regions have capacities). For example, for the case of fat triangles of similar size, we show an O(1)-approximation and prove that no \PTAS is possible.
An MCMC Approach to Universal Lossy Compression of Analog Sources
Venue: arXiv cs.IT 2011
Year: 2011

Motivated by the Markov chain Monte Carlo (MCMC) approach to the compression of discrete sources developed by Jalali and Weissman, we propose a lossy compression algorithm for analog sources that relies on a finite reproduction alphabet, which grows with the input length. The algorithm achieves, in an appropriate asymptotic sense, the optimum Shannon theoretic tradeoff between rate and distortion, universally for stationary ergodic continuous amplitude sources. We further propose an MCMC-based algorithm that resorts to a reduced reproduction alphabet when such reduction does not prevent achieving the Shannon limit. The latter algorithm is advantageous due to its reduced complexity and improved rates of convergence when employed on sources with a finite and small optimum reproduction alphabet.
Facial Expression Classification Based on Multi Artificial Neural Network and Two Dimensional Principal Component Analysis
Venue: arXiv cs.CV 2011
Year: 2011

Facial expression classification is a kind of image classification and it has received much attention, in recent years. There are many approaches to solve these problems with aiming to increase efficient classification. One of famous suggestions is described as first step, project image to different spaces; second step, in each of these spaces, images are classified into responsive class and the last step, combine the above classified results into the final result. The advantages of this approach are to reflect fulfill and multiform of image classified. In this paper, we use 2D-PCA and its variants to project the pattern or image into different spaces with different grouping strategies. Then we develop a model which combines many Neural Networks applied for the last step. This model evaluates the reliability of each space and gives the final classification conclusion. Our model links many Neural Networks together, so we call it Multi Artificial Neural Network (MANN). We apply our proposal model for 6 basic facial expressions on JAFFE database consisting 213 images posed by 10 Japanese female models.
Quantum information approach to normal representation of extensive games
Venue: arXiv cs.GT 2011
Year: 2011

We modify the concept of quantum strategic game to make it useful for extensive form games. We prove that our modification allows to consider the normal representation of any finite extensive game using the fundamental concepts of quantum information. The Selten's Horse game and the general form of two-stage extensive game with perfect information are studied to illustrate a potential application of our idea. In both examples we use Eisert-Wilkens-Lewenstein approach as well as Marinatto-Weber approach to quantization of games.
Real-time retrieval for case-based reasoning in interactive multiagent-based simulations
Venue: arXiv cs.AI 2011
Year: 2011

The aim of this paper is to present the principles and results about case-based reasoning adapted to real- time interactive simulations, more precisely concerning retrieval mechanisms. The article begins by introducing the constraints involved in interactive multiagent-based simulations. The second section pre- sents a framework stemming from case-based reasoning by autonomous agents. Each agent uses a case base of local situations and, from this base, it can choose an action in order to interact with other auton- omous agents or users' avatars. We illustrate this framework with an example dedicated to the study of dynamic situations in football. We then go on to address the difficulties of conducting such simulations in real-time and propose a model for case and for case base. Using generic agents and adequate case base structure associated with a dedicated recall algorithm, we improve retrieval performance under time pressure compared to classic CBR techniques. We present some results relating to the performance of this solution. The article concludes by outlining future development of our project.
Arithmetic and Frequency Filtering Methods of Pixel-Based Image Fusion Techniques
Venue: arXiv cs.CV 2011
Year: 2011

In remote sensing, image fusion technique is a useful tool used to fuse high spatial resolution panchromatic images (PAN) with lower spatial resolution multispectral images (MS) to create a high spatial resolution multispectral of image fusion (F) while preserving the spectral information in the multispectral image (MS).There are many PAN sharpening techniques or Pixel-Based image fusion techniques that have been developed to try to enhance the spatial resolution and the spectral property preservation of the MS. This paper attempts to undertake the study of image fusion, by using two types of pixel-based image fusion techniques i.e. Arithmetic Combination and Frequency Filtering Methods of Pixel-Based Image Fusion Techniques. The first type includes Brovey Transform (BT), Color Normalized Transformation (CN) and Multiplicative Method (MLT). The second type include High-Pass Filter Additive Method (HPFA), High-Frequency-Addition Method (HFA) High Frequency Modulation Method (HFM) and The Wavelet transform-based fusion method (WT). This paper also devotes to concentrate on the analytical techniques for evaluating the quality of image fusion (F) by using various methods including Standard Deviation (SD), Entropy(En), Correlation Coefficient (CC), Signal-to Noise Ratio (SNR), Normalization Root Mean Square Error (NRMSE) and Deviation Index (DI) to estimate the quality and degree of information improvement of a fused image quantitatively.
Snake-in-the-Box Codes for Rank Modulation
Venue: arXiv cs.IT 2011
Year: 2011

Motivated by the rank-modulation scheme with applications to flash memory, we consider Gray codes capable of detecting a single error, also known as snake-in-the-box codes. We study two error metrics: Kendall's $τ$-metric, which applies to charge-constrained errors, and the $\ell_\infty$-metric, which is useful in the case of limited magnitude errors. In both cases we construct snake-in-the-box codes with rate asymptotically tending to 1. We also provide efficient successor-calculation functions, as well as ranking and unranking functions. Finally, we also study bounds on the parameters of such codes.
Evaluation of servo, geometric and dynamic error sources on five axis high-speed machine tool
Venue: arXiv cs.OH 2011
Year: 2011

Many sources of errors exist in the manufacturing process of complex shapes. Some approximations occur at each step from the design geometry to the machined part. The aim of the paper is to present a method to evaluate the effect of high speed and high dynamic load on volumetric errors at the tool center point. The interpolator output signals and the machine encoder signals are recorded and compared to evaluate the contouring errors resulting from each axis follow-up error. The machine encoder signals are also compared to the actual tool center point position as recorded with a non-contact measuring instrument called CapBall to evaluate the total geometric errors. The novelty of the work lies in the method that is proposed to decompose the geometric errors in two categories: the quasi-static geometric errors independent from the speed of the trajectory and the dynamic geometric errors, dependent on the programmed feed rate and resulting from the machine structure deflection during the acceleration of its axes. The evolution of the respective contributions for contouring errors, quasi-static geometric errors and dynamic geomet- ric errors is experimentally evaluated and a relation between programmed feed rate and dynamic errors is highlighted.
QoS Routing and Performance Evaluation for Mobile Ad Hoc Networks using OLSR Protocol
Venue: arXiv cs.NI 2011
Year: 2011

Mobile Ad-Hoc network is a collection of mobile nodes in communication without using infrastructure. As the real-time applications used in today's wireless network grow, we need some schemes to provide more suitable service for them. We know that most of actual schemes do not perform well on traffic which is not strictly CBR. Therefore, in this paper we have studied the impact, respectively, of mobility models and the density of nodes on the performances (End-to-End Delay, Throughput and Packet Delivery ratio) of routing protocol (Optimized Link State Routing) OLSR by using in the first a real-time VBR (MPEG-4) and secondly the Constant Bit Rate (CBR) traffic. Finally we compare the performance on both cases. Experimentally, we considered the three mobility models as follows Random Waypoint, Random Direction and Mobgen Steady State. The experimental results illustrate that the behavior of OLSR change according to the model and the used traffics.
On the approximation in the smoothed finite element method (SFEM)
Venue: arXiv cs.NA 2011
Year: 2011

This letter aims at resolving the issues raised in the recent short communication [1] and answered by [2] by proposing a systematic approximation scheme based on non-mapped shape functions, which both allows to fully exploit the unique advantages of the smoothed finite element method (SFEM) [3, 4, 5, 6, 7, 8, 9] and resolve the existence, linearity and positivity deficiencies pointed out in [1]. We show that Wachspress interpolants [10] computed in the physical coordinate system are very well suited to the SFEM, especially when elements are heavily distorted (obtuse interior angles). The proposed approximation leads to results which are almost identical to those of the SFEM initially proposed in [3]. These results that the proposed approximation scheme forms a strong and rigorous basis for construction of smoothed finite element methods.
An Analysis of Chinese Search Engine Filtering
Venue: arXiv cs.CR 2011
Year: 2011

The imposition of government mandates upon Internet search engine operation is a growing area of interest for both computer science and public policy. Users of these search engines often observe evidence of censorship, but the government policies that impose this censorship are not generally public. To better understand these policies, we conducted a set of experiments on major search engines employed by Internet users in China, issuing queries against a variety of different words: some neutral, some with names of important people, some political, and some pornographic. We conducted these queries, in Chinese, against Baidu, Google (including google.cn, before it was terminated), Yahoo!, and Bing. We found remarkably aggressive filtering of pornographic terms, in some cases causing non-pornographic terms which use common characters to also be filtered. We also found that names of prominent activists and organizers as well as top political and military leaders, were also filtered in whole or in part. In some cases, we found search terms which we believe to be "blacklisted". In these cases, the only results that appeared, for any of them, came from a short "whitelist" of sites owned or controlled directly by the Chinese government. By repeating observations over a long observation period, we also found that the keyword blocking policies of the Great Firewall of China vary over time. While our results don't offer any fundamental insight into how to defeat or work around Chinese internet censorship, they are still helpful to understand the structure of how censorship duties are shared between the Great Firewall and Chinese search engines.
Achieving a vanishing SNR-gap to exact lattice decoding at a subexponential complexity
Venue: arXiv cs.IT 2011
Year: 2011

The work identifies the first lattice decoding solution that achieves, in the general outage-limited MIMO setting and in the high-rate and high-SNR limit, both a vanishing gap to the error-performance of the (DMT optimal) exact solution of preprocessed lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits. The proposed solution employs lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. These performance and complexity guarantees hold for most MIMO scenarios, all reasonable fading statistics, all channel dimensions and all full-rate lattice codes. In sharp contrast to the above manageable complexity, the complexity of other standard preprocessed lattice decoding solutions is shown here to be extremely high. Specifically the work is first to quantify the complexity of these lattice (sphere) decoding solutions and to prove the surprising result that the complexity required to achieve a certain rate-reliability performance, is exponential in the lattice dimensionality and in the number of codeword bits, and it in fact matches, in common scenarios, the complexity of ML-based solutions. Through this sharp contrast, the work was able to, for the first time, rigorously quantify the pivotal role of lattice reduction as a special complexity reducing ingredient. Finally the work analytically refines transceiver DMT analysis which generally fails to address potentially massive gaps between theory and practice. Instead the adopted vanishing gap condition guarantees that the decoder's error curve is arbitrarily close, given a sufficiently high SNR, to the optimal error curve of exact solutions, which is a much stronger condition than DMT optimality which only guarantees an error gap that is subpolynomial in SNR, and can thus be unbounded and generally unacceptable in practical settings.
Data Aggregation and Privacy for Police Patrols
Venue: arXiv cs.CR 2011
Year: 2011

With a widespread growth in the potential applications of Wireless Sensor Networks, the need for reliable security mechanisms for them has increased manifold. This paper proposes a scheme, Privacy for Police Patrols (PPP), to provide secure data aggregation that relies on multilevel routing. Privacy factors have been identified and implemented. Aggregates are prepared and the summary of information is gathered and stored in a repository. The above defined approaches are integrated in police patrol applications and preliminary results are obtained.
Is Cloud Computing Steganography-proof?
Venue: arXiv cs.CR 2011
Year: 2011

The paper focuses on characterisation of information hiding possibilities in Cloud Computing. After general introduction to cloud computing and its security we move to brief description of steganography. In particular we introduce classification of steganographic communication scenarios in cloud computing which is based on location of the steganograms receiver. These scenarios as well as the threats that steganographic methods can cause must be taken into account when designing secure cloud computing services.
The settlement of Madagascar: what dialects and languages can tell
Venue: arXiv cs.CL 2011
Year: 2011

The dialects of Madagascar belong to the Greater Barito East group of the Austronesian family and it is widely accepted that the Island was colonized by Indonesian sailors after a maritime trek which probably took place around 650 CE. The language most closely related to Malagasy dialects is Maanyan but also Malay is strongly related especially for what concerns navigation terms. Since the Maanyan Dayaks live along the Barito river in Kalimantan (Borneo) and they do not possess the necessary skill for long maritime navigation, probably they were brought as subordinates by Malay sailors. In a recent paper we compared 23 different Malagasy dialects in order to determine the time and the landing area of the first colonization. In this research we use new data and new methods to confirm that the landing took place on the south-east coast of the Island. Furthermore, we are able to state here that it is unlikely that there were multiple settlements and, therefore, colonization consisted in a single founding event. To reach our goal we find out the internal kinship relations among all the 23 Malagasy dialects and we also find out the different kinship degrees of the 23 dialects versus Malay and Maanyan. The method used is an automated version of the lexicostatistic approach. The data concerning Madagascar were collected by the author at the beginning of 2010 and consist of Swadesh lists of 200 items for 23 dialects covering all areas of the Island. The lists for Maanyan and Malay were obtained from published datasets integrated by author's interviews.
Effective Capacity of Two-Hop Wireless Communication Systems
Venue: arXiv cs.IT 2011
Year: 2011

A two-hop wireless communication link in which a source sends data to a destination with the aid of an intermediate relay node is studied. It is assumed that there is no direct link between the source and the destination, and the relay forwards the information to the destination by employing the decode-and-forward scheme. Both the source and intermediate relay nodes are assumed to operate under statistical quality of service (QoS) constraints imposed as limitations on the buffer overflow probabilities. The maximum constant arrival rates that can be supported by this two-hop link in the presence of QoS constraints are characterized by determining the effective capacity of such links as a function of the QoS parameters and signal-to-noise ratios at the source and relay, and the fading distributions of the links. The analysis is performed for both full-duplex and half-duplex relaying. Through this study, the impact upon the throughput of having buffer constraints at the source and intermediate relay nodes is identified. The interactions between the buffer constraints in different nodes and how they affect the performance are studied. The optimal time-sharing parameter in half-duplex relaying is determined, and performance with half-duplex relaying is investigated.