OpenRaiser/Intern-Atlas huggingface dataset:
Image Segmentation in Liquid Argon Time Projection Chamber Detector
Venue: arXiv cs.CV 2015
Year: 2015

The Liquid Argon Time Projection Chamber (LAr-TPC) detectors provide excellent imaging and particle identification ability for studying neutrinos. An efficient and automatic reconstruction procedures are required to exploit potential of this imaging technology. Herein, a novel method for segmentation of images from LAr-TPC detectors is presented. The proposed approach computes a feature descriptor for each pixel in the image, which characterizes amplitude distribution in pixel and its neighbourhood. The supervised classifier is employed to distinguish between pixels representing particle's track and noise. The classifier is trained and evaluated on the hand-labeled dataset. The proposed approach can be a preprocessing step for reconstructing algorithms working directly on detector images.
A Note on the Rate Region of Exact-Repair Regenerating Codes
Venue: arXiv cs.IT 2015
Year: 2015

The rate region of the $(5,4,4)$ exact-repair regenerating codes is provided. The outer bound is obtained through extension of the computational approach developed in an earlier work, and this region is indeed achievable using the canonical layered codes. This result is part of the online collection of "Solutions of Computed Information Theoretic Limits (SCITL)".
Sequential Feature Explanations for Anomaly Detection
Venue: arXiv cs.AI 2015
Year: 2015

In many applications, an anomaly detection system presents the most anomalous data instance to a human analyst, who then must determine whether the instance is truly of interest (e.g. a threat in a security setting). Unfortunately, most anomaly detectors provide no explanation about why an instance was considered anomalous, leaving the analyst with no guidance about where to begin the investigation. To address this issue, we study the problems of computing and evaluating sequential feature explanations (SFEs) for anomaly detectors. An SFE of an anomaly is a sequence of features, which are presented to the analyst one at a time (in order) until the information contained in the highlighted features is enough for the analyst to make a confident judgement about the anomaly. Since analyst effort is related to the amount of information that they consider in an investigation, an explanation's quality is related to the number of features that must be revealed to attain confidence. One of our main contributions is to present a novel framework for large scale quantitative evaluations of SFEs, where the quality measure is based on analyst effort. To do this we construct anomaly detection benchmarks from real data sets along with artificial experts that can be simulated for evaluation. Our second contribution is to evaluate several novel explanation approaches within the framework and on traditional anomaly detection benchmarks, offering several insights into the approaches.
On the complexity of Temporal Equilibrium Logic
Venue: arXiv cs.LO 2015
Year: 2015

Temporal Equilibrium Logic (TEL) is a promising framework that extends the knowledge representation and reasoning capabilities of Answer Set Programming with temporal operators in the style of LTL. To our knowledge it is the first nonmonotonic logic that accommodates fully the syntax of a standard temporal logic (specifically LTL) without requiring further constructions. This paper provides a systematic complexity analysis for the (consistency) problem of checking the existence of a temporal equilibrium model of a TEL formula. It was previously shown that this problem in the general case lies somewhere between PSPACE and EXPSPACE. Here we establish a lower bound matching the known EXPSPACE upper bound. Additionally we analyse the complexity for various natural subclasses of TEL formulas, identifying both tractable and intractable fragments. Finally the paper offers some new insights on the logic LTL by addressing satisfiability for minimal LTL models. The complexity results obtained highlight a substantial difference between interpreting LTL over finite or infinite words.
Crowd Congestion and Stampede Management through Multi Robotic Agents
Venue: arXiv cs.MA 2015
Year: 2015

Crowd management is a complex, challenging and crucial task. Lack of appropriate management of crowd has, in past, led to many unfortunate stampedes with significant loss of life. To increase the crowd management efficiency, we deploy automated real time detection of stampede prone areas. Then, we use robotic agents to aid the crowd management police in controlling the crowd in these stampede prone areas. While doing so, we aim for minimum interference by robotic agents in our environment. Thereby not disturbing the ambiance and aesthetics of the place. We evaluate the effectiveness of our model in dealing with difficult scenarios like emergency evacuation and presence of localized congestion. Lastly, we simulate a multi agent system based on our model and use it to illustrate the utility of robotic agents for detecting and reducing congestion.
Google-based Mode Choice Modeling Approach
Venue: arXiv cs.OH 2015
Year: 2015

