OpenRaiser/Intern-Atlas huggingface dataset:
Faster Algorithms for Integer Programs with Block Structure
Venue: arXiv cs.DM 2018
Year: 2018

We consider integer programming problems $\max \{ c^T x : \mathcal{A} x = b, l \leq x \leq u, x \in \mathbb{Z}^{nt}\}$ where $\mathcal{A}$ has a (recursive) block-structure generalizing "$n$-fold integer programs" which recently received considerable attention in the literature. An $n$-fold IP is an integer program where $\mathcal{A}$ consists of $n$ repetitions of submatrices $A \in \mathbb{Z}^{r \times t}$ on the top horizontal part and $n$ repetitions of a matrix $B \in \mathbb{Z}^{s \times t}$ on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the $n$-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time $n^2 t^2 ϕ \cdot (rsΔ)^{\mathcal{O}(rs^2+ sr^2)}$ (ignoring logarithmic factors). Here $Δ$ is an upper bound on the largest absolute value of an entry of $\mathcal{A}$ and $ϕ$ is the largest binary encoding length of a coefficient of $c$. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time $n^3t^3 ϕ \cdot Δ^{\mathcal{O}(t^2s)}$. In particular, our algorithm is not exponential in the number $t$ of columns of $A$ and $B$. Our algorithm is based on a new upper bound on the $l_1$-norm of an element of the "Graver basis" of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the "Steinitz Lemma". Furthermore, we extend our techniques to the recently introduced "tree-fold IPs", where we again present a more efficient algorithm in a generalized setting.
Robotic design choice overview using co-simulation
Venue: arXiv cs.RO 2018
Year: 2018

Rapid robotic system development sets a demand for multi-disciplinary methods and tools to explore and compare design alternatives. In this paper, we present collaborative modeling that combines discrete-event models of controller software with continuous-time models of physical robot components. The presented co-modeling method utilized VDM for discrete-event and 20-sim for continuous-time modeling. The collaborative modeling method is illustrated with a concrete example of collaborative model development of a mobile robot animal feeding system. Simulations are used to evaluate the robot model output response in relation to operational demands. The result of the simulations provides the developers with an overview of the impacts of each solution instance in the chosen design space. Based on the solution overview the developers can select candidates that are deemed viable to be deployed and tested on an actual physical robot.
Autonomous Vehicle Speed Control for Safe Navigation of Occluded Pedestrian Crosswalk
Venue: arXiv cs.RO 2018
Year: 2018

Both humans and the sensors on an autonomous vehicle have limited sensing capabilities. When these limitations coincide with scenarios involving vulnerable road users, it becomes important to account for these limitations in the motion planner. For the scenario of an occluded pedestrian crosswalk, the speed of the approaching vehicle should be a function of the amount of uncertainty on the roadway. In this work, the longitudinal controller is formulated as a partially observable Markov decision process and dynamic programming is used to compute the control policy. The control policy scales the speed profile to be used by a model predictive steering controller.
Heuristic Based Induction of Answer Set Programs: From Default theories to combinatorial problems
Venue: arXiv cs.LO 2018
Year: 2018

Significant research has been conducted in recent years to extend Inductive Logic Programming (ILP) methods to induce Answer Set Programs (ASP). These methods perform an exhaustive search for the correct hypothesis by encoding an ILP problem instance as an ASP program. Exhaustive search, however, results in loss of scalability. In addition, the language bias employed in these methods is overly restrictive too. In this paper we extend our previous work on learning stratified answer set programs that have a single stable model to learning arbitrary (i.e., non-stratified) ones with multiple stable models. Our extended algorithm is a greedy FOIL-like algorithm, capable of inducing non-monotonic logic programs, examples of which includes programs for combinatorial problems such as graph-coloring and N-queens. To the best of our knowledge, this is the first heuristic-based ILP algorithm to induce answer set programs with multiple stable models.
Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

Constrained Markov Decision Process (CMDP) is a natural framework for reinforcement learning tasks with safety constraints, where agents learn a policy that maximizes the long-term reward while satisfying the constraints on the long-term cost. A canonical approach for solving CMDPs is the primal-dual method which updates parameters in primal and dual spaces in turn. Existing methods for CMDPs only use on-policy data for dual updates, which results in sample inefficiency and slow convergence. In this paper, we propose a policy search method for CMDPs called Accelerated Primal-Dual Optimization (APDO), which incorporates an off-policy trained dual variable in the dual update procedure while updating the policy in primal space with on-policy likelihood ratio gradient. Experimental results on a simulated robot locomotion task show that APDO achieves better sample efficiency and faster convergence than state-of-the-art approaches for CMDPs.
Committee Scoring Rules: Axiomatic Characterization and Hierarchy
Venue: arXiv cs.GT 2018
Year: 2018

