OpenRaiser/Intern-Atlas huggingface dataset:
A Compact Linear Programming Relaxation for Binary Sub-modular MRF
Venue: arXiv cs.CV 2014
Year: 2014

We propose a novel compact linear programming (LP) relaxation for binary sub-modular MRF in the context of object segmentation. Our model is obtained by linearizing an $l_1^+$-norm derived from the quadratic programming (QP) form of the MRF energy. The resultant LP model contains significantly fewer variables and constraints compared to the conventional LP relaxation of the MRF energy. In addition, unlike QP which can produce ambiguous labels, our model can be viewed as a quasi-total-variation minimization problem, and it can therefore preserve the discontinuities in the labels. We further establish a relaxation bound between our LP model and the conventional LP model. In the experiments, we demonstrate our method for the task of interactive object segmentation. Our LP model outperforms QP when converting the continuous labels to binary labels using different threshold values on the entire Oxford interactive segmentation dataset. The computational complexity of our LP is of the same order as that of the QP, and it is significantly lower than the conventional LP relaxation.
Outer-Product Hidden Markov Model and Polyphonic MIDI Score Following
Venue: arXiv cs.AI 2014
Year: 2014

We present a polyphonic MIDI score-following algorithm capable of following performances with arbitrary repeats and skips, based on a probabilistic model of musical performances. It is attractive in practical applications of score following to handle repeats and skips which may be made arbitrarily during performances, but the algorithms previously described in the literature cannot be applied to scores of practical length due to problems with large computational complexity. We propose a new type of hidden Markov model (HMM) as a performance model which can describe arbitrary repeats and skips including performer tendencies on distributed score positions before and after them, and derive an efficient score-following algorithm that reduces computational complexity without pruning. A theoretical discussion on how much such information on performer tendencies improves the score-following results is given. The proposed score-following algorithm also admits performance mistakes and is demonstrated to be effective in practical situations by carrying out evaluations with human performances. The proposed HMM is potentially valuable for other topics in information processing and we also provide a detailed description of inference algorithms.
Teaching Network Storage Technology Assessment Outcomes and Directions
Venue: arXiv cs.OH 2014
Year: 2014

The paper presents academic content, delivery and assessment mechanisms used, available resources including initial lessons from teaching Networked Storage Technology as a special topics course to students enrolled in two specific programs - IT and CS. The course is based on the EMC s vendor-neutral Storage Technology Fundamentals course. Furthermore, this manuscript provides a detailed review of how the course fits into our curriculum, particularly, how it helps achieving the 2008 ABET assessment requirements.
Automation Security
Venue: arXiv cs.OH 2014
Year: 2014

Web-based Automated Process Control systems are a new type of applications that use the Internet to control industrial processes with the access to the real-time data. Supervisory control and data acquisition (SCADA) networks contain computers and applications that perform key functions in providing essential services and commodities (e.g., electricity, natural gas, gasoline, water, waste treatment, transportation) to all Americans. As such, they are part of the nation s critical infrastructure and require protection from a variety of threats that exist in cyber space today.
Low-complexity Decoding is Asymptotically Optimal in the SIMO MAC
Venue: arXiv cs.IT 2014
Year: 2014

A single input multiple output (SIMO) multiple access channel, with a large number of transmitters sending symbols from a constellation to the receiver of a multi-antenna base station, is considered. The fundamental limits of joint decoding of the signals from all the users using a low complexity convex relaxation of the maximum likelihood decoder (ML, constellation search) is investigated. It has been shown that in a rich scattering environment, and in the asymptotic limit of a large number of transmitters, reliable communication is possible even without employing coding at the transmitters. This holds even when the number of receiver antennas per transmitter is arbitrarily small, with scaling behaviour arbitrarily close to what is achievable with coding. Thus, the diversity of a large system not only makes the scaling law for coded systems similar to that of uncoded systems, but, as we show, also allows efficient decoders to realize close to the optimal performance of maximum-likelihood decoding. However, while there is no performance loss relative to the scaling laws of the optimal decoder, our proposed low-complexity decoder exhibits a loss of the exponential or near-exponential rates of decay of error probability relative to the optimal ML decoder.
How Credible is the Prediction of a Party-Based Election?
Venue: arXiv cs.MA 2014
Year: 2014

