OpenRaiser/Intern-Atlas huggingface dataset:
Escaping Prisoner's Dilemmas: From Discord to Harmony in the Landscape of 2x2 Games
Venue: arXiv cs.GT 2012
Year: 2012

Changes in payoffs can transform Prisoner's Dilemma and other social dilemmas into harmonious win-win games. Using the Robinson-Goforth topology of 2x2 games, this paper analyzes how payoff swaps turn Prisoner's Dilemma into other games, compares Prisoner's Dilemmas with other families of games, traces paths that affect the difficulty of transforming Prisoner's Dilemma and other social dilemmas into win-win games, and shows how ties connect simpler and more complex games. Charts illustrate the relationships between the 144 strict ordinal 2x2 games, the 38 symmetric 2x2 ordinal games with and without ties, and the complete set of 1,413 2x2 ordinal games. Payoffs from the symmetric ordinal 2x2 games combine to form asymmetric games, generating coordinates for a simple labeling scheme to uniquely identify and locate all asymmetric ordinal 2x2 games. The expanded topology elegantly maps relationships between 2x2 games with and without ties, enables a systematic understanding of the potential for transformations in social dilemmas and other strategic interactions, offers a tool for institutional analysis and design, and locates a variety of interesting games for further research.
Improvement of Loadability in Distribution System Using Genetic Algorithm
Venue: arXiv cs.SY 2012
Year: 2012

Generally during recent decades due to development of power systems, the methods for delivering electrical energy to consumers, and because of voltage variations is a very important problem, the power plants follow this criteria. The good solution for improving transfer and distribution of electrical power the majority of consumers prefer to use energy near the loads .So small units that are connected to distribution system named "Decentralized Generation" or "Dispersed Generation". Deregulated in power industry and development of renewable energies are the most important factors in developing this type of electricity generation. Today DG has a key role in electrical distribution systems. For example we can refer to improving reliability indices, improvement of stability and reduction of losses in power system. One of the key problems in using DG's, is allocation of these sources in distribution networks. Load ability in distribution systems and its improvement has an effective role in the operation of power systems. However, placement of distributed generation sources in order to improve the distribution system load ability index was not considered, we show DG placement and allocation with genetic algorithm optimization method maximize load ability of power systems .This method implemented on the IEEE Standard bench marks. The results show the effectiveness of the proposed algorithm .Another benefits of DG in selected positions are also studied and compared.
An Empirical Study of the Repair Performance of Novel Coding Schemes for Networked Distributed Storage Systems
Venue: arXiv cs.DC 2012
Year: 2012

Erasure coding techniques are getting integrated in networked distributed storage systems as a way to provide fault-tolerance at the cost of less storage overhead than traditional replication. Redundancy is maintained over time through repair mechanisms, which may entail large network resource overheads. In recent years, several novel codes tailor-made for distributed storage have been proposed to optimize storage overhead and repair, such as Regenerating Codes that minimize the per repair traffic, or Self-Repairing Codes which minimize the number of nodes contacted per repair. Existing studies of these coding techniques are however predominantly theoretical, under the simplifying assumption that only one object is stored. They ignore many practical issues that real systems must address, such as data placement, de/correlation of multiple stored objects, or the competition for limited network resources when multiple objects are repaired simultaneously. This paper empirically studies the repair performance of these novel storage centric codes with respect to classical erasure codes by simulating realistic scenarios and exploring the interplay of code parameters, failure characteristics and data placement with respect to the trade-offs of bandwidth usage and speed of repairs.
Communication-Efficient Parallel Belief Propagation for Latent Dirichlet Allocation
Venue: arXiv cs.LG 2012
Year: 2012

This paper presents a novel communication-efficient parallel belief propagation (CE-PBP) algorithm for training latent Dirichlet allocation (LDA). Based on the synchronous belief propagation (BP) algorithm, we first develop a parallel belief propagation (PBP) algorithm on the parallel architecture. Because the extensive communication delay often causes a low efficiency of parallel topic modeling, we further use Zipf's law to reduce the total communication cost in PBP. Extensive experiments on different data sets demonstrate that CE-PBP achieves a higher topic modeling accuracy and reduces more than 80% communication cost than the state-of-the-art parallel Gibbs sampling (PGS) algorithm.
Complex Orthogonal Matching Pursuit and Its Exact Recovery Conditions
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we present new results on using orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries for complex cases (i.e., complex measurement vector, complex dictionary and complex additive white Gaussian noise (CAWGN)). A sufficient condition that OMP can recover the optimal representation of an exactly sparse signal in the complex cases is proposed both in noiseless and bound Gaussian noise settings. Similar to exact recovery condition (ERC) results in real cases, we extend them to complex case and derivate the corresponding ERC in the paper. It leverages this theory to show that OMP succeed for k-sparse signal from a class of complex dictionary. Besides, an application with geometrical theory of diffraction (GTD) model is presented for complex cases. Finally, simulation experiments illustrate the validity of the theoretical analysis.
A Fast HRRP Synthesis Algorithm with Sensing Dictionary in GTD Model
Venue: arXiv cs.IT 2012
Year: 2012

