OpenRaiser/Intern-Atlas huggingface dataset:
Probabilistic index maps for modeling natural signals
Venue: arXiv cs.CV 2012
Year: 2012

One of the major problems in modeling natural signals is that signals with very similar structure may locally have completely different measurements, e.g., images taken under different illumination conditions, or the speech signal captured in different environments. While there have been many successful attempts to address these problems in application-specific settings, we believe that underlying a large set of problems in signal representation is a representational deficiency of intensity-derived local measurements that are the basis of most efficient models. We argue that interesting structure in signals is better captured when the signal is de- fined as a matrix whose entries are discrete indices to a separate palette of possible measurements. In order to model the variability in signal structure, we define a signal class not by a single index map, but by a probability distribution over the index maps, which can be estimated from the data, and which we call probabilistic index maps. The existing algorithm can be adapted to work with this representation. Furthermore, the probabilistic index map representation leads to algorithms with computational costs proportional to either the size of the palette or the log of the size of the palette, making the cost of significantly increased invariance to non-structural changes quite bearable. We illustrate the benefits of the probabilistic index map representation in several applications in computer vision and speech processing.
A Hierarchical Graphical Model for Record Linkage
Venue: arXiv cs.LG 2012
Year: 2012

The task of matching co-referent records is known among other names as rocord linkage. For large record-linkage problems, often there is little or no labeled data available, but unlabeled data shows a reasonable clear structure. For such problems, unsupervised or semi-supervised methods are preferable to supervised methods. In this paper, we describe a hierarchical graphical model framework for the linakge-problem in an unsupervised setting. In addition to proposing new methods, we also cast existing unsupervised probabilistic record-linkage methods in this framework. Some of the techniques we propose to minimize overfitting in the above model are of interest in the general graphical model setting. We describe a method for incorporating monotinicity constraints in a graphical model. We also outline a bootstrapping approach of using "single-field" classifiers to noisily label latent variables in a hierarchical model. Experimental results show that our proposed unsupervised methods perform quite competitively even with fully supervised record-linkage methods.
MIMO Interference Alignment in Random Access Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we analyze a multiple-input multiple-output (MIMO) interference channel where nodes are randomly distributed on a plane as a spatial Poisson cluster point process. Each cluster uses interference alignment (IA) to suppress intra-cluster interference but unlike most work on IA, we do not neglect inter-cluster interference. We also connect the accuracy of channel state information to the distance between the nodes, i.e. the quality of CSI degrades with increasing distance. Accounting for the training and feedback overhead, we derive the transmission capacity of this MIMO IA ad hoc network and then compare it to open-loop (interference-blind) spatial multiplexing. Finally, we present exemplary system setups where spatial multiplexing outperforms IA due to the imperfect channel state information or the non-aligned inter-cluster interference.
Multiscale Network Generation
Venue: arXiv cs.DM 2012
Year: 2012

Networks are widely used in science and technology to represent relationships between entities, such as social or ecological links between organisms, enzymatic interactions in metabolic systems, or computer infrastructure. Statistical analyses of networks can provide critical insights into the structure, function, dynamics, and evolution of those systems. However, the structures of real-world networks are often not known completely, and they may exhibit considerable variation so that no single network is sufficiently representative of a system. In such situations, researchers may turn to proxy data from related systems, sophisticated methods for network inference, or synthetic networks. Here, we introduce a flexible method for synthesizing realistic ensembles of networks starting from a known network, through a series of mappings that coarsen and later refine the network structure by randomized editing. The method, MUSKETEER, preserves structural properties with minimal bias, including unknown or unspecified features, while introducing realistic variability at multiple scales. Using examples from several domains, we show that MUSKETEER produces the intended stochasticity while achieving greater fidelity across a suite of network properties than do other commonly used network generation algorithms.
Sequentializing Parameterized Programs
Venue: arXiv cs.LO 2012
Year: 2012

We exhibit assertion-preserving (reachability preserving) transformations from parameterized concurrent shared-memory programs, under a k-round scheduling of processes, to sequential programs. The salient feature of the sequential program is that it tracks the local variables of only one thread at any point, and uses only O(k) copies of shared variables (it does not use extra counters, not even one counter to keep track of the number of threads). Sequentialization is achieved using the concept of a linear interface that captures the effect an unbounded block of processes have on the shared state in a k-round schedule. Our transformation utilizes linear interfaces to sequentialize the program, and to ensure the sequential program explores only reachable states and preserves local invariants.
Analysis of Neighbourhoods in Multi-layered Dynamic Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