Microsimulation based frameworks have become very popular in many research areas including travel demand modeling where activity-based models have been in the center of attention for the past decade. Advanced activity-based models synthesize the entire population of the study region and simulate their activities in a way that they can keep track of agents resources as well as their spatial location. However, the models that are built for these frameworks do not take into account this information mainly because they do not have them at the modeling stage. This paper tries to describe the importance of this information by analyzing a travel survey and generate the actual alternatives that individuals had when making their trips. With a focus on transit, the study reveals how transit alternatives are limited\unavailable in certain areas which must be taken in to account in our mode choice models. Some statistics regarding available alternatives and the constraints people encounter when making a choice are presented with a comprehensive choice set formation. A mode choice model is then developed based on this approach to represent the importance of such information.
Regular realizability problems and context-free languages
Venue: arXiv cs.FL 2015
Year: 2015

We investigate regular realizability (RR) problems, which are the problems of verifying whether intersection of a regular language -- the input of the problem -- and fixed language called filter is non-empty. In this paper we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages complexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context-free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.
A Sampling Technique of Proving Lower Bounds for Noisy Computations
Venue: arXiv cs.CC 2015
Year: 2015

We present a technique of proving lower bounds for noisy computations. This is achieved by a theorem connecting computations on a kind of randomized decision trees and sampling based algorithms. This approach is surprisingly powerful, and applicable to several models of computation previously studied. As a first illustration we show how all the results of Evans and Pippenger (SIAM J. Computing, 1999) for noisy decision trees, some of which were derived using Fourier analysis, follow immediately if we consider the sampling-based algorithms that naturally arise from these decision trees. Next, we show a tight lower bound of $Ω(N \log\log N)$ on the number of transmissions required to compute several functions (including the parity function and the majority function) in a network of $N$ randomly placed sensors, communicating using local transmissions, and operating with power near the connectivity threshold. This result considerably simplifies and strengthens an earlier result of Dutta, Kanoria Manjunath and Radhakrishnan (SODA 08) that such networks cannot compute the parity function reliably with significantly fewer than $N\log \log N$ transmissions. The lower bound for parity shown earlier made use of special properties of the parity function and is inapplicable, e.g., to the majority function. In this paper, we use our approach to develop an interesting connection between computation of boolean functions on noisy networks that make few transmissionss, and algorithms that work by sampling only a part of the input. It is straightforward to verify that such sampling-based algorithms cannot compute the majority function.
Phase Transitions in Sparse PCA
Venue: arXiv cs.IT 2015
Year: 2015

We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to analyze what is the information theoretically minimal mean-squared error and the one achieved by AMP in the limit of large sizes. For a special case of rank one and large enough density of non-zeros Deshpande and Montanari [1] proved that AMP is asymptotically optimal. We show that both for low density and for large rank the problem undergoes a series of phase transitions suggesting existence of a region of parameters where estimation is information theoretically possible, but AMP (and presumably every other polynomial algorithm) fails. The analysis of the large rank limit is particularly instructive.
Coauthorship networks: A directed network approach considering the order and number of coauthors
Venue: arXiv cs.DL 2015
Year: 2015

In many scientific fields, the order of coauthors on a paper conveys information about each individual's contribution to a piece of joint work. We argue that in prior network analyses of coauthorship networks, the information on ordering has been insufficiently considered because ties between authors are typically symmetrized. This is basically the same as assuming that each co-author has contributed equally to a paper. We introduce a solution to this problem by adopting a coauthorship credit allocation model proposed by Kim and Diesner (2014), which in its core conceptualizes co-authoring as a directed, weighted, and self-looped network. We test and validate our application of the adopted framework based on a sample data of 861 authors who have published in the journal Psychometrika. Results suggest that this novel sociometric approach can complement traditional measures based on undirected networks and expand insights into coauthoring patterns such as the hierarchy of collaboration among scholars. As another form of validation, we also show how our approach accurately detects prominent scholars in the Psychometric Society affiliated with the journal.
Heuristic Algorithm using Internet of Things and Mobility for solving demographic issues in Financial Inclusion projects
Venue: arXiv cs.CY 2015
Year: 2015

All over the world, the population in rural and semi-urban areas is a major concern for policy makers as they require technology enablement most to get elevated from their living conditions. Financial Inclusion projects are meant to work in this area as well. However the reach of financial institutions in those areas is much lesser than in urban areas in general. New policies and strategies are being made towards making banking services more accessible to the people in rural and semi-urban area. Technology, in particular Internet of Things (IoT) and Mobility can play a major role in this context as an enabler and multiplier. This paper discusses about an IoT and Mobility driven approach, which the Financial Institutions may consider while trying to work on financial inclusion projects.
Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements
Venue: arXiv cs.IT 2015
Year: 2015