To achieve high range resolution profile (HRRP), the geometric theory of diffraction (GTD) parametric model is widely used in stepped-frequency radar system. In the paper, a fast synthetic range profile algorithm, called orthogonal matching pursuit with sensing dictionary (OMP-SD), is proposed. It formulates the traditional HRRP synthetic to be a sparse approximation problem over redundant dictionary. As it employs a priori information that targets are sparsely distributed in the range space, the synthetic range profile (SRP) can be accomplished even in presence of data lost. Besides, the computational complexity is reduced by introducing sensing dictionary (SD) and it mitigates the model mismatch at the same time. The computation complexity decreases from O(MNDK) flops for OMP to O(M(N +D)K) flops for OMP-SD. Simulation experiments illustrate its advantages both in additive white Gaussian noise (AWGN) and noiseless situation, respectively.
A Novel Windowing Technique for Efficient Computation of MFCC for Speaker Recognition
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, we propose a novel family of windowing technique to compute Mel Frequency Cepstral Coefficient (MFCC) for automatic speaker recognition from speech. The proposed method is based on fundamental property of discrete time Fourier transform (DTFT) related to differentiation in frequency domain. Classical windowing scheme such as Hamming window is modified to obtain derivatives of discrete time Fourier transform coefficients. It has been mathematically shown that the slope and phase of power spectrum are inherently incorporated in newly computed cepstrum. Speaker recognition systems based on our proposed family of window functions are shown to attain substantial and consistent performance improvement over baseline single tapered Hamming window as well as recently proposed multitaper windowing technique.
Performance Improvement of Heterogeneous Wireless Networks using Modified Newton Method
Venue: arXiv cs.NI 2012
Year: 2012

The heterogeneous wireless networks where coexistence of different Radio access technology (RAT) are widely deployed for various services and support various traffic demand, channel allocation. Under heterogeneous wireless networks, a user can send data through a single or multi RATs simultaneous. The objective of this paper is to choose the optimal bandwidth for the services and power allocation to that bandwidth. The proposed distributed joint allocation algorithm using modified Newton method is adopted to maximize the total system capacity. We validate the performance of the proposed algorithm through numerical results.
Information theoretic security by the laws of classical physics
Venue: arXiv cs.ET 2012
Year: 2012

It has been shown recently that the use of two pairs of resistors with enhanced Johnson-noise and a Kirchhoff-loop-i.e., a Kirchhoff-Law-Johnson-Noise (KLJN) protocol-for secure key distribution leads to information theoretic security levels superior to those of a quantum key distribution, including a natural immunity against a man-in-the-middle attack. This issue is becoming particularly timely because of the recent full cracks of practical quantum communicators, as shown in numerous peer-reviewed publications. This presentation first briefly surveys the KLJN system and then discusses related, essential questions such as: what are perfect and imperfect security characteristics of key distribution, and how can these two types of securities be unconditional (or information theoretical)? Finally the presentation contains a live demonstration.
Rate Model for Compressed Video Considering Impacts Of Spatial, Temporal and Amplitude Resolutions and Its Applications for Video Coding and Adaptation
Venue: arXiv cs.MM 2012
Year: 2012

In this paper, we investigate the impacts of spatial, temporal and amplitude resolution (STAR) on the bit rate of a compressed video. We propose an analytical rate model in terms of the quantization stepsize, frame size and frame rate. Experimental results reveal that the increase of the video rate as the individual resolution increases follows a power function. Hence, the proposed model expresses the rate as the product of power functions of the quantization stepsize, frame size and frame rate, respectively. The proposed rate model is analytically tractable, requiring only four content dependent parameters. We also propose methods for predicting the model parameters from content features that can be computed from original video. Simulation results show that model predicted rates fit the measured data very well with high Pearson correlation (PC) and small relative root mean square error (RRMSE). The same model function works for different coding scenarios (including scalable and non-scalable video, temporal prediction using either hierarchical B or IPPP structure, etc.) with very high accuracy (average PC $>$ 0.99), but the values of model parameters differ. Using the proposed rate model and the quality model introduced in a separate work, we show how to optimize the STAR for a given rate constraint, which is important for both encoder rate control and scalable video adaptation. Furthermore, we demonstrate how to order the spatial, temporal and amplitude layers of a scalable video in a rate-quality optimized way.
Decomposition of Kolmogorov Complexity And Link To Geometry
Venue: arXiv cs.CC 2012
Year: 2012