Social networks existing among employees, customers or users of various IT systems have become one of the research areas of growing importance. A social network consists of nodes - social entities and edges linking pairs of nodes. In regular, one-layered social networks, two nodes - i.e. people are connected with a single edge whereas in the multi-layered social networks, there may be many links of different types for a pair of nodes. Nowadays data about people and their interactions, which exists in all social media, provides information about many different types of relationships within one network. Analysing this data one can obtain knowledge not only about the structure and characteristics of the network but also gain understanding about semantic of human relations. Are they direct or not? Do people tend to sustain single or multiple relations with a given person? What types of communication is the most important for them? Answers to these and more questions enable us to draw conclusions about semantic of human interactions. Unfortunately, most of the methods used for social network analysis (SNA) may be applied only to one-layered social networks. Thus, some new structural measures for multi-layered social networks are proposed in the paper, in particular: cross-layer clustering coefficient, cross-layer degree centrality and various versions of multi-layered degree centralities. Authors also investigated the dynamics of multi-layered neighbourhood for five different layers within the social network. The evaluation of the presented concepts on the real-world dataset is presented. The measures proposed in the paper may directly be used to various methods for collective classification, in which nodes are assigned to labels according to their structural input features.
Pareto Local Optima of Multiobjective NK-Landscapes with Correlated Objectives
Venue: arXiv cs.NE 2012
Year: 2012

In this paper, we conduct a fitness landscape analysis for multiobjective combinatorial optimization, based on the local optima of multiobjective NK-landscapes with objective correlation. In single-objective optimization, it has become clear that local optima have a strong impact on the performance of metaheuristics. Here, we propose an extension to the multiobjective case, based on the Pareto dominance. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives and the correlation degree between objective functions on the number of Pareto local optima.
Time-Space Constrained Codes for Phase-Change Memories
Venue: arXiv cs.IT 2012
Year: 2012

Phase-change memory (PCM) is a promising non-volatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells, to balance the heat both in time and space. In this paper, we study the time-space constraint for PCM, which was originally proposed by Jiang et al. A code is called an \emph{$(α,β,p)$-constrained code} if for any $α$ consecutive rewrites and for any segment of $β$ contiguous cells, the total rewrite cost of the $β$ cells over those $α$ rewrites is at most $p$. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang et al. Then, we generalize their construction for $(α\geq 1, β=1,p=1)$-constrained codes and show another construction for $(α= 1, β\geq 1,p\geq1)$-constrained codes. Finally, we show that these two constructions can be used to construct codes for all values of $α$, $β$, and $p$.
A 9k kernel for nonseparating independent set in planar graphs
Venue: arXiv cs.DS 2012
Year: 2012

We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. Our main result is a kernel of size at most 9k vertices for the Planar Maximum Nonseparating Independent Set problem. A direct consequence of this result is that Planar Connected Vertex Cover has no kernel with at most (9/8 - epsilon)k vertices, for any epsilon > 0, assuming P \ne NP. We also show a very simple 5k-vertices kernel for Planar Max Leaf, which results in a lower bound of (5/4 - epsilon)k vertices for the kernel of Planar Connected Dominating Set (also under P \ne NP). As a by-product we show a few extremal graph theory results which might be of independent interest. We prove that graphs that contain no separator consisting of only degree two vertices contain (a) a spanning tree with at least n/4 leaves and (b) a nonseparating independent set of size at least n/9 (also, equivalently, a connected vertex cover of size at most 8/9n). The result (a) is a generalization of a theorem of Kleitman and West [SIDMA 1991] who showed the same bound for graphs of minimum degree three. Finally we show that every n-vertex outerplanar graph contains an independent set I and a collection of vertex-disjoint cycles C such that 9|I| >= 4n-3|C|.
Efficient Feedback-Based Scheduling Policies for Chunked Network Codes over Networks with Loss and Delay
Venue: arXiv cs.IT 2012
Year: 2012