In a party-based election system, the voters are grouped into parties and all voters of a party are assumed to vote according to the party preferences over the candidates. Hence, once the party preferences are declared the outcome of the election can be determined. However, in the actual election, the members of some "instable" parties often leave their own party to join other parties. We introduce two parameters to measure the credibility of the prediction based on party preferences: Min is the minimum number of voters leaving the instable parties such that the prediction is no longer true, while Max is the maximum number of voters leaving the instable parties such that the prediction remains valid. Concerning the complexity of computing Min and Max, we consider both positional scoring rules (Plurality, Veto, r-Approval and Borda) and Condorcet-consistent rules (Copeland and Maximin). We show that for all considered scoring rules, Min is polynomial-time computable, while it is NP-hard to compute Min for Copeland and Maximin. With the only exception of Borda, Max can be computed in polynomial time for other scoring rules. We have NP-hardness results for the computation of Max under Borda, Maximin and Copeland.
Quantum annealing
Venue: arXiv cs.DS 2014
Year: 2014

Brief description on the state of the art of some local optimization methods: Quantum annealing Quantum annealing (also known as alloy, crystallization or tempering) is analogous to simulated annealing but in substitution of thermal activation by quantum tunneling. The class of algorithmic methods for quantum annealing (dubbed: 'QA'), sometimes referred by the italian school as Quantum Stochastic Optimization ('QSO'), is a promising metaheuristic tool for solving local search problems in multivariable optimization contexts.
FRTRUST: a fuzzy reputation based model for trust management in semantic P2P grids
Venue: arXiv cs.DC 2014
Year: 2014

Grid and peer-to-peer (P2P) networks are two ideal technologies for file sharing. A P2P grid is a special case of grid networks in which P2P communications are used for communication between nodes and trust management. Use of this technology allows creation of a network with greater distribution and scalability. Semantic grids have appeared as an expansion of grid networks in which rich resource metadata are revealed and clearly handled. In a semantic P2P grid, nodes are clustered into different groups based on the semantic similarities between their services. This paper proposes a reputation model for trust management in a semantic P2P Grid. We use fuzzy theory, in a trust overlay network named FR TRUST that models the network structure and the storage of reputation information. In fact we present a reputation collection and computation system for semantic P2P Grids. The system uses fuzzy theory to compute a peer trust level, which can be either: Low, Medium, or High. Our experimental results demonstrate that FR TRUST combines low (and therefore desirable) a good computational complexity with high ranking accuracy.
Concave Switching in Single and Multihop Networks
Venue: arXiv cs.SY 2014
Year: 2014

Switched queueing networks model wireless networks, input queued switches and numerous other networked communications systems. For single-hop networks, we consider a {($α,g$)-switch policy} which combines the MaxWeight policies with bandwidth sharing networks -- a further well studied model of Internet congestion. We prove the maximum stability property for this class of randomized policies. Thus these policies have the same first order behavior as the MaxWeight policies. However, for multihop networks some of these generalized polices address a number of critical weakness of the MaxWeight/BackPressure policies. For multihop networks with fixed routing, we consider the Proportional Scheduler (or (1,log)-policy). In this setting, the BackPressure policy is maximum stable, but must maintain a queue for every route-destination, which typically grows rapidly with a network's size. However, this proportionally fair policy only needs to maintain a queue for each outgoing link, which is typically bounded in number. As is common with Internet routing, by maintaining per-link queueing each node only needs to know the next hop for each packet and not its entire route. Further, in contrast to BackPressure, the Proportional Scheduler does not compare downstream queue lengths to determine weights, only local link information is required. This leads to greater potential for decomposed implementations of the policy. Through a reduction argument and an entropy argument, we demonstrate that, whilst maintaining substantially less queueing overhead, the Proportional Scheduler achieves maximum throughput stability.
User Centered Development of Agent-based Business Process Models and Notations
Venue: arXiv cs.SE 2014
Year: 2014

We discuss questions about user centric development of business process modeling notations. In the center of our research there is a fully featured multi-enterprise business process platform (ME-BPP) based on the concepts of agent-based business processes, which builds on the formal foundations of the subject-oriented business process management methodology (S-BPM). The platform is implemented based on cloud technology using commercial services. Additionally we developed a "block modeling" technique to find a semantically transparent modeling notation which can be used by novice users to model subject-oriented business process (S-BPM) models. As this is ongoing research there are still serious open questions. But, the presented approach breaks with some of the rules of typical process modeling notations and hopefully stimulates innovation. Additionally we want to continue our research towards the enhancement of our modeling approach towards a user centric "syntax and semantic free" modeling technique to develop user and domain specific modeling notations.
A Simple Algorithm for Hamiltonicity
Venue: arXiv cs.DS 2014
Year: 2014

We develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit $f$ over a field of characteristic $2$ of degree~$d$. Decide whether $f$, expressed as an equivalent multivariate polynomial, contains a multilinear monomial of degree $d$. This problem was solved by Williams \cite{W} and Björklund et. al. \cite{BHKK} for a white box (the circuit is given as an input) that contains arithmetic circuit. We show a simple black box algorithm that solves the problem with the same time complexity. This gives a simple randomized algorithm for the simple $k$-path problem for directed graphs of the same time complexity\footnote{$O^*(f(k))$ is $O(poly(n)\cdot f(k))$} $O^*(2^k)$ as in \cite{W} and with reusing the same ideas from \cite{BHKK} with the above gives another algorithm (probably not simpler) for undirected graphs of the same time complexity $O^*(1.657^k)$ as in \cite{B10,BHKK}.
Gradient-based Laplacian Feature Selection
Venue: arXiv cs.LG 2014
Year: 2014

Analysis of high dimensional noisy data is of essence across a variety of research fields. Feature selection techniques are designed to find the relevant feature subset that can facilitate classification or pattern detection. Traditional (supervised) feature selection methods utilize label information to guide the identification of relevant feature subsets. In this paper, however, we consider the unsupervised feature selection problem. Without the label information, it is particularly difficult to identify a small set of relevant features due to the noisy nature of real-world data which corrupts the intrinsic structure of the data. Our Gradient-based Laplacian Feature Selection (GLFS) selects important features by minimizing the variance of the Laplacian regularized least squares regression model. With $\ell_1$ relaxation, GLFS can find a sparse subset of features that is relevant to the Laplacian manifolds. Extensive experiments on simulated, three real-world object recognition and two computational biology datasets, have illustrated the power and superior performance of our approach over multiple state-of-the-art unsupervised feature selection methods. Additionally, we show that GLFS selects a sparser set of more relevant features in a supervised setting outperforming the popular elastic net methodology.
Computing Minimum Tile Sets to Self-Assemble Colors Patterns
Venue: arXiv cs.CC 2014
Year: 2014

Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular color pattern. For $k \ge 1$, $k$-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. We prove the {\bf NP}-hardness of 29-PATS, where the best known is that of 60-PATS.
A Tutorial on Independent Component Analysis
Venue: arXiv cs.LG 2014
Year: 2014

Independent component analysis (ICA) has become a standard data analysis technique applied to an array of problems in signal processing and machine learning. This tutorial provides an introduction to ICA based on linear algebra formulating an intuition for ICA from first principles. The goal of this tutorial is to provide a solid foundation on this advanced topic so that one might learn the motivation behind ICA, learn why and when to apply this technique and in the process gain an introduction to this exciting field of active research.
Joint Successive Cancellation Decoding of Polar Codes over Intersymbol Interference Channels
Venue: arXiv cs.IT 2014
Year: 2014

Polar codes are a class of capacity-achieving codes for the binary-input discrete memoryless channels (B-DMCs). However, when applied in channels with intersymbol interference (ISI), the codes may perform poorly with BCJR equalization and conventional decoding methods. To deal with the ISI problem, in this paper a new joint successive cancellation (SC) decoding algorithm is proposed for polar codes in ISI channels, which combines the equalization and conventional decoding. The initialization information of the decoding method is the likelihood functions of ISI codeword symbols rather than the codeword symbols. The decoding adopts recursion formulas like conventional SC decoding and is without iterations. This is in contrast to the conventional iterative algorithm which performs iterations between the equalizer and decoder. In addition, the proposed SC trellis decoding can be easily extended to list decoding which can further improve the performance. Simulation shows that the proposed scheme significantly outperforms the conventional decoding schemes in ISI channels.
ACL2(ml): Machine-Learning for ACL2
Venue: arXiv cs.LO 2014
Year: 2014

ACL2(ml) is an extension for the Emacs interface of ACL2. This tool uses machine-learning to help the ACL2 user during the proof-development. Namely, ACL2(ml) gives hints to the user in the form of families of similar theorems, and generates auxiliary lemmas automatically. In this paper, we present the two most recent extensions for ACL2(ml). First, ACL2(ml) can suggest now families of similar function definitions, in addition to the families of similar theorems. Second, the lemma generation tool implemented in ACL2(ml) has been improved with a method to generate preconditions using the guard mechanism of ACL2. The user of ACL2(ml) can also invoke directly the latter extension to obtain preconditions for his own conjectures.
Compressive Origin-Destination Matrix Estimation
Venue: arXiv cs.SY 2014
Year: 2014

The paper presents an approach to estimate Origin-Destination (OD) flows and their path splits, based on traffic counts on links in the network. The approach called Compressive Origin-Destination Estimation (CODE) is inspired by Compressive Sensing (CS) techniques. Even though the estimation problem is underdetermined, CODE recovers the unknown variables exactly when the number of alternative paths for each OD pair is small. Noiseless, noisy, and weighted versions of CODE are illustrated for synthetic networks, and with real data for a small region in East Providence. CODE's versatility is suggested by its use to estimate the number of vehicles and the Vehicle-Miles Traveled (VMT) using link counts.
An Integer Programming Model for the Dynamic Location and Relocation of Emergency Vehicles: A Case Study
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we address the dynamic Emergency Medical Service (EMS) systems. A dynamic location model is presented that tries to locate and relocate the ambulances. The proposed model controls the movements and locations of ambulances in order to provide a better coverage of the demand points under different fluctuation patterns that may happen during a given period of time. Some numerical experiments have been carried out by using some real-world data sets that have been collected through the French EMS system.
On Simplex Pivoting Rules and Complexity Theory
Venue: arXiv cs.CC 2014
Year: 2014

