OpenRaiser/Intern-Atlas huggingface dataset:
Iterated risk measures for risk-sensitive Markov decision processes with discounted cost
Venue: arXiv cs.GT 2012
Year: 2012

We demonstrate a limitation of discounted expected utility, a standard approach for representing the preference to risk when future cost is discounted. Specifically, we provide an example of the preference of a decision maker that appears to be rational but cannot be represented with any discounted expected utility. A straightforward modification to discounted expected utility leads to inconsistent decision making over time. We will show that an iterated risk measure can represent the preference that cannot be represented by any discounted expected utility and that the decisions based on the iterated risk measure are consistent over time.
New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices
Venue: arXiv cs.LG 2012
Year: 2012

Kernel methods are successful approaches for different machine learning problems. This success is mainly rooted in using feature maps and kernel matrices. Some methods rely on the eigenvalues/eigenvectors of the kernel matrix, while for other methods the spectral information can be used to estimate the excess risk. An important question remains on how close the sample eigenvalues/eigenvectors are to the population values. In this paper, we improve earlier results on concentration bounds for eigenvalues of general kernel matrices. For distance and inner product kernel functions, e.g. radial basis functions, we provide new concentration bounds, which are characterized by the eigenvalues of the sample covariance matrix. Meanwhile, the obstacles for sharper bounds are accounted for and partially addressed. As a case study, we derive a concentration inequality for sample kernel target-alignment.
An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Models
Venue: arXiv cs.LG 2012
Year: 2012

Probabilistic inference in graphical models is the task of computing marginal and conditional densities of interest from a factorized representation of a joint probability distribution. Inference algorithms such as variable elimination and belief propagation take advantage of constraints embedded in this factorization to compute such densities efficiently. In this paper, we propose an algorithm which computes interventional distributions in latent variable causal models represented by acyclic directed mixed graphs(ADMGs). To compute these distributions efficiently, we take advantage of a recursive factorization which generalizes the usual Markov factorization for DAGs and the more recent factorization for ADMGs. Our algorithm can be viewed as a generalization of variable elimination to the mixed graph case. We show our algorithm is exponential in the mixed graph generalization of treewidth.
Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective
Venue: arXiv cs.AI 2012
Year: 2012

Identifying and controlling bias is a key problem in empirical sciences. Causal diagram theory provides graphical criteria for deciding whether and how causal effects can be identified from observed (nonexperimental) data by covariate adjustment. Here we prove equivalences between existing as well as new criteria for adjustment and we provide a new simplified but still equivalent notion of d-separation. These lead to efficient algorithms for two important tasks in causal diagram analysis: (1) listing minimal covariate adjustments (with polynomial delay); and (2) identifying the subdiagram involved in biasing paths (in linear time). Our results improve upon existing exponential-time solutions for these problems, enabling users to assess the effects of covariate adjustment on diagrams with tens to hundreds of variables interactively in real time.
Tightening MRF Relaxations with Planar Subproblems
Venue: arXiv cs.LG 2012
Year: 2012

We describe a new technique for computing lower-bounds on the minimum energy configuration of a planar Markov Random Field (MRF). Our method successively adds large numbers of constraints and enforces consistency over binary projections of the original problem state space. These constraints are represented in terms of subproblems in a dual-decomposition framework that is optimized using subgradient techniques. The complete set of constraints we consider enforces cycle consistency over the original graph. In practice we find that the method converges quickly on most problems with the addition of a few subproblems and outperforms existing methods for some interesting classes of hard potentials.
Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization
Venue: arXiv cs.AI 2012
Year: 2012

Compiling Bayesian networks (BNs) to junction trees and performing belief propagation over them is among the most prominent approaches to computing posteriors in BNs. However, belief propagation over junction tree is known to be computationally intensive in the general case. Its complexity may increase dramatically with the connectivity and state space cardinality of Bayesian network nodes. In this paper, we address this computational challenge using GPU parallelization. We develop data structures and algorithms that extend existing junction tree techniques, and specifically develop a novel approach to computing each belief propagation message in parallel. We implement our approach on an NVIDIA GPU and test it using BNs from several applications. Experimentally, we study how junction tree parameters affect parallelization opportunities and hence the performance of our algorithm. We achieve speedups ranging from 0.68 to 9.18 for the BNs studied.
A feature extraction technique based on character geometry for character recognition
Venue: arXiv cs.CV 2012
Year: 2012