Committee scoring voting rules are multiwinner analogues of positional scoring rules which constitute an important subclass of single-winner voting rules. We identify several natural subclasses of committee scoring rules, namely, weakly separable, representation-focused, top-$k$-counting, OWA-based, and decomposable rules. We characterize SNTV, Bloc, and $k$-Approval Chamberlin--Courant as the only nontrivial rules in pairwise intersections of these classes. We provide some axiomatic characterizations for these classes, where monotonicity properties appear to be especially useful. The class of decomposable rules is new to the literature. We show that it strictly contains the class of OWA-based rules and describe some of the applications of decomposable rules.
Reconfiguration of Colorable Sets in Classes of Perfect Graphs
Venue: arXiv cs.DS 2018
Year: 2018

A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.
Verifying Semantic Conflict-Freedom in Three-Way Program Merges
Venue: arXiv cs.PL 2018
Year: 2018

Even though many programmers rely on 3-way merge tools to integrate changes from different branches, such tools can introduce subtle bugs in the integration process. This paper aims to mitigate this problem by defining a semantic notion of confict-freedom, which ensures that the merged program does not introduce new unwanted behaviors. We also show how to verify this property using a novel, compositional algorithm that combines lightweight dependence analysis for shared program fragments and precise relational reasoning for the modifications. We evaluate our tool called SafeMerge on 52 real-world merge scenarios obtained from Github and compare the results against a textual merge tool. The experimental results demonstrate the benefits of our approach over syntactic confict-freedom and indicate that SafeMerge is both precise and practical.
A 4-Approximation Algorithm for k-Prize Collecting Steiner Tree Problems
Venue: arXiv cs.CC 2018
Year: 2018

This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.
On the computation of Shannon Entropy from Counting Bloom Filters
Venue: arXiv cs.IT 2018
Year: 2018

In this short note a method for computing the naive plugin estimator of discrete entropy from a counting Bloom filter will be presented. The method does work reasonably as long as the collision probability in the bloom filter is kept low.
Ensemble computation approach to the Hough transform
Venue: arXiv cs.CC 2018
Year: 2018

It is demonstrated that the classical Hough transform with shift-elevation parametrization of digital straight lines has additive complexity of at most $\mathcal{O}(n^3 / \log n)$ on a $n\times n$ image. The proof is constructive and uses ensemble computation approach to build summation circuits. The proposed method has similarities with the fast Hough transform (FHT) and may be considered a form of the "divide and conquer" technique. It is based on the fact that lines with close slopes can be decomposed into common components, allowing generalization for other pattern families. When applied to FHT patterns, the algorithm yields exactly the $Θ(n^2\log n)$ FHT asymptotics which might suggest that the actual classical Hough transform circuits could smaller size than $Θ(n^3/ \log n)$.
Osteoarthritis Disease Detection System using Self Organizing Maps Method based on Ossa Manus X-Ray
Venue: arXiv cs.CV 2018
Year: 2018

Osteoarthritis is a disease found in the world, including in Indonesia. The purpose of this study was to detect the disease Osteoarthritis using Self Organizing mapping (SOM), and to know the procedure of artificial intelligence on the methods of Self Organizing Mapping (SOM). In this system, there are several stages to preserve to detect disease Osteoarthritis using Self Organizing maps is the result of photographic images rontgen Ossa Manus normal and sick with the resolution (150 x 200 pixels) do the repair phase contrast, the Gray scale, thresholding process, Histogram of process , and do the last process, where the process of doing training (Training) and testing on images that have kept the shape data (.text). the conclusion is the result of testing by using a data image, where 42 of data have 12 Normal image data and image data 30 sick. On the results of the process of training data there are 8 X-ray image revealed normal right and 19 data x-ray image of pain expressed is correct. Then the accuracy on the process of training was 96.42%, and in the process of testing normal true image 4 obtained revealed Normal, 9 data pain stated true pain and 1 data imagery hurts stated incorrectly, then the accuracy gained from the results of testing are 92,8%.
CalcuList: a Functional Language Extended with Imperative Features
Venue: arXiv cs.PL 2018
Year: 2018