This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that element-wise sparsifies the data, retaining only a few its elements. Our new algorithm independently samples the data using sampling probabilities that depend on both the squares ($\ell_2$ sampling) and absolute values ($\ell_1$ sampling) of the entries. We prove that the hybrid algorithm recovers a near-PCA reconstruction of the data from a sublinear sample-size: hybrid-($\ell_1,\ell_2$) inherits the $\ell_2$-ability to sample the important elements as well as the regularization properties of $\ell_1$ sampling, and gives strictly better performance than either $\ell_1$ or $\ell_2$ on their own. We also give a one-pass version of our algorithm and show experiments to corroborate the theory.
Towards Understanding Enjoyment and Flow in Information Visualization
Venue: arXiv cs.HC 2015
Year: 2015

Traditionally, evaluation studies in information visualization have measured effectiveness by assessing performance time and accuracy. More recently, there has been a concerted effort to understand aspects beyond time and errors. In this paper we study enjoyment, which, while arguably not the primary goal of visualization, has been shown to impact performance and memorability. Different models of enjoyment have been proposed in psychology, education and gaming; yet there is no standard approach to evaluate and measure enjoyment in visualization. In this paper we relate the flow model of Csikszentmihalyi to Munzner's nested model of visualization evaluation and previous work in the area. We suggest that, even though previous papers tackled individual elements of flow, in order to understand what specifically makes a visualization enjoyable, it might be necessary to measure all specific elements.
Interface Reconciliation in Kahn Process Networks using CSP and SAT
Venue: arXiv cs.PL 2015
Year: 2015

We present a new CSP- and SAT-based approach for coordinating interfaces of distributed stream-connected components provided as closed-source services. The Kahn Process Network (KPN) is taken as a formal model of computation and a Message Definition Language (MDL) is introduced to describe the format of messages communicated between the processes. MDL links input and output interfaces of a node to support flow inheritance and contextualisation. Since interfaces can also be linked by the existence of a data channel between them, the match is generally not only partial but also substantially nonlocal. The KPN communication graph thus becomes a graph of interlocked constraints to be satisfied by specific instances of the variables. We present an algorithm that solves the CSP by iterative approximation while generating an adjunct Boolean SAT problem on the way. We developed a solver in OCaml as well as tools that analyse the source code of KPN vertices to derive MDL terms and automatically modify the code by propagating type definitions back to the vertices after the CSP has been solved. Techniques and approaches are illustrated on a KPN implementing an image processing algorithm as a running example.
5G Cellular: Key Enabling Technologies and Research Challenges
Venue: arXiv cs.NI 2015
Year: 2015

The evolving fifth generation (5G) cellular wireless networks are envisioned to provide higher data rates, enhanced end-user quality-of-experience (QoE), reduced end-to-end latency, and lower energy consumption. This article presents several emerging technologies, which will enable and define the 5G mobile communications standards. The major research problems, which these new technologies breed, as well as the measurement and test challenges for 5G systems are also highlighted.
Millimeter Wave Cellular Networks: A MAC Layer Perspective
Venue: arXiv cs.IT 2015
Year: 2015

The millimeter wave (mmWave) frequency band is seen as a key enabler of multi-gigabit wireless access in future cellular networks. In order to overcome the propagation challenges, mmWave systems use a large number of antenna elements both at the base station and at the user equipment, which lead to high directivity gains, fully-directional communications, and possible noise-limited operations. The fundamental differences between mmWave networks and traditional ones challenge the classical design constraints, objectives, and available degrees of freedom. This paper addresses the implications that highly directional communication has on the design of an efficient medium access control (MAC) layer. The paper discusses key MAC layer issues, such as synchronization, random access, handover, channelization, interference management, scheduling, and association. The paper provides an integrated view on MAC layer issues for cellular networks, identifies new challenges and tradeoffs, and provides novel insights and solution approaches.
Simple, Efficient, and Neural Algorithms for Sparse Coding
Venue: arXiv cs.LG 2015
Year: 2015

Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuristics based on alternating minimization. Re- cent work has resulted in several algorithms for sparse coding with provable guarantees, but somewhat surprisingly these are outperformed by the simple alternating minimization heuristics. Here we give a general framework for understanding alternating minimization which we leverage to analyze existing heuristics and to design new ones also with provable guarantees. Some of these algorithms seem implementable on simple neural architectures, which was the original motivation of Olshausen and Field (1997a) in introducing sparse coding. We also give the first efficient algorithm for sparse coding that works almost up to the information theoretic limit for sparse recovery on incoherent dictionaries. All previous algorithms that approached or surpassed this limit run in time exponential in some natural parameter. Finally, our algorithms improve upon the sample complexity of existing approaches. We believe that our analysis framework will have applications in other settings where simple iterative algorithms are used.
DAG-width of Control Flow Graphs with Applications to Model Checking
Venue: arXiv cs.DM 2015
Year: 2015

