OpenRaiser/Intern-Atlas huggingface dataset:
Noisy Activation Functions
Venue: arXiv cs.LG 2016
Year: 2016

Common nonlinear activation functions used in neural networks can cause training difficulties due to the saturation behavior of the activation function, which may hide dependencies that are not visible to vanilla-SGD (using first order gradients only). Gating mechanisms that use softly saturating activation functions to emulate the discrete switching of digital logic circuits are good examples of this. We propose to exploit the injection of appropriate noise so that the gradients may flow easily, even if the noiseless application of the activation function would yield zero gradient. Large noise will dominate the noise-free gradient and allow stochastic gradient descent toexplore more. By adding noise only to the problematic parts of the activation function, we allow the optimization procedure to explore the boundary between the degenerate (saturating) and the well-behaved parts of the activation function. We also establish connections to simulated annealing, when the amount of noise is annealed down, making it easier to optimize hard objective functions. We find experimentally that replacing such saturating activation functions by noisy variants helps training in many contexts, yielding state-of-the-art or competitive results on different datasets and task, especially when training seems to be the most difficult, e.g., when curriculum learning is necessary to obtain good results.
Crowdsourcing On-street Parking Space Detection
Venue: arXiv cs.HC 2016
Year: 2016

As the number of vehicles continues to grow, parking spaces are at a premium in city streets. Additionally, due to the lack of knowledge about street parking spaces, heuristic circling the blocks not only costs drivers' time and fuel, but also increases city congestion. In the wake of recent trend to build convenient, green and energy-efficient smart cities, we rethink common techniques adopted by high-profile smart parking systems, and present a user-engaged (crowdsourcing) and sonar-based prototype to identify urban on-street parking spaces. The prototype includes an ultrasonic sensor, a GPS receiver and associated Arduino micro-controllers. It is mounted on the passenger side of a car to measure the distance from the vehicle to the nearest roadside obstacle. Multiple road tests are conducted around Wheatley, Oxford to gather results and emulate the crowdsourcing approach. By extracting parked vehicles' features from the collected trace, a supervised learning algorithm is developed to estimate roadside parking occupancy and spot illegal parking vehicles. A quantity estimation model is derived to calculate the required number of sensing units to cover urban streets. The estimation is quantitatively compared to a fixed sensing solution. The results show that the crowdsourcing way would need substantially fewer sensors compared to the fixed sensing system.
Wanted: Floating-Point Add Round-off Error instruction
Venue: arXiv cs.NA 2016
Year: 2016

We propose a new instruction (FPADDRE) that computes the round-off error in floating-point addition. We explain how this instruction benefits high-precision arithmetic operations in applications where double precision is not sufficient. Performance estimates on Intel Haswell, Intel Skylake, and AMD Steamroller processors, as well as Intel Knights Corner co-processor, demonstrate that such an instruction would improve the latency of double-double addition by up to 55% and increase double-double addition throughput by up to 103%, with smaller, but non-negligible benefits for double-double multiplication. The new instruction delivers up to 2x speedups on three benchmarks that use high-precision floating-point arithmetic: double-double matrix-matrix multiplication, compensated dot product, and polynomial evaluation via the compensated Horner scheme.
Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
Venue: arXiv cs.LG 2016
Year: 2016

Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled \emph{with} replacement. In practice, however, sampling \emph{without} replacement is very common, easier to implement in many cases, and often performs better. In this paper, we provide competitive convergence guarantees for without-replacement sampling, under various scenarios, for three types of algorithms: Any algorithm with online regret guarantees, stochastic gradient descent, and SVRG. A useful application of our SVRG analysis is a nearly-optimal algorithm for regularized least squares in a distributed setting, in terms of both communication complexity and runtime complexity, when the data is randomly partitioned and the condition number can be as large as the data size per machine (up to logarithmic factors). Our proof techniques combine ideas from stochastic optimization, adversarial online learning, and transductive learning theory, and can potentially be applied to other stochastic optimization and learning problems.
RowHammer: Reliability Analysis and Security Implications
Venue: arXiv cs.DC 2016
Year: 2016