CalcuList (Calculator with List manipulation), is an educational language for teaching functional programming extended with some imperative and side-effect features, which are enabled under explicit request by the programmer. In addition to strings and lists, the language natively supports json objects. The language adopts a Python-like syntax and enables interactive computation sessions with the user through a REPL (Read-Evaluate-Print-Loop) shell. The object code produced by a compilation is a program that will be eventually executed by the CalcuList Virtual Machine (CLVM).
Cost-efficient QoS-Aware Data Acquisition Point Placement for Advanced Metering Infrastructure
Venue: arXiv cs.NI 2018
Year: 2018

In an advanced metering infrastructure (AMI), data acquisition points (DAPs) are responsible for collecting traffic from several smart meters and automated devices and transmitting them to the utility control center. Although the problem of optimized data collector placement has already been addressed for wireless broadband and sensor networks, DAP placement is quite a new research area for AMIs. In this paper, we investigate the minimum required number of DAPs and their optimized locations on top of the existing utility poles in a distribution grid such that smart grid quality of service requirements can best be provided. In order to solve the problem for large-scale AMIs, we devise a novel heuristic algorithm using a greedy approach for identifying potential pole locations for DAP placement and the Dijkstra shortest path algorithm for constructing reliable routes. We employ the characteristics of medium access schemes from the IEEE 802.15.4g smart utility network (SUN) standard, and consider mission-critical and non-critical smart grid traffic. The performance and time-complexity of our algorithm are compared with those obtained by the IBM CPLEX software for small scenarios. Finally, we apply our devised DAP placement algorithm to examples of realistic smart grid AMI topologies.
Multi-task, multi-label and multi-domain learning with residual convolutional networks for emotion recognition
Venue: arXiv cs.CV 2018
Year: 2018

Automated emotion recognition in the wild from facial images remains a challenging problem. Although recent advances in Deep Learning have supposed a significant breakthrough in this topic, strong changes in pose, orientation and point of view severely harm current approaches. In addition, the acquisition of labeled datasets is costly, and current state-of-the-art deep learning algorithms cannot model all the aforementioned difficulties. In this paper, we propose to apply a multi-task learning loss function to share a common feature representation with other related tasks. Particularly we show that emotion recognition benefits from jointly learning a model with a detector of facial Action Units (collective muscle movements). The proposed loss function addresses the problem of learning multiple tasks with heterogeneously labeled data, improving previous multi-task approaches. We validate the proposal using two datasets acquired in non controlled environments, and an application to predict compound facial emotion expressions.
On Local Distributed Sampling and Counting
Venue: arXiv cs.DS 2018
Year: 2018

In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper ($Δ+1$)-list-colorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information. We study distributed sampling and counting problems, in which each instance specifies a joint distribution of feasible solutions. The task of distributed algorithm is to sample from this joint distribution, or to locally measure the volume of the probability space via the marginal probabilities. The latter task is also known as inference, which is a local counterpart of counting. For self-reducible classes of instances, the following equivalences are established in the LOCAL model up to polylogarithmic factors: $\bullet$ For all joint distributions, approximate inference and approximate sampling are computationally equivalent. $\bullet$ For all joint distributions defined by local constraints, exact sampling is reducible to either one of the above tasks. $\bullet$ If further, sequentially constructing a feasible solution is trivial locally, then all above tasks are easy if and only if the joint distribution exhibits strong spatial mixing. Combining with the state of the arts of strong spatial mixing, we obtain efficient sampling algorithms in the LOCAL model for various important sampling problems, including: an $O(\sqrtΔ\log^3n)$-round algorithm for exact sampling matchings in graphs with maximum degree $Δ$, and an $O(\log^3n)$-round algorithm for sampling according to the hardcore model (weighted independent sets) in the uniqueness regime, which along with the $Ω(\mathrm{diam})$ lower bound in arXiv:1702.00142 for sampling according to the hardcore model in the non-uniqueness regime, gives the first computational phase transition for distributed sampling.
The Complexity of Drawing a Graph in a Polygonal Region
Venue: arXiv cs.CC 2018
Year: 2018