The treewidth of control flow graphs arising from structured programs is known to be at most six. However, as a control flow graph is inherently directed, it makes sense to consider a measure of width for digraphs instead. We use the so-called DAG-width and show that the DAG-width of control flow graphs arising from structured (goto-free) programs is at most three. Additionally, we also give a linear time algorithm to compute the DAG decomposition of these control flow graphs. One consequence of this result is that parity games (and hence the $μ$-calculus model checking problem), which are known to be tractable on graphs of bounded DAG-width, can be solved efficiently in practice on control flow graphs.
Improved adaptive sparse channel estimation using mixed square/fourth error criterion
Venue: arXiv cs.IT 2015
Year: 2015

Sparse channel estimation problem is one of challenge technical issues in stable broadband wireless communications. Based on square error criterion (SEC), adaptive sparse channel estimation (ASCE) methods, e.g., zero-attracting least mean square error (ZA-LMS) algorithm and reweighted ZA-LMS (RZA-LMS) algorithm, have been proposed to mitigate noise interferences as well as to exploit the inherent channel sparsity. However, the conventional SEC-ASCE methods are vulnerable to 1) random scaling of input training signal; and 2) imbalance between convergence speed and steady state mean square error (MSE) performance due to fixed step-size of gradient descend method. In this paper, a mixed square/fourth error criterion (SFEC) based improved ASCE methods are proposed to avoid aforementioned shortcomings. Specifically, the improved SFEC-ASCE methods are realized with zero-attracting least mean square/fourth error (ZA-LMS/F) algorithm and reweighted ZA-LMS/F (RZA-LMS/F) algorithm, respectively. Firstly, regularization parameters of the SFEC-ASCE methods are selected by means of Monte-Carlo simulations. Secondly, lower bounds of the SFEC-ASCE methods are derived and analyzed. Finally, simulation results are given to show that the proposed SFEC-ASCE methods achieve better estimation performance than the conventional SEC-ASCE methods. 1
Maximum correntropy criterion based sparse adaptive filtering algorithms for robust channel estimation under non-Gaussian environments
Venue: arXiv cs.IT 2015
Year: 2015

Sparse adaptive channel estimation problem is one of the most important topics in broadband wireless communications systems due to its simplicity and robustness. So far many sparsity-aware channel estimation algorithms have been developed based on the well-known minimum mean square error (MMSE) criterion, such as the zero-attracting least mean square (ZALMS), which are robust under Gaussian assumption. In non-Gaussian environments, however, these methods are often no longer robust especially when systems are disturbed by random impulsive noises. To address this problem, we propose in this work a robust sparse adaptive filtering algorithm using correntropy induced metric (CIM) penalized maximum correntropy criterion (MCC) rather than conventional MMSE criterion for robust channel estimation. Specifically, MCC is utilized to mitigate the impulsive noise while CIM is adopted to exploit the channel sparsity efficiently. Both theoretical analysis and computer simulations are provided to corroborate the proposed methods.
Quantomatic: A Proof Assistant for Diagrammatic Reasoning
Venue: arXiv cs.LO 2015
Year: 2015

Monoidal algebraic structures consist of operations that can have multiple outputs as well as multiple inputs, which have applications in many areas including categorical algebra, programming language semantics, representation theory, algebraic quantum information, and quantum groups. String diagrams provide a convenient graphical syntax for reasoning formally about such structures, while avoiding many of the technical challenges of a term-based approach. Quantomatic is a tool that supports the (semi-)automatic construction of equational proofs using string diagrams. We briefly outline the theoretical basis of Quantomatic's rewriting engine, then give an overview of the core features and architecture and give a simple example project that computes normal forms for commutative bialgebras.