As process technology scales down to smaller dimensions, DRAM chips become more vulnerable to disturbance, a phenomenon in which different DRAM cells interfere with each other's operation. For the first time in academic literature, our ISCA paper exposes the existence of disturbance errors in commodity DRAM chips that are sold and used today. We show that repeatedly reading from the same address could corrupt data in nearby addresses. More specifically: When a DRAM row is opened (i.e., activated) and closed (i.e., precharged) repeatedly (i.e., hammered), it can induce disturbance errors in adjacent DRAM rows. This failure mode is popularly called RowHammer. We tested 129 DRAM modules manufactured within the past six years (2008-2014) and found 110 of them to exhibit RowHammer disturbance errors, the earliest of which dates back to 2010. In particular, all modules from the past two years (2012-2013) were vulnerable, which implies that the errors are a recent phenomenon affecting more advanced generations of process technology. Importantly, disturbance errors pose an easily-exploitable security threat since they are a breach of memory protection, wherein accesses to one page (mapped to one row) modifies the data stored in another page (mapped to an adjacent row).
Vertex Cover Structural Parameterization Revisited
Venue: arXiv cs.DS 2016
Year: 2016

A pseudoforest is a graph whose connected components have at most one cycle. Let X be a pseudoforest modulator of graph G, i. e. a vertex subset of G such that G-X is a pseudoforest. We show that Vertex Cover admits a polynomial kernel being parameterized by the size of the pseudoforest modulator. In other words, we provide a polynomial time algorithm that for an input graph G and integer k, outputs a graph G' and integer k', such that G' has O(|X|12) vertices and G has a vertex cover of size k if and only if G' has vertex cover of size k'. We complement our findings by proving that there is no polynomial kernel for Vertex Cover parameterized by the size of a modulator to a mock forest (a graph where no cycles share a vertex) unless NP is a subset of coNP/poly. In particular, this also rules out polynomial kernels when parameterized by the size of a modulator to outerplanar and cactus graphs.
Filter based Taxonomy Modification for Improving Hierarchical Classification
Venue: arXiv cs.AI 2016
Year: 2016

Hierarchical Classification (HC) is a supervised learning problem where unlabeled instances are classified into a taxonomy of classes. Several methods that utilize the hierarchical structure have been developed to improve the HC performance. However, in most cases apriori defined hierarchical structure by domain experts is inconsistent; as a consequence performance improvement is not noticeable in comparison to flat classification methods. We propose a scalable data-driven filter based rewiring approach to modify an expert-defined hierarchy. Experimental comparisons of top-down HC with our modified hierarchy, on a wide range of datasets shows classification performance improvement over the baseline hierarchy (i:e:, defined by expert), clustered hierarchy and flattening based hierarchy modification approaches. In comparison to existing rewiring approaches, our developed method (rewHier) is computationally efficient, enabling it to scale to datasets with large numbers of classes, instances and features. We also show that our modified hierarchy leads to improved classification performance for classes with few training samples in comparison to flat and state-of-the-art HC approaches.
Grand Challenges in Measuring and Characterizing Scholarly Impact
Venue: arXiv cs.DL 2016
Year: 2016

The constantly growing body of scholarly knowledge of science, technology, and humanities is an asset of the mankind. While new discoveries expand the existing knowledge, they may simultaneously render some of it obsolete. It is crucial for scientists and other stakeholders to keep their knowledge up to date. Policy makers, decision makers, and the general public also need an efficient communication of scientific knowledge. Several grand challenges concerning the creation, adaptation, and diffusion of scholarly knowledge, and advance quantitative and qualitative approaches to the study of scholarly knowledge are identified.
Trainyard is NP-Hard
Venue: arXiv cs.CC 2016
Year: 2016