We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm's path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig's shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules.
Group homomorphisms as error correcting codes
Venue: arXiv cs.IT 2014
Year: 2014

We investigate the minimum distance of the error correcting code formed by the homomorphisms between two finite groups $G$ and $H$. We prove some general structural results on how the distance behaves with respect to natural group operations, such as passing to subgroups and quotients, and taking products. Our main result is a general formula for the distance when $G$ is solvable or $H$ is nilpotent, in terms of the normal subgroup structure of $G$ as well as the prime divisors of $|G|$ and $|H|$. In particular, we show that in the above case, the distance is independent of the subgroup structure of $H$. We complement this by showing that, in general, the distance depends on the subgroup structure $G$.
A Way For Accelerating The DNA Sequence Reconstruction Problem By CUDA
Venue: arXiv cs.DC 2014
Year: 2014

Traditionally, we usually utilize the method of shotgun to cut a DNA sequence into pieces and we have to reconstruct the original DNA sequence from the pieces, those are widely used method for DNA assembly. Emerging DNA sequence technologies open up more opportunities for molecular biology. This paper introduce a new method to improve the efficiency of reconstructing DNA sequence using suffix array based on CUDA programming model. The experimental result show the construction of suffix array using GPU is an more efficient approach on Intel(R) Core(TM) i3-3110K quad-core and NVIDIA GeForce 610M GPU, and study show the performance of our method is more than 20 times than that of CPU serial implementation. We believe our method give a cost-efficient solution to the bioinformatics community.
A Theoretical Assessment of Solution Quality in Evolutionary Algorithms for the Knapsack Problem
Venue: arXiv cs.NE 2014
Year: 2014

Evolutionary algorithms are well suited for solving the knapsack problem. Some empirical studies claim that evolutionary algorithms can produce good solutions to the 0-1 knapsack problem. Nonetheless, few rigorous investigations address the quality of solutions that evolutionary algorithms may produce for the knapsack problem. The current paper focuses on a theoretical investigation of three types of (N+1) evolutionary algorithms that exploit bitwise mutation, truncation selection, plus different repair methods for the 0-1 knapsack problem. It assesses the solution quality in terms of the approximation ratio. Our work indicates that the solution produced by pure strategy and mixed strategy evolutionary algorithms is arbitrarily bad. Nevertheless, the evolutionary algorithm using helper objectives may produce 1/2-approximation solutions to the 0-1 knapsack problem.
Recover Canonical-View Faces in the Wild with Deep Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

Face images in the wild undergo large intra-personal variations, such as poses, illuminations, occlusions, and low resolutions, which cause great challenges to face-related applications. This paper addresses this challenge by proposing a new deep learning framework that can recover the canonical view of face images. It dramatically reduces the intra-person variances, while maintaining the inter-person discriminativeness. Unlike the existing face reconstruction methods that were either evaluated in controlled 2D environment or employed 3D information, our approach directly learns the transformation from the face images with a complex set of variations to their canonical views. At the training stage, to avoid the costly process of labeling canonical-view images from the training set by hand, we have devised a new measurement to automatically select or synthesize a canonical-view image for each identity. As an application, this face recovery approach is used for face verification. Facial features are learned from the recovered canonical-view face images by using a facial component-based convolutional neural network. Our approach achieves the state-of-the-art performance on the LFW dataset.
Joint Estimation and Localization in Sensor Networks
Venue: arXiv cs.MA 2014
Year: 2014

This paper addresses the problem of collaborative tracking of dynamic targets in wireless sensor networks. A novel distributed linear estimator, which is a version of a distributed Kalman filter, is derived. We prove that the filter is mean square consistent in the case of static target estimation. When large sensor networks are deployed, it is common that the sensors do not have good knowledge of their locations, which affects the target estimation procedure. Unlike most existing approaches for target tracking, we investigate the performance of our filter when the sensor poses need to be estimated by an auxiliary localization procedure. The sensors are localized via a distributed Jacobi algorithm from noisy relative measurements. We prove strong convergence guarantees for the localization method and in turn for the joint localization and target estimation approach. The performance of our algorithms is demonstrated in simulation on environmental monitoring and target tracking tasks.