The problem of designing efficient feedback-based scheduling policies for chunked codes (CC) over packet networks with delay and loss is considered. For networks with feedback, two scheduling policies, referred to as random push (RP) and local-rarest-first (LRF), already exist. We propose a new scheduling policy, referred to as minimum-distance-first (MDF), based on the expected number of innovative successful packet transmissions at each node of the network prior to the "next" transmission time, given the feedback information from the downstream node(s) about the received packets. Unlike the existing policies, the MDF policy incorporates loss and delay models of the link in the selection process of the chunk to be transmitted. Our simulations show that MDF significantly reduces the expected time required for all the chunks (or equivalently, all the message packets) to be decodable compared to the existing scheduling policies for line networks with feedback. The improvements are particularly profound (up to about 46% for the tested cases) for smaller chunks and larger networks which are of more practical interest. The improvement in the performance of the proposed scheduling policy comes at the cost of more computations, and a slight increase in the amount of feedback. We also propose a low-complexity version of MDF with a rather small loss in the performance, referred to as minimumcurrent-metric-first (MCMF). The MCMF policy is based on the expected number of innovative packet transmissions prior to the "current" transmission time, as opposed to the next transmission time, used in MDF. Our simulations (over line networks) demonstrate that MCMF is always superior to RP and LRF policies, and the superiority becomes more pronounced for smaller chunks and larger networks.
"Two betting strategies that predict all compressible sequences" presentation
Venue: arXiv cs.CC 2012
Year: 2012

Presentation for a talk "Two betting strategies that predict all compressible sequences" given at Seventh International Conference on Computability, Complexity and Randomness (CCR 2012) http://www.newton.ac.uk/programmes/SAS/seminars/070217001.html
Design and User Satisfaction of Interactive Maps for Visually Impaired People
Venue: arXiv cs.HC 2012
Year: 2012

Multimodal interactive maps are a solution for presenting spatial information to visually impaired people. In this paper, we present an interactive multimodal map prototype that is based on a tactile paper map, a multi-touch screen and audio output. We first describe the different steps for designing an interactive map: drawing and printing the tactile paper map, choice of multi-touch technology, interaction technologies and the software architecture. Then we describe the method used to assess user satisfaction. We provide data showing that an interactive map - although based on a unique, elementary, double tap interaction - has been met with a high level of user satisfaction. Interestingly, satisfaction is independent of a user's age, previous visual experience or Braille experience. This prototype will be used as a platform to design advanced interactions for spatial learning.
Finite Alphabet Iterative Decoders, Part I: Decoding Beyond Belief Propagation on BSC
Venue: arXiv cs.IT 2012
Year: 2012

We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the Binary Symmetric channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the Belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist 3-bit precision FAIDs that surpass the BP decoder in the error floor. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.
Bounds and Computation of Irregularity of a Graph
Venue: arXiv cs.DM 2012
Year: 2012

Albertson has defined the irregularity of a simple undirected graph $G=(V,E)$ as $ \irr(G) = \sum_{uv\in E}|d_G(u)-d_G(v)|,$ where $d_G(u)$ denotes the degree of a vertex $u \in V$. Recently, this graph invariant gained interest in the chemical graph theory, where it occured in some bounds on the first and the second Zagreb index, and was named the third Zagreb index Fath-Tabar. For general graphs with $n$ vertices, Albertson has obtained an asymptotically tight upper bound on the irregularity of $4 n^3 /27.$ Here, by exploiting a different approach than in Albertson, we show that for general graphs with $n$ vertices the upper bound $\lfloor \frac{n}{3} \rfloor \lceil \frac{2 n}{3} \rceil (\lceil \frac{2 n}{3} \rceil -1)$ is sharp. Next, we determine $k$-cyclic graphs with maximal irregularity. We also present some bounds on the maximal/minimal irregularity of graphs with fixed minimal and/or maximal vertex degrees, and consider an approximate computation of the irregularity of a graph.
Exploring the rationality of some syntactic merging operators (extended version)
Venue: arXiv cs.AI 2012
Year: 2012

Most merging operators are defined by semantics methods which have very high computational complexity. In order to have operators with a lower computational complexity, some merging operators defined in a syntactical way have be proposed. In this work we define some syntactical merging operators and exploring its rationality properties. To do that we constrain the belief bases to be sets of formulas very close to logic programs and the underlying logic is defined through forward chaining rule (Modus Ponens). We propose two types of operators: arbitration operators when the inputs are only two bases and fusion with integrity constraints operators. We introduce a set of postulates inspired of postulates LS, proposed by Liberatore and Shaerf and then we analyzed the first class of operators through these postulates. We also introduce a set of postulates inspired of postulates KP, proposed by Konieczny and Pino Pérez and then we analyzed the second class of operators through these postulates.
Automorphism Groups of Graphical Models and Lifted Variational Inference
Venue: arXiv cs.AI 2012
Year: 2012

