OpenRaiser/Intern-Atlas huggingface dataset:
Fast Dynamic Programming on Graph Decompositions
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we consider tree decompositions, branch decompositions, and clique decompositions. We improve the running time of dynamic programming algorithms on these graph decompositions for a large number of problems as a function of the treewidth, branchwidth, or cliquewidth, respectively. On tree decompositions of width $k$, we improve the running time for Dominating Set to $O(3^k)$. We generalise this result to $[ρ,σ]$-domination problems with finite or cofinite $ρ$ and $σ$. For these problems, we give $O(s^k)$-time algorithms, where $s$ is the number of `states' a vertex can have in a standard dynamic programming algorithm for such a problems. Furthermore, we give an $O(2^k)$-time algorithm for counting the number of perfect matchings in a graph, and generalise this to $O(2^k)$-time algorithms for many clique covering, packing, and partitioning problems. On branch decompositions of width $k$, we give an $O(3^{\fracω{2}k})$-time algorithm for Dominating Set, an $O(2^{\fracω{2}k})$-time algorithm for counting the number of perfect matchings, and $O(s^{\fracω{2}k})$-time algorithms for $[ρ,σ]$-domination problems involving $s$ states with finite or cofinite $ρ$ and $σ$. Finally, on clique decompositions of width $k$, we give $O(4^k)$-time algorithms for Dominating Set, Independent Dominating Set, and Total Dominating Set. The main techniques used in this paper are a generalisation of fast subset convolution, as introduced by Björklund et al., now applied in the setting of graph decompositions and augmented such that multiple states and multiple ranks can be used. Recently, Lokshtanov et al. have shown that some of the algorithms obtained in this paper have running times in which the base in the exponents is optimal, unless the Strong Exponential-Time Hypothesis fails.
Tree Path Majority Data Structures
Venue: arXiv cs.DS 2018
Year: 2018

We present the first solution to $τ$-majorities on tree paths. Given a tree of $n$ nodes, each with a label from $[1..σ]$, and a fixed threshold $0<τ<1$, such a query gives two nodes $u$ and $v$ and asks for all the labels that appear more than $τ\cdot |P_{uv}|$ times in the path $P_{uv}$ from $u$ to $v$, where $|P_{uv}|$ denotes the number of nodes in $P_{uv}$. Note that the answer to any query is of size up to $1/τ$. On a $w$-bit RAM, we obtain a linear-space data structure with $O((1/τ)\log^* n \log\log_w σ)$ query time. For any $κ> 1$, we can also build a structure that uses $O(n\log^{[κ]} n)$ space, where $\log^{[κ]} n$ denotes the function that applies logarithm $κ$ times to $n$, and answers queries in time $O((1/τ)\log\log_w σ)$. The construction time of both structures is $O(n\log n)$. We also describe two succinct-space solutions with the same query time of the linear-space structure. One uses $2nH + 4n + o(n)(H+1)$ bits, where $H \le \lgσ$ is the entropy of the label distribution, and can be built in $O(n\log n)$ time. The other uses $nH + O(n) + o(nH)$ bits and is built in $O(n\log n)$ time w.h.p.
Performance Evaluation of Deep Learning Networks for Semantic Segmentation of Traffic Stereo-Pair Images
Venue: arXiv cs.CV 2018
Year: 2018

Semantic image segmentation is one the most demanding task, especially for analysis of traffic conditions for self-driving cars. Here the results of application of several deep learning architectures (PSPNet and ICNet) for semantic image segmentation of traffic stereo-pair images are presented. The images from Cityscapes dataset and custom urban images were analyzed as to the segmentation accuracy and image inference time. For the models pre-trained on Cityscapes dataset, the inference time was equal in the limits of standard deviation, but the segmentation accuracy was different for various cities and stereo channels even. The distributions of accuracy (mean intersection over union - mIoU) values for each city and channel are asymmetric, long-tailed, and have many extreme outliers, especially for PSPNet network in comparison to ICNet network. Some statistical properties of these distributions (skewness, kurtosis) allow us to distinguish these two networks and open the question about relations between architecture of deep learning networks and statistical distribution of the predicted results (mIoU here). The results obtained demonstrated the different sensitivity of these networks to: (1) the local street view peculiarities in different cities that should be taken into account during the targeted fine tuning the models before their practical applications, (2) the right and left data channels in stereo-pairs. For both networks, the difference in the predicted results (mIoU here) for the right and left data channels in stereo-pairs is out of the limits of statistical error in relation to mIoU values. It means that the traffic stereo pairs can be effectively used not only for depth calculations (as it is usually used), but also as an additional data channel that can provide much more information about scene objects than simple duplication of the same street view images.
A New Theoretical Evaluation Framework for Satisfaction Equilibria in Wireless Networks
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, a theoretical evaluation framework regarding the \textit{Satisfaction Equilibrium (SE)} in wireless communication networks is introduced and examined. To study these equilibria operation points, we coin some new concepts, namely the \textit{Valued Satisfaction Equilibrium}, the \textit{Price of Efficiency} and the \textit{Max Price of Satisfaction}, which can be used for measuring the efficiency of the obtained equilibria solutions. The aforementioned framework is analyzed and evaluated in a wireless communication environment under the presence of the Gaussian Interference channel (GIC). Within this setting, a non-cooperative game among the users is studied, where users aim in a selfish manner to meet their Quality of Service (QoS) prerequisite. However instead of maximizing the QoS which is generally energy costly, we evangelize that better energy-efficiency is achieved by targeting satisfactory QoS levels only. The sufficient and necessary conditions that lead to the \textit{Satisfaction Equilibrium} are provided for the two-user case and the \textit{Efficient Satisfaction Equilibrium (ESE)} is determined, where the users satisfy their QoS constraints with the lowest possible cost. Moreover, specific measures for evaluating the efficiency of various satisfaction equilibria, in a formal and quantitative manner, expressing the tradeoff with respect to the achieved utility or a given objective function and corresponding cost, are defined and analyzed.
Exploring Feature Reuse in DenseNet Architectures
Venue: arXiv cs.CV 2018
Year: 2018

Densely Connected Convolutional Networks (DenseNets) have been shown to achieve state-of-the-art results on image classification tasks while using fewer parameters and computation than competing methods. Since each layer in this architecture has full access to the feature maps of all previous layers, the network is freed from the burden of having to relearn previously useful features, thus alleviating issues with vanishing gradients. In this work we explore the question: To what extent is it necessary to connect to all previous layers in order to reap the benefits of feature reuse? To this end, we introduce the notion of local dense connectivity and present evidence that less connectivity, allowing for increased growth rate at a fixed network capacity, can achieve a more efficient reuse of features and lead to higher accuracy in dense architectures.
Mining for meaning: from vision to language through multiple networks consensus
Venue: arXiv cs.CV 2018
Year: 2018

Describing visual data into natural language is a very challenging task, at the intersection of computer vision, natural language processing and machine learning. Language goes well beyond the description of physical objects and their interactions and can convey the same abstract idea in many ways. It is both about content at the highest semantic level as well as about fluent form. Here we propose an approach to describe videos in natural language by reaching a consensus among multiple encoder-decoder networks. Finding such a consensual linguistic description, which shares common properties with a larger group, has a better chance to convey the correct meaning. We propose and train several network architectures and use different types of image, audio and video features. Each model produces its own description of the input video and the best one is chosen through an efficient, two-phase consensus process. We demonstrate the strength of our approach by obtaining state of the art results on the challenging MSR-VTT dataset.
Learning to rank for censored survival data
Venue: arXiv cs.LG 2018
Year: 2018

Survival analysis is a type of semi-supervised ranking task where the target output (the survival time) is often right-censored. Utilizing this information is a challenge because it is not obvious how to correctly incorporate these censored examples into a model. We study how three categories of loss functions, namely partial likelihood methods, rank methods, and our classification method based on a Wasserstein metric (WM) and the non-parametric Kaplan Meier estimate of the probability density to impute the labels of censored examples, can take advantage of this information. The proposed method allows us to have a model that predict the probability distribution of an event. If a clinician had access to the detailed probability of an event over time this would help in treatment planning. For example, determining if the risk of kidney graft rejection is constant or peaked after some time. Also, we demonstrate that this approach directly optimizes the expected C-index which is the most common evaluation metric for ranking survival models.
A Peek Into the Hidden Layers of a Convolutional Neural Network Through a Factorization Lens
Venue: arXiv cs.LG 2018
Year: 2018

Despite their increasing popularity and success in a variety of supervised learning problems, deep neural networks are extremely hard to interpret and debug: Given and already trained Deep Neural Net, and a set of test inputs, how can we gain insight into how those inputs interact with different layers of the neural network? Furthermore, can we characterize a given deep neural network based on it's observed behavior on different inputs? In this paper we propose a novel factorization based approach on understanding how different deep neural networks operate. In our preliminary results, we identify fascinating patterns that link the factorization rank (typically used as a measure of interestingness in unsupervised data analysis) with how well or poorly the deep network has been trained. Finally, our proposed approach can help provide visual insights on how high-level. interpretable patterns of the network's input behave inside the hidden layers of the deep network.
Improving Performance Models for Irregular Point-to-Point Communication
Venue: arXiv cs.DC 2018
Year: 2018

Parallel applications are often unable to take full advantage of emerging parallel architectures due to scaling limitations, which arise due to inter-process communication. Performance models are used to analyze the sources of communication costs. However, traditional models for point-to-point communication fail to capture the full cost of many irregular operations, such as sparse matrix methods. In this paper, a node-aware based model is presented. Furthermore, the model is extended to include communication queue search time as well as an additional parameter estimating network contention. The resulting model is applied to a variety of irregular communication patterns throughout matrix operations, displaying improved accuracy over traditional models.
Problems and solutions of the Fourth International Students' Olympiad in Cryptography NSUCRYPTO
Venue: arXiv cs.CR 2018
Year: 2018

Mathematical problems and their solutions of the Fourth International Students' Olympiad in cryptography NSUCRYPTO'2017 are presented. We consider problems related to attacks on ciphers and hash functions, cryptographic Boolean functions, the linear branch number, addition chains, error correction codes, etc. We discuss several open problems on algebraic structure of cryptographic functions, useful proof-of-work algorithms, the Boolean hidden shift problem and quantum computings.
MicroShare: Privacy-Preserved Medical Resource Sharing through MicroService Architecture
Venue: arXiv cs.SE 2018
Year: 2018

This paper takes up the problem of medical resource sharing through MicroService architecture without compromising patient privacy. To achieve this goal, we suggest refactoring the legacy EHR systems into autonomous MicroServices communicating by the unified techniques such as RESTFul web service. This lets us handle clinical data queries directly and far more efficiently for both internal and external queries. The novelty of the proposed approach lies in avoiding the data de-identification process often used as a means of preserving patient privacy. The implemented toolkit combines software engineering technologies such as Java EE, RESTful web services, JSON Web Tokens to allow exchanging medical data in an unidentifiable XML and JSON format as well as restricting users to the need-to-know principle. Our technique also inhibits retrospective processing of data such as attacks by an adversary on a medical dataset using advanced computational methods to reveal Protected Health Information (PHI). The approach is validated on an endoscopic reporting application based on openEHR and MST standards. From the usability perspective, the approach can be used to query datasets by clinical researchers, governmental or non-governmental organizations in monitoring health care and medical record services to improve quality of care and treatment.
Leveraging Secure Multiparty Computation in the Internet of Things
Venue: arXiv cs.CR 2018
Year: 2018

Centralized systems in the Internet of Things---be it local middleware or cloud-based services---fail to fundamentally address privacy of the collected data. We propose an architecture featuring secure multiparty computation at its core in order to realize data processing systems which already incorporate support for privacy protection in the architecture.
Online Makespan Minimization: The Power of Restart
Venue: arXiv cs.DS 2018
Year: 2018

We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of $(5 - \sqrt{5})/2 \approx 1.382$, matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios. We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case.
Designing for Co-located and Virtual Social Interactions in Residential Care
Venue: arXiv cs.CY 2018
Year: 2018

In this paper we explore the feasibility and design challenges in supporting co-located and virtual social interactions in residential care by building on the practice of reminiscence. Motivated by the challenges of social interaction in this context, we first explore the feasibility of a reminiscence-based social interaction tool designed to stimulate conversation in residential care with different stakeholders. Then, we explore the design challenges in supporting an assisting role in co-located reminiscence sessions, by running pilot studies with a technology probe. Our findings point to the feasibility of the tool and the willingness of stakeholders to contribute in the process, although with some skepticism about virtual interactions. The reminiscence sessions showed that compromises are needed when designing for both story collection and conversation stimulation, evidencing specific design areas where further exploration is needed.
Spatial Frequency Loss for Learning Convolutional Autoencoders
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a learning method for convolutional autoencoders (CAEs) for extracting features from images. CAEs can be obtained by utilizing convolutional neural networks to learn an approximation to the identity function in an unsupervised manner. The loss function based on the pixel loss (PL) that is the mean squared error between the pixel values of original and reconstructed images is the common choice for learning. However, using the loss function leads to blurred reconstructed images. A method for learning CAEs using a loss function computed from features reflecting spatial frequencies is proposed to mitigate the problem. The blurs in reconstructed images show lack of high spatial frequency components mainly constituting edges and detailed textures that are important features for tasks such as object detection and spatial matching. In order to evaluate the lack of components, a convolutional layer with a Laplacian filter bank as weights is added to CAEs and the mean squared error of features in a subband, called the spatial frequency loss (SFL), is computed from the outputs of each filter. The learning is performed using a loss function based on the SFL. Empirical evaluation demonstrates that using the SFL reduces the blurs in reconstructed images.
D2D Communications Underlaying Wireless Powered Communication Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we investigate the resource allocation problem for D2D communications underlaying wireless powered communication networks, where multiple D2D pairs harvest energy from a power station equipped with multiple antennas and then transmit information signals simultaneously over the same spectrum resource. The aim is to maximize the sum throughput via joint time scheduling and power control, while satisfying the energy causality constraints. The formulated non-convex problem is first transformed into a nonlinear fractional programming problem with a tactful reformulation. Then, by leveraging D.C. (difference of two convex functions) programming, a suboptimal solution to the non-convex problem is obtained by iteratively solving a sequence of convex problems. Simulation results demonstrate that the proposed scheme works well in different scenarios and can significantly improve the system throughput compared with the-state-of-the-art schemes.
Gaussian Mixture Reduction for Time-Constrained Approximate Inference in Hybrid Bayesian Networks
Venue: arXiv cs.AI 2018
Year: 2018

Hybrid Bayesian Networks (HBNs), which contain both discrete and continuous variables, arise naturally in many application areas (e.g., image understanding, data fusion, medical diagnosis, fraud detection). This paper concerns inference in an important subclass of HBNs, the conditional Gaussian (CG) networks, in which all continuous random variables have Gaussian distributions and all children of continuous random variables must be continuous. Inference in CG networks can be NP-hard even for special-case structures, such as poly-trees, where inference in discrete Bayesian networks can be performed in polynomial time. Therefore, approximate inference is required. In approximate inference, it is often necessary to trade off accuracy against solution time. This paper presents an extension to the Hybrid Message Passing inference algorithm for general CG networks and an algorithm for optimizing its accuracy given a bound on computation time. The extended algorithm uses Gaussian mixture reduction to prevent an exponential increase in the number of Gaussian mixture components. The trade-off algorithm performs pre-processing to find optimal run-time settings for the extended algorithm. Experimental results for four CG networks compare performance of the extended algorithm with existing algorithms and show the optimal settings for these CG networks.
Action4D: Real-time Action Recognition in the Crowd and Clutter
Venue: arXiv cs.CV 2018
Year: 2018

Recognizing every person's action in a crowded and cluttered environment is a challenging task. In this paper, we propose a real-time action recognition method, Action4D, which gives reliable and accurate results in the real-world settings. We propose to tackle the action recognition problem using a holistic 4D "scan" of a cluttered scene to include every detail about the people and environment. Recognizing multiple people's actions in the cluttered 4D representation is a new problem. In this paper, we propose novel methods to solve this problem. We propose a new method to track people in 4D, which can reliably detect and follow each person in real time. We propose a new deep neural network, the Action4D-Net, to recognize the action of each tracked person. The Action4D-Net's novel structure uses both the global feature and the focused attention to achieve state-of-the-art result. Our real-time method is invariant to camera view angles, resistant to clutter and able to handle crowd. The experimental results show that the proposed method is fast, reliable and accurate. Our method paves the way to action recognition in the real-world applications and is ready to be deployed to enable smart homes, smart factories and smart stores.
Visual Reasoning by Progressive Module Networks
Venue: arXiv cs.CV 2018
Year: 2018

Humans learn to solve tasks of increasing complexity by building on top of previously acquired knowledge. Typically, there exists a natural progression in the tasks that we learn - most do not require completely independent solutions, but can be broken down into simpler subtasks. We propose to represent a solver for each task as a neural module that calls existing modules (solvers for simpler tasks) in a functional program-like manner. Lower modules are a black box to the calling module, and communicate only via a query and an output. Thus, a module for a new task learns to query existing modules and composes their outputs in order to produce its own output. Our model effectively combines previous skill-sets, does not suffer from forgetting, and is fully differentiable. We test our model in learning a set of visual reasoning tasks, and demonstrate improved performances in all tasks by learning progressively. By evaluating the reasoning process using human judges, we show that our model is more interpretable than an attention-based baseline.