This paper describes a geometry based technique for feature extraction applicable to segmentation-based word recognition systems. The proposed system extracts the geometric features of the character contour. This features are based on the basic line types that forms the character skeleton. The system gives a feature vector as its output. The feature vectors so generated from a training set, were then used to train a pattern recognition engine based on Neural Networks so that the system can be benchmarked.
Performance of Amplify-and-Forward Multihop Transmission over Relay Clusters with Different Routing Strategies
Venue: arXiv cs.IT 2012
Year: 2012

We Consider a multihop relay network in which two terminals are communicating with each other via a number of cluster of relays. Performance of such networks depends on the routing protocols employed. In this paper, we find the expressions for the average symbol error probability (ASEP) performance of amplify-and-forward (AF) multihop transmission for the simplest routing protocol in which the relay transmits using the channel having the best symbol to noise ratio (SNR). The ASEP performance of a better protocol proposed in [1] known as the adhoc protocol is also analyzed. The derived expressions for the performance are a convenient tool to analyze the performance of AF multihop transmission over relay clusters. Monte-Carlo simulations verify the correctness of the proposed formulation and are in agreement with analytical results. Furthermore, we propose new generalized protocols termed as last-n-hop selection protocol, the dual path protocol, the forward- backward last-n-hop selection protocol, and the forward-backward dual path protocol, to get improved ASEP performances. The ASEP performance of these proposed schemes is analysed by computer simulations. It is shown that close to optimal performance can be achieved by using the last-n-hop selection protocol and its forward-backward variant. The complexity of the protocols is also studied.
The Leiden Ranking 2011/2012: Data collection, indicators, and interpretation
Venue: arXiv cs.DL 2012
Year: 2012

The Leiden Ranking 2011/2012 is a ranking of universities based on bibliometric indicators of publication output, citation impact, and scientific collaboration. The ranking includes 500 major universities from 41 different countries. This paper provides an extensive discussion of the Leiden Ranking 2011/2012. The ranking is compared with other global university rankings, in particular the Academic Ranking of World Universities (commonly known as the Shanghai Ranking) and the Times Higher Education World University Rankings. Also, a detailed description is offered of the data collection methodology of the Leiden Ranking 2011/2012 and of the indicators used in the ranking. Various innovations in the Leiden Ranking 2011/2012 are presented. These innovations include (1) an indicator based on counting a university's highly cited publications, (2) indicators based on fractional rather than full counting of collaborative publications, (3) the possibility of excluding non-English language publications, and (4) the use of stability intervals. Finally, some comments are made on the interpretation of the ranking, and a number of limitations of the ranking are pointed out.
Web Services-Enhanced Agile Modeling and Integrating Business Processes
Venue: arXiv cs.SE 2012
Year: 2012

In a global business context with continuous changes, the enterprises have to enhance their operational efficiency, to react more quickly, to ensure the flexibility of their business processes, and to build new collaboration pathways with external partners. To achieve this goal, they must use e-business methods, mechanisms and techniques while capitalizing on the potential of new information and communication technologies. In this context, we propose a standards, model and Web services-based approach for modeling and integrating agile enterprise business processes. The purpose is to benefit from Web services characteristics to enhance the processes design and realize their dynamic integration. The choice of focusing on Web services is essentially justified by their broad adoption by enterprises as well as their capability to warranty interoperability between both intra and inter-enterprises systems. Thereby, we propose in this chapter a metamodel for describing business processes, and discuss their dynamic integration by addressing the Web services discovery issue. On the one hand, the proposed metamodel is in line with the W3C Web services standards, namely, WSDL, SAWSDL and WS-Policy. It considers the use of BPMN standard to describe the behavioral aspect of business processes and completes their design using UML diagrams describing their functional, non-functional and semantic aspects. On other hand, our approach for integrating processes is in line with BPEL standard recommended to orchestrate Web services. To realize executable business processes, this approach recommends the use of semantic matching and selection mechanisms in order to produce agile systems.
Serial Symmetrical Relocation Algorithm for the Equal Sphere Packing Problem
Venue: arXiv cs.DM 2012
Year: 2012

For dealing with the equal sphere packing problem, we propose a serial symmetrical relocation algorithm, which is effective in terms of the quality of the numerical results. We have densely packed up to 200 equal spheres in spherical container and up to 150 equal spheres in cube container. All results are rigorous because of a fake sphere trick. It was conjectured impossible to pack 68 equal spheres of radius 1 into a sphere of radius 5. The serial symmetrical relocation algorithm has proven wrong this conjecture by finding one such packing.
Regularized Robust Coding for Face Recognition
Venue: arXiv cs.CV 2012
Year: 2012