We prove that the following problem is complete for the existential theory of the reals: Given a planar graph and a polygonal region, with some vertices of the graph assigned to points on the boundary of the region, place the remaining vertices to create a planar straight-line drawing of the graph inside the region. This strengthens an NP-hardness result by Patrignani on extending partial planar graph drawings. Our result is one of the first showing that a problem of drawing planar graphs with straight-line edges is hard for the existential theory of the reals. The complexity of the problem is open in the case of a simply connected region. We also show that, even for integer input coordinates, it is possible that drawing a graph in a polygonal region requires some vertices to be placed at irrational coordinates. By contrast, the coordinates are known to be bounded in the special case of a convex region, or for drawing a path in any polygonal region.
Differentially Private Generative Adversarial Network
Venue: arXiv cs.LG 2018
Year: 2018

Generative Adversarial Network (GAN) and its variants have recently attracted intensive research interests due to their elegant theoretical foundation and excellent empirical performance as generative models. These tools provide a promising direction in the studies where data availability is limited. One common issue in GANs is that the density of the learned generative distribution could concentrate on the training data points, meaning that they can easily remember training samples due to the high model complexity of deep networks. This becomes a major concern when GANs are applied to private or sensitive data such as patient medical records, and the concentration of distribution may divulge critical patient information. To address this issue, in this paper we propose a differentially private GAN (DPGAN) model, in which we achieve differential privacy in GANs by adding carefully designed noise to gradients during the learning procedure. We provide rigorous proof for the privacy guarantee, as well as comprehensive empirical evidence to support our analysis, where we demonstrate that our method can generate high quality data points at a reasonable privacy level.
Deep Inference of Personality Traits by Integrating Image and Word Use in Social Networks
Venue: arXiv cs.CY 2018
Year: 2018

Social media, as a major platform for communication and information exchange, is a rich repository of the opinions and sentiments of 2.3 billion users about a vast spectrum of topics. To sense the whys of certain social user's demands and cultural-driven interests, however, the knowledge embedded in the 1.8 billion pictures which are uploaded daily in public profiles has just started to be exploited since this process has been typically been text-based. Following this trend on visual-based social analysis, we present a novel methodology based on Deep Learning to build a combined image-and-text based personality trait model, trained with images posted together with words found highly correlated to specific personality traits. So the key contribution here is to explore whether OCEAN personality trait modeling can be addressed based on images, here called \emph{Mind{P}ics}, appearing with certain tags with psychological insights. We found that there is a correlation between those posted images and their accompanying texts, which can be successfully modeled using deep neural networks for personality estimation. The experimental results are consistent with previous cyber-psychology results based on texts or images. In addition, classification results on some traits show that some patterns emerge in the set of images corresponding to a specific text, in essence to those representing an abstract concept. These results open new avenues of research for further refining the proposed personality model under the supervision of psychology experts.
Network Lifetime Maximization for Cellular-Based M2M Networks
Venue: arXiv cs.IT 2018
Year: 2018

High energy efficiency is critical for enabling massive machine-type communications (MTC) over cellular networks. This work is devoted to energy consumption modeling, battery lifetime analysis, lifetime-aware scheduling and transmit power control for massive MTC over cellular networks. We consider a realistic energy consumption model for MTC and model network battery-lifetime. Analytic expressions are derived to demonstrate the impact of scheduling on both the individual and network battery lifetimes. The derived expressions are subsequently employed in the uplink scheduling and transmit power control for mixed-priority MTC traffic in order to maximize the network lifetime. Besides the main solutions, low-complexity solutions with limited feedback requirement are investigated, and the results are extended to existing LTE networks. Also, the energy efficiency, spectral efficiency, and network lifetime tradeoffs in resource provisioning and scheduling for MTC over cellular networks are investigated. The simulation results show that the proposed solutions can provide substantial network lifetime improvement and network maintenance cost reduction
Bayes-optimal Hierarchical Classification over Asymmetric Tree-Distance Loss
Venue: arXiv cs.LG 2018
Year: 2018

Hierarchical classification is supervised multi-class classification problem over the set of class labels organized according to a hierarchy. In this report, we study the work by Ramaswamy et. al. on hierarchical classification over symmetric tree distance loss. We extend the consistency of hierarchical classification algorithm over asymmetric tree distance loss. We design a $\mathcal{O}(nk\log{}n)$ algorithm to find Bayes optimal classification for a k-ary tree as a hierarchy. We show that under reasonable assumptions over asymmetric loss function, the Bayes optimal classification over this asymmetric loss can be found in $\mathcal{O}(k\log{}n)$. We exploit this insight and attempt to extend the Ova-Cascade algorithm \citet{ramaswamy2015convex} for hierarchical classification over the asymmetric loss.