A link between Kolmogorov Complexity and geometry is uncovered. A similar concept of projection and vector decomposition is described for Kolmogorov Complexity. By using a simple approximation to the Kolmogorov Complexity, coded in Mathematica, the derived formulas are tested and used to study the geometry of Light Cone.
On Constrained Randomized Quantization
Venue: arXiv cs.IT 2012
Year: 2012

Randomized (dithered) quantization is a method capable of achieving white reconstruction error independent of the source. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization. In this paper we extend conventional dithered quantization to nonuniform quantization, via a subterfage: dithering is performed in the companded domain. Closed form necessary conditions for optimality of the compressor and expander mappings are derived for both fixed and variable rate randomized quantization. Numerically, mappings are optimized by iteratively imposing these necessary conditions. The framework is extended to include an explicit constraint that deterministic or randomized quantizers yield reconstruction error that is uncorrelated with the source. Surprising theoretical results show direct and simple connection between the optimal constrained quantizers and their unconstrained counterparts. Numerical results for the Gaussian source provide strong evidence that the proposed constrained randomized quantizer outperforms the conventional dithered quantizer, as well as the constrained deterministic quantizer. Moreover, the proposed constrained quantizer renders the reconstruction error nearly white. In the second part of the paper, we investigate whether uncorrelated reconstruction error requires random coding to achieve asymptotic optimality. We show that for a Gaussian source, the optimal vector quantizer of asymptotically high dimension whose quantization error is uncorrelated with the source, is indeed random. Thus, random encoding in this setting of rate-distortion theory, is not merely a tool to characterize performance bounds, but a required property of quantizers that approach such bounds.
Study of the Importance of Adequacy to Robot Verbal and Non Verbal Communication in Human-Robot interaction
Venue: arXiv cs.RO 2012
Year: 2012

The Robadom project aims at creating a homecare robot that help and assist people in their daily life, either in doing task for the human or in managing day organization. A robot could have this kind of role only if it is accepted by humans. Before thinking about the robot appearance, we decided to evaluate the importance of the relation between verbal and nonverbal communication during a human-robot interaction in order to determine the situation where the robot is accepted. We realized two experiments in order to study this acceptance. The first experiment studied the importance of having robot nonverbal behavior in relation of its verbal behavior. The second experiment studied the capability of a robot to provide a correct human-robot interaction.
Multi-terminal Secrecy in a Linear Non-coherent Packetized Networks
Venue: arXiv cs.IT 2012
Year: 2012

We consider a group of m+1 trusted nodes that aim to create a shared secret key K over a network in the presence of a passive eavesdropper, Eve. We assume a linear non-coherent network coding broadcast channel (over a finite field F_q) from one of the honest nodes (i.e., Alice) to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free public channel which is also overheard by Eve. For this setup, we propose upper and lower bounds for the secret key generation capacity assuming that the field size q is very large. For the case of two trusted terminals (m = 1) our upper and lower bounds match and we have complete characterization for the secrecy capacity in the large field size regime.
The Glory of the Past and Geometrical Concurrency
Venue: arXiv cs.LO 2012
Year: 2012

This paper contributes to the general understanding of the geometrical model of concurrency that was named higher dimensional automata (HDAs) by Pratt. In particular we investigate modal logics for such models and their expressive power in terms of the bisimulation that can be captured. The geometric model of concurrency is interesting from two main reasons: its generality and expressiveness, and the natural way in which autoconcurrency and action refinement are captured. Logics for this model, though, are not well investigated, where a simple, yet adequate, modal logic over HDAs was only recently introduced. As this modal logic, with two existential modalities, during and after, captures only split bisimulation, which is rather low in the spectrum of van Glabbeek and Vaandrager, the immediate question was what small extension of this logic could capture the more fine-grained hereditary history preserving bisimulation (hh)? In response, the work in this paper provides several insights. One is the fact that the geometrical aspect of HDAs makes it possible to use for capturing the hh-bisimulation, a standard modal logic that does not employ event variables, opposed to the two logics (over less expressive models) that we compare with. The logic that we investigate here uses standard past modalities and extends the previously introduced logic (called HDML) that had only forward, action-labelled, modalities. Besides, we try to understand better the above issues by introducing a related model that we call ST-configuration structures, which extend the configuration structures of van Glabbeek and Plotkin. We relate this model to HDAs, and redefine and prove the earlier results in the light of this new model. These offer a different view on why the past modalities and geometrical concurrency capture the hereditary history preserving bisimulation. Additional correlating insights are also gained.
Software Model Checking with Explicit Scheduler and Symbolic Threads
Venue: arXiv cs.LO 2012
Year: 2012