Recently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that this features are somehow related to their computational complexity \cite{Eppstein}. Indeed, many puzzle games --such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few-- are known to be NP-hard \cite{CondonFLS97, culberson1999sokoban, GualaLN14, Mehta14a}. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP-hard. We also \href{http://trainyard.isnphard.com}{provide} an implementation of our hardness reduction.
Cellular Automata Segmentation of the Boundary between the Compacta of Vertebral Bodies and Surrounding Structures
Venue: arXiv cs.CV 2016
Year: 2016

Due to the aging population, spinal diseases get more and more common nowadays; e.g., lifetime risk of osteoporotic fracture is 40% for white women and 13% for white men in the United States. Thus the numbers of surgical spinal procedures are also increasing with the aging population and precise diagnosis plays a vital role in reducing complication and recurrence of symptoms. Spinal imaging of vertebral column is a tedious process subjected to interpretation errors. In this contribution, we aim to reduce time and error for vertebral interpretation by applying and studying the GrowCut-algorithm for boundary segmentation between vertebral body compacta and surrounding structures. GrowCut is a competitive region growing algorithm using cellular automata. For our study, vertebral T2-weighted Magnetic Resonance Imaging (MRI) scans were first manually outlined by neurosurgeons. Then, the vertebral bodies were segmented in the medical images by a GrowCut-trained physician using the semi-automated GrowCut-algorithm. Afterwards, results of both segmentation processes were compared using the Dice Similarity Coefficient (DSC) and the Hausdorff Distance (HD) which yielded to a DSC of 82.99+/-5.03% and a HD of 18.91+/-7.2 voxel, respectively. In addition, the times have been measured during the manual and the GrowCut segmentations, showing that a GrowCut-segmentation - with an average time of less than six minutes (5.77+/-0.73) - is significantly shorter than a pure manual outlining.
Finiteness and Computation in Toposes
Venue: arXiv cs.LO 2016
Year: 2016

Some notions in mathematics can be considered relative. Relative is a term used to denote when the variation in the position of an observer implies variation in properties or measures on the observed object. We know, from Skolem theorem, that there are first-order models where the set of real numbers is countable and some where it is not. This fact depends on the position of the observer and on the instrument/language the obserevr uses as well, i.e., it depends on whether he/she is inside the model or not and in this particular case the use of first-order logic. In this article, we assume that computation is based on finiteness rather than natural numbers and discuss Turing machines computable morphisms defined on top of the sole notion finiteness. We explore the relativity of finiteness in models provided by toposes where the Axiom of Choice (AC) does not hold, since Tarski proved that if AC holds then all finiteness notions are equivalent. Our toposes do not have natural numbers object (NNO) either, since in a topos with a NNO these finiteness notions are equivalent to Peano finiteness going back to computation on top of Natural Numbers. The main contribution of this article is to show that although from inside every topos, with the properties previously stated, the computation model is standard, from outside some of these toposes, unexpected properties on the computation arise, e.g., infinitely long programs, finite computations containing infinitely long ones, infinitely branching computations. We mainly consider Dedekind and Kuratowski notions of finiteness in this article.
Local Map Descriptor for Compressive Change Retrieval
Venue: arXiv cs.RO 2016
Year: 2016

Change detection, i.e., anomaly detection from local maps built by a mobile robot at multiple different times, is a challenging problem to solve in practice. Most previous work either cannot be applied to scenarios where the size of the map collection is large, or simply assumed that the robot self-location is globally known. In this paper, we tackle the problem of simultaneous self-localization and change detection, by reformulating the problem as a map retrieval problem, and propose a local map descriptor with a compressed bag-of-words (BoW) structure as a scalable solution. We make the following contributions. (1) To enable a direct comparison of the spatial layout of visual features between different local maps, the origin of the local map coordinate (termed "viewpoint") is planned by scene parsing and determined by our "viewpoint planner" to be invariant against small variations in self-location and changes, aiming at providing similar viewpoints for similar scenes (i.e., the relevant map pair). (2) We extend the BoW model to enable the use of not only the appearance (e.g., polestar) but also the spatial layout (e.g., spatial pyramid) of visual features with respect to the planned viewpoint. The key observation is that the planned viewpoint (i.e., the origin of local map coordinate) acts as a pseudo viewpoint that is usually required by spatial BoW (e.g., SPM) and also by anomaly detection (e.g., NN-d, LOF). (3) Experimental results on a challenging "loop-closing" scenario show that the proposed method outperforms previous BoW methods in self-localization, and furthermore, that the use of both appearance and pose information in change detection produces better results than the use of either information alone.
Learning Functions: When Is Deep Better Than Shallow
Venue: arXiv cs.LG 2016
Year: 2016

While the universal approximation property holds both for hierarchical and shallow networks, we prove that deep (hierarchical) networks can approximate the class of compositional functions with the same accuracy as shallow networks but with exponentially lower number of training parameters as well as VC-dimension. This theorem settles an old conjecture by Bengio on the role of depth in networks. We then define a general class of scalable, shift-invariant algorithms to show a simple and natural set of requirements that justify deep convolutional networks.
Reducing complexity of autonomous control agents for verifiability
Venue: arXiv cs.SY 2016
Year: 2016

The AgentSpeak type of languages are considered for decision making in autonomous control systems. To reduce the complexity and increase the verifiability of decision making, a limited instruction set agent (LISA) is introduced. The new decision method is structurally simpler than its predecessors and easily lends itself to both design time and runtime verification methods. The process of converting a control agent in LISA into a model in a probabilistic model checker is described. Due to the practical complexity of design time verification the feasibility of runtime probabilistic verification is investigated and illustrated in the LISA agent programming system for verifying symbolic plans of the agent using a probabilistic model checker.
Where to be wary: The impact of widespread photo-taking and image enhancement practices on users' geo-privacy
Venue: arXiv cs.CY 2016
Year: 2016

Today's geo-location estimation approaches are able to infer the location of a target image using its visual content alone. These approaches exploit visual matching techniques, applied to a large collection of background images with known geo-locations. Users who are unaware that visual retrieval approaches can compromise their geo-privacy, unwittingly open themselves to risks of crime or other unintended consequences. Private photo sharing is not able to protect users effectively, since its inconvenience is a barrier to consistent use, and photos can still fall into the wrong hands if they are re-shared. This paper lays the groundwork for a new approach to geo-privacy of social images: Instead of requiring a complete change of user behavior, we investigate the protection potential latent in users existing practices. We carry out a series of retrieval experiments using a large collection of social images (8.5M) to systematically analyze where users should be wary, and how both photo taking and editing practices impact the performance of geo-location estimation. We find that practices that are currently widespread are already sufficient to protect single-handedly the geo-location ('geo-cloak') up to more than 50% of images whose location would otherwise be automatically predictable. Our conclusion is that protecting users against the unwanted effects of visual retrieval is a viable research field, and should take as its starting point existing user practices.
Designing for Different Stages in Behavior Change
Venue: arXiv cs.HC 2016
Year: 2016

The behavior change process is a dynamic journey with different informational and motivational needs across its different stages; yet current technologies for behavior change are static. In our recent deployment of Habito, an activity tracking mobile app, we found individuals "readiness" to behavior change (or the stage of behavior change they were in) to be a strong predictor of adoption. Individuals in the contemplation and preparation stages had an adoption rate of 56%, whereas individuals in precontemplation, action or maintenance stages had an adoption rate of only 20%. In this position paper we argue for behavior change technologies that are tailored to the different stages of behavior change.
Approximate Relational Hoare Logic for Continuous Random Samplings
Venue: arXiv cs.LO 2016
Year: 2016

Approximate relational Hoare logic (apRHL) is a logic for formal verification of the differential privacy of databases written in the programming language pWHILE. Strictly speaking, however, this logic deals only with discrete random samplings. In this paper, we define the graded relational lifting of the subprobabilistic variant of Giry monad, which described differential privacy. We extend the logic apRHL with this graded lifting to deal with continuous random samplings. We give a generic method to give proof rules of apRHL for continuous random samplings.
A knowledge representation meta-model for rule-based modelling of signalling networks
Venue: arXiv cs.AI 2016
Year: 2016

The study of cellular signalling pathways and their deregulation in disease states, such as cancer, is a large and extremely complex task. Indeed, these systems involve many parts and processes but are studied piecewise and their literatures and data are consequently fragmented, distributed and sometimes--at least apparently--inconsistent. This makes it extremely difficult to build significant explanatory models with the result that effects in these systems that are brought about by many interacting factors are poorly understood. The rule-based approach to modelling has shown some promise for the representation of the highly combinatorial systems typically found in signalling where many of the proteins are composed of multiple binding domains, capable of simultaneous interactions, and/or peptide motifs controlled by post-translational modifications. However, the rule-based approach requires highly detailed information about the precise conditions for each and every interaction which is rarely available from any one single source. Rather, these conditions must be painstakingly inferred and curated, by hand, from information contained in many papers--each of which contains only part of the story. In this paper, we introduce a graph-based meta-model, attuned to the representation of cellular signalling networks, which aims to ease this massive cognitive burden on the rule-based curation process. This meta-model is a generalization of that used by Kappa and BNGL which allows for the flexible representation of knowledge at various levels of granularity. In particular, it allows us to deal with information which has either too little, or too much, detail with respect to the strict rule-based meta-model. Our approach provides a basis for the gradual aggregation of fragmented biological knowledge extracted from the literature into an instance of the meta-model from which we can define an automated translation into executable Kappa programs.
Effective use of the PGAS Paradigm: Driving Transformations and Self-Adaptive Behavior in DASH-Applications
Venue: arXiv cs.DC 2016
Year: 2016

DASH is a library of distributed data structures and algorithms designed for running the applications on modern HPC architectures, composed of hierarchical network interconnections and stratified memory. DASH implements a PGAS (partitioned global address space) model in the form of C++ templates, built on top of DART -- a run-time system with an abstracted tier above existing one-sided communication libraries. In order to facilitate the application development process for exploiting the hierarchical organization of HPC machines, DART allows to reorder the placement of the computational units. In this paper we present an automatic, hierarchical units mapping technique (using a similar approach to the Hilbert curve transformation) to reorder the placement of DART units on the Cray XC40 machine Hazel Hen at HLRS. To evaluate the performance of new units mapping which takes into the account the topology of allocated compute nodes, we perform latency benchmark for a 3D stencil code. The technique of units mapping is generic and can be be adopted in other DART communication substrates and on other hardware platforms. Furthermore, high--level features of DASH are presented, enabling more complex automatic transformations and optimizations in the future.