Recently the sparse representation based classification (SRC) has been proposed for robust face recognition (FR). In SRC, the testing image is coded as a sparse linear combination of the training samples, and the representation fidelity is measured by the l2-norm or l1-norm of the coding residual. Such a sparse coding model assumes that the coding residual follows Gaussian or Laplacian distribution, which may not be effective enough to describe the coding residual in practical FR systems. Meanwhile, the sparsity constraint on the coding coefficients makes SRC's computational cost very high. In this paper, we propose a new face coding model, namely regularized robust coding (RRC), which could robustly regress a given signal with regularized regression coefficients. By assuming that the coding residual and the coding coefficient are respectively independent and identically distributed, the RRC seeks for a maximum a posterior solution of the coding problem. An iteratively reweighted regularized robust coding (IR3C) algorithm is proposed to solve the RRC model efficiently. Extensive experiments on representative face databases demonstrate that the RRC is much more effective and efficient than state-of-the-art sparse representation based methods in dealing with face occlusion, corruption, lighting and expression changes, etc.
Immuno-inspired robotic applications: a review
Venue: arXiv cs.RO 2012
Year: 2012

Artificial immune systems primarily mimic the adaptive nature of biological immune functions. Their ability to adapt to varying pathogens makes such systems a suitable choice for various robotic applications. Generally, AIS-based robotic applications map local instantaneous sensory information into either an antigen or a co-stimulatory signal, according to the choice of representation schema. Algorithms then use relevant immune functions to output either evolved antibodies or maturity of dendritic cells, in terms of actuation signals. It is observed that researchers, in an attempt to solve the problem in hand, do not try to replicate the biological immunity but select necessary immune functions instead, resulting in an ad-hoc manner these applications are reported. Authors, therefore, present a comprehensive review of immuno-inspired robotic applications in an attempt to categorize them according to underlying immune definitions. Implementation details are tabulated in terms of corresponding mathematical expressions and their representation schema that include binary, real or hybrid data. Limitations of reported applications are also identified in light of modern immunological interpretations. As a result of this study, authors suggest a renewed focus on innate immunity and also emphasize that immunological representations should benefit from robot embodiment and must be extended to include modern trends.
A Critical Look at Decentralized Personal Data Architectures
Venue: arXiv cs.CY 2012
Year: 2012

While the Internet was conceived as a decentralized network, the most widely used web applications today tend toward centralization. Control increasingly rests with centralized service providers who, as a consequence, have also amassed unprecedented amounts of data about the behaviors and personalities of individuals. Developers, regulators, and consumer advocates have looked to alternative decentralized architectures as the natural response to threats posed by these centralized services. The result has been a great variety of solutions that include personal data stores (PDS), infomediaries, Vendor Relationship Management (VRM) systems, and federated and distributed social networks. And yet, for all these efforts, decentralized personal data architectures have seen little adoption. This position paper attempts to account for these failures, challenging the accepted wisdom in the web community on the feasibility and desirability of these approaches. We start with a historical discussion of the development of various categories of decentralized personal data architectures. Then we survey the main ideas to illustrate the common themes among these efforts. We tease apart the design characteristics of these systems from the social values that they (are intended to) promote. We use this understanding to point out numerous drawbacks of the decentralization paradigm, some inherent and others incidental. We end with recommendations for designers of these systems for working towards goals that are achievable, but perhaps more limited in scope and ambition.
Conceptual Level Design of Semi-structured Database System: Graph-semantic Based Approach
Venue: arXiv cs.SE 2012
Year: 2012

This paper has proposed a Graph - semantic based conceptual model for semi-structured database system, called GOOSSDM, to conceptualize the different facets of such system in object oriented paradigm. The model defines a set of graph based formal constructs, variety of relationship types with participation constraints and rich set of graphical notations to specify the conceptual level design of semi-structured database system. The proposed design approach facilitates modeling of irregular, heterogeneous, hierarchical and non-hierarchical semi-structured data at the conceptual level. Moreover, the proposed GOOSSDM is capable to model XML document at conceptual level with the facility of document-centric design, ordering and disjunction characteristic. A rule based transformation mechanism of GOOSSDM schema into the equivalent XML Schema Definition (XSD) also has been proposed in this paper. The concepts of the proposed conceptual model have been implemented using Generic Modeling Environment (GME).
Bifurcation Boundary Conditions for Switching DC-DC Converters Under Constant On-Time Control
Venue: arXiv cs.SY 2012
Year: 2012