In many practical application domains, the software is organized into a set of threads, whose activation is exclusive and controlled by a cooperative scheduling policy: threads execute, without any interruption, until they either terminate or yield the control explicitly to the scheduler. The formal verification of such software poses significant challenges. On the one side, each thread may have infinite state space, and might call for abstraction. On the other side, the scheduling policy is often important for correctness, and an approach based on abstracting the scheduler may result in loss of precision and false positives. Unfortunately, the translation of the problem into a purely sequential software model checking problem turns out to be highly inefficient for the available technologies. We propose a software model checking technique that exploits the intrinsic structure of these programs. Each thread is translated into a separate sequential program and explored symbolically with lazy abstraction, while the overall verification is orchestrated by the direct execution of the scheduler. The approach is optimized by filtering the exploration of the scheduler with the integration of partial-order reduction. The technique, called ESST (Explicit Scheduler, Symbolic Threads) has been implemented and experimentally evaluated on a significant set of benchmarks. The results demonstrate that ESST technique is way more effective than software model checking applied to the sequentialized programs, and that partial-order reduction can lead to further performance improvements.
CORL: A Continuous-state Offset-dynamics Reinforcement Learner
Venue: arXiv cs.LG 2012
Year: 2012

Continuous state spaces and stochastic, switching dynamics characterize a number of rich, realworld domains, such as robot navigation across varying terrain. We describe a reinforcementlearning algorithm for learning in these domains and prove for certain environments the algorithm is probably approximately correct with a sample complexity that scales polynomially with the state-space dimension. Unfortunately, no optimal planning techniques exist in general for such problems; instead we use fitted value iteration to solve the learned MDP, and include the error due to approximate planning in our bounds. Finally, we report an experiment using a robotic car driving over varying terrain to demonstrate that these dynamics representations adequately capture real-world dynamics and that our algorithm can be used to efficiently solve such problems.
AND/OR Importance Sampling
Venue: arXiv cs.AI 2012
Year: 2012

The paper introduces AND/OR importance sampling for probabilistic graphical models. In contrast to importance sampling, AND/OR importance sampling caches samples in the AND/OR space and then extracts a new sample mean from the stored samples. We prove that AND/OR importance sampling may have lower variance than importance sampling; thereby providing a theoretical justification for preferring it over importance sampling. Our empirical evaluation demonstrates that AND/OR importance sampling is far more accurate than importance sampling in many cases.
Complexity of Inference in Graphical Models
Venue: arXiv cs.DS 2012
Year: 2012

It is well-known that inference in graphical models is hard in the worst case, but tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with unbounded treewidth in which inference is tractable? Subject to a combinatorial hypothesis due to Robertson et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth.
Multi-View Learning in the Presence of View Disagreement
Venue: arXiv cs.LG 2012
Year: 2012

Traditional multi-view learning approaches suffer in the presence of view disagreement,i.e., when samples in each view do not belong to the same class due to view corruption, occlusion or other noise processes. In this paper we present a multi-view learning approach that uses a conditional entropy criterion to detect view disagreement. Once detected, samples with view disagreement are filtered and standard multi-view learning methods can be successfully applied to the remaining samples. Experimental evaluation on synthetic and audio-visual databases demonstrates that the detection and filtering of view disagreement considerably increases the performance of traditional multi-view learning approaches.
Learning Arithmetic Circuits
Venue: arXiv cs.AI 2012
Year: 2012

Graphical models are usually learned without regard to the cost of doing inference with them. As a result, even if a good model is learned, it may perform poorly at prediction, because it requires approximate inference. We propose an alternative: learning models with a score function that directly penalizes the cost of inference. Specifically, we learn arithmetic circuits with a penalty on the number of edges in the circuit (in which the cost of inference is linear). Our algorithm is equivalent to learning a Bayesian network with context-specific independence by greedily splitting conditional distributions, at each step scoring the candidates by compiling the resulting network into an arithmetic circuit, and using its size as the penalty. We show how this can be done efficiently, without compiling a circuit from scratch for each candidate. Experiments on several real-world domains show that our algorithm is able to learn tractable models with very large treewidth, and yields more accurate predictions than a standard context-specific Bayesian network learner, in far less time.