Using the theory of group action, we first introduce the concept of the automorphism group of an exponential family or a graphical model, thus formalizing the general notion of symmetry of a probabilistic model. This automorphism group provides a precise mathematical framework for lifted inference in the general exponential family. Its group action partitions the set of random variables and feature functions into equivalent classes (called orbits) having identical marginals and expectations. Then the inference problem is effectively reduced to that of computing marginals or expectations for each class, thus avoiding the need to deal with each individual variable or feature. We demonstrate the usefulness of this general framework in lifting two classes of variational approximation for MAP inference: local LP relaxation and local LP relaxation with cycle constraints; the latter yields the first lifted inference that operate on a bound tighter than local constraints. Initial experimental results demonstrate that lifted MAP inference with cycle constraints achieved the state of the art performance, obtaining much better objective function values than local approximation while remaining relatively efficient.
A new algorithm for extracting a small representative subgraph from a very large graph
Venue: arXiv cs.DS 2012
Year: 2012

Many real-world networks are prohibitively large for data retrieval, storage and analysis of all of its nodes and links. Understanding the structure and dynamics of these networks entails creating a smaller representative sample of the full graph while preserving its relevant topological properties. In this report, we show that graph sampling algorithms currently proposed in the literature are not able to preserve network properties even with sample sizes containing as many as 20% of the nodes from the original graph. We present a new sampling algorithm, called Tiny Sample Extractor, with a new goal of a sample size smaller than 5% of the original graph while preserving two key properties of a network, the degree distribution and its clustering co-efficient. Our approach is based on a new empirical method of estimating measurement biases in crawling algorithms and compensating for them accordingly. We present a detailed comparison of best known graph sampling algorithms, focusing in particular on how the properties of the sample subgraphs converge to those of the original graph as they grow. These results show that our sampling algorithm extracts a smaller subgraph than other algorithms while also achieving a closer convergence to the degree distribution, measured by the degree exponent, of the original graph. The subgraph generated by the Tiny Sample Extractor, however, is not necessarily representative of the full graph with regard to other properties such as assortativity. This indicates that the problem of extracting a truly representative small subgraph from a large graph remains unsolved.
Multisegmentation through wavelets: Comparing the efficacy of Daubechies vs Coiflets
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, we carry out a comparative study of the efficacy of wavelets belonging to Daubechies and Coiflet family in achieving image segmentation through a fast statistical algorithm.The fact that wavelets belonging to Daubechies family optimally capture the polynomial trends and those of Coiflet family satisfy mini-max condition, makes this comparison interesting. In the context of the present algorithm, it is found that the performance of Coiflet wavelets is better, as compared to Daubechies wavelet.
Checking Satisfiability by Dependency Sequents
Venue: arXiv cs.LO 2012
Year: 2012

We introduce a new algorithm for checking satisfiability based on a calculus of Dependency sequents (D-sequents). Given a CNF formula F(X), a D-sequent is a record stating that under a partial assignment a set of variables of X is redundant in formula \exists{X}[F]. The D-sequent calculus is based on operation join that forms a new D-sequent from two existing D-sequents. The new algorithm solves the quantified version of SAT. That is, given a satisfiable formula F, it, in general, does not produce an assignment satisfying F. The new algorithm is called DS-QSAT where DS stands for Dependency Sequent and Q for Quantified. Importantly, a DPLL-like procedure is only a special case of DS-QSAT where a very restricted kind of D-sequents is used. We argue that this restriction a) adversely affects scalability of SAT-solvers and b) is caused by looking for an explicit satisfying assignment rather than just proving satisfiability. We give experimental results substantiating these claims.
Developing an Activity-Based Costing Approach to Maximize the Efficiency of Customer Relationship Management Projects
Venue: arXiv cs.OH 2012
Year: 2012

In today's competitive environment, profitability analysis is not just about looking at the profit and loss statement. It is more about knowing which of your customers are making you money and which are losing you money. This paper considers how activity-based costing approach may complement a customer relationship management effort. The model presented in this paper combines the principles of activity-based costing with performance measurement. Applying this model helps managers understand the true costs of providing products and services, and the factors that drive these costs, while addressing other concerns such as customer satisfaction. This approach has the potential to integrate all business processes around the requirements of significant profitable customers, a fact that most of the previous researches fail to acknowledge.