Sampled-data analysis and harmonic balance analysis are applied to analyze switching DC-DC converters under constant on-time control. Design-oriented boundary conditions for the period-doubling bifurcation and the saddle-node bifurcation are derived. The required ramp slope to avoid the bifurcations and the assigned pole locations associated with the ramp are also derived. The derived boundary conditions are more general and accurate than those recently obtained. Those recently obtained boundary conditions become special cases under the general modeling approach presented in this paper. Different analyses give different perspectives on the system dynamics and complement each other. Under the sampled-data analysis, the boundary conditions are expressed in terms of signal slopes and the ramp slope. Under the harmonic balance analysis, the boundary conditions are expressed in terms of signal harmonics. The derived boundary conditions are useful for a designer to design a converter to avoid the occurrence of the period-doubling bifurcation and the saddle-node bifurcation.
Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks
Venue: arXiv cs.DC 2012
Year: 2012

Consider a time-slotted, single-hop, wireless sensor network (WSN) consisting of n correct devices and and t=f*n Byzantine devices where f>=0 is any constant; that is, the Byzantine devices may outnumber the correct ones. There exists a trusted sender Alice who wishes to deliver a message m over a single channel to the correct devices. There also exists a malicious user Carol who controls the t Byzantine devices and uses them to disrupt the communication channel. For a constant k>=2, the correct and Byzantine devices each possess a meager energy budget of O(n^{1/k}), Alice and Carol each possess a limited budget of \tilde{O}(n^{1/k}), and sending or listening in a slot incurs unit cost. This general setup captures the inherent challenges of guaranteeing communication despite scarce resources and attacks on the network. Given this Alice versus Carol scenario, we ask: Is communication of m feasible and, if so, at what cost? We develop a protocol which, for an arbitrarily small constant ε>0, ensures that at least (1-ε)n correct devices receive m with high probability. Furthermore, if Carol's devices expend T energy jamming the channel, then Alice and the correct devices each spend only \tilde{O}(T^{1/(k+1)}). In other words, delaying the transmission of m forces a jammer to rapidly deplete its energy supply and, consequently, cease attacks on the network.
Securing a mobile adhoc network from routing attacks through the application of genetic algorithm
Venue: arXiv cs.NI 2012
Year: 2012

In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile networks [mobile ad hoc networks (MANETs)], wireless sensor networks, etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, i.e., the network topology changes over time due to energy conservation or node mobility. Therefore, the SP routing problem in MANETs turns out to be a dynamic optimization problem. GA's are able to find, if not the shortest, at least an optimal path between source and destination in mobile ad-hoc network nodes. And we obtain the alternative path or backup path to avoid reroute discovery in the case of link failure or node failure.
All graphs with at most seven vertices are Pairwise Compatibility Graphs
Venue: arXiv cs.DM 2012
Year: 2012

A graph $G$ is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree $T$ and two non-negative real numbers $d_{min}$ and $d_{max}$ such that each leaf $l_u$ of $T$ corresponds to a vertex $u \in V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_{T,w} (l_u, l_v) \leq d_{max}$ where $d_{T,w} (l_u, l_v)$ is the sum of the weights of the edges on the unique path from $l_u$ to $l_v$ in $T$. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular all these graphs except for the wheel on 7 vertices $W_7$ are PCGs of a particular structure of a tree: a centipede.
Publication Trends in Astronomy: The Lone Author
Venue: arXiv cs.DL 2012
Year: 2012

In this short communication I highlight how the number of collaborators on papers in the main astronomy journals has evolved over time. We see a trend of moving away from single-author papers. This communication is based on data in the holdings of the SAO/NASA Astrophysics Data System (ADS). The ADS is funded by NASA Grant NNX09AB39G.
Non-Stationary Random Process for Large-Scale Failure and Recovery of Power Distributions
Venue: arXiv cs.SY 2012
Year: 2012

A key objective of the smart grid is to improve reliability of utility services to end users. This requires strengthening resilience of distribution networks that lie at the edge of the grid. However, distribution networks are exposed to external disturbances such as hurricanes and snow storms where electricity service to customers is disrupted repeatedly. External disturbances cause large-scale power failures that are neither well-understood, nor formulated rigorously, nor studied systematically. This work studies resilience of power distribution networks to large-scale disturbances in three aspects. First, a non-stationary random process is derived to characterize an entire life cycle of large-scale failure and recovery. Second, resilience is defined based on the non-stationary random process. Close form analytical expressions are derived under specific large-scale failure scenarios. Third, the non-stationary model and the resilience metric are applied to a real life example of large-scale disruptions due to Hurricane Ike. Real data on large-scale failures from an operational network is used to learn time-varying model parameters and resilience metrics.