OpenRaiser/Intern-Atlas huggingface dataset:
On the Convergence of the Polarization Process in the Noisiness/Weak-$\ast$ Topology
Venue: arXiv cs.IT 2018
Year: 2018

Let $W$ be a channel where the input alphabet is endowed with an Abelian group operation, and let $(W_n)_{n\geq 0}$ be Arıkan's channel-valued polarization process that is obtained from $W$ using this operation. We prove that the process $(W_n)_{n\geq 0}$ converges almost surely to deterministic homomorphism channels in the noisiness/weak-$\ast$ topology. This provides a simple proof of multilevel polarization for a large family of channels, containing among others, discrete memoryless channels (DMC), and channels with continuous output alphabets. This also shows that any continuous channel functional converges almost surely (even if the functional does not induce a submartingale or a supermartingale).
Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
Venue: arXiv cs.DS 2018
Year: 2018

One powerful technique to solve NP-hard optimization problems in practice is branch-and-reduce search---which is branch-and-bound that intermixes branching with reductions to decrease the input size. While this technique is known to be very effective in practice for unweighted problems, very little is known for weighted problems, in part due to a lack of known effective reductions. In this work, we develop a full suite of new reductions for the maximum weight independent set problem and provide extensive experiments to show their effectiveness in practice on real-world graphs of up to millions of vertices and edges. Our experiments indicate that our approach is able to outperform existing state-of-the-art algorithms, solving many instances that were previously infeasible. In particular, we show that branch-and-reduce is able to solve a large number of instances up to two orders of magnitude faster than existing (inexact) local search algorithms---and is able to solve the majority of instances within 15 minutes. For those instances remaining infeasible, we show that combining kernelization with local search produces higher-quality solutions than local search alone.
Training of a Skull-Stripping Neural Network with efficient data augmentation
Venue: arXiv cs.CV 2018
Year: 2018

Skull-stripping methods aim to remove the non-brain tissue from acquisition of brain scans in magnetic resonance (MR) imaging. Although several methods sharing this common purpose have been presented in literature, they all suffer from the great variability of the MR images. In this work we propose a novel approach based on Convolutional Neural Networks to automatically perform the brain extraction obtaining cutting-edge performance in the NFBS public database. Additionally, we focus on the efficient training of the neural network designing an effective data augmentation pipeline. Obtained results are evaluated through Dice metric, obtaining a value of 96.5%, and processing time, with 4.5s per volume.
Extended Comment on the Article "Consistent Development of a Beam-To-Beam Contact Algorithm via the Curve to Solid Beam Contact - Analysis for the Non-Frictional Case"
Venue: arXiv cs.CE 2018
Year: 2018

In the authors' previous works, novel finite element formulations for the contact interaction of slender beams have been proposed. In their recent article "Consistent Development of a Beam-To-Beam Contact Algorithm via the Curve to Solid Beam Contact - Analysis for the Non-Frictional Case", Konyukhov et al. refer extensively to the aforementioned works by the authors. However, many of these statements turn out to be scientifically incorrect and not only question the quality and correctness of the authors' previous works in a way that is neither objective nor justified but also might cause quite some confusion to researchers in this field. Hence, the authors find it necessary to comment on these statements, disprove them if incorrect, and demonstrate the correctness of the derivations made in their previous works.
Waveform Signal Entropy and Compression Study of Whole-Building Energy Datasets
Venue: arXiv cs.OH 2018
Year: 2018

Electrical energy consumption has been an ongoing research area since the coming of smart homes and Internet of Things devices. Consumption characteristics and usages profiles are directly influenced by building occupants and their interaction with electrical appliances. Extracted information from these data can be used to conserve energy and increase user comfort levels. Data analysis together with machine learning models can be utilized to extract valuable information for the benefit of occupants themselves, power plants, and grid operators. Public energy datasets provide a scientific foundation to develop and benchmark these algorithms and techniques. With datasets exceeding tens of terabytes, we present a novel study of five whole-building energy datasets with high sampling rates, their signal entropy, and how a well-calibrated measurement can have a significant effect on the overall storage requirements. We show that some datasets do not fully utilize the available measurement precision, therefore leaving potential accuracy and space savings untapped. We benchmark a comprehensive list of 365 file formats, transparent data transformations, and lossless compression algorithms. The primary goal is to reduce the overall dataset size while maintaining an easy-to-use file format and access API. We show that with careful selection of file format and encoding scheme, we can reduce the size of some datasets by up to 73%.
Maximum Independent Sets in Subcubic Graphs: New Results
Venue: arXiv cs.DS 2018
Year: 2018

The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subclass of subcubic graphs generalizing several previously known results.
Training Generative Adversarial Networks Via Turing Test
Venue: arXiv cs.LG 2018
Year: 2018

In this article, we introduce a new mode for training Generative Adversarial Networks (GANs). Rather than minimizing the distance of evidence distribution $\tilde{p}(x)$ and the generative distribution $q(x)$, we minimize the distance of $\tilde{p}(x_r)q(x_f)$ and $\tilde{p}(x_f)q(x_r)$. This adversarial pattern can be interpreted as a Turing test in GANs. It allows us to use information of real samples during training generator and accelerates the whole training procedure. We even find that just proportionally increasing the size of discriminator and generator, it succeeds on 256x256 resolution without adjusting hyperparameters carefully.
SilentPhone: Inferring User Unavailability based Opportune Moments to Minimize Call Interruptions
Venue: arXiv cs.CY 2018
Year: 2018

The increasing popularity of cell phones has made them the most personal and ubiquitous communication devices nowadays. Typically, the ringing notifications of mobile phones are used to inform the users about the incoming calls. However, the notifications of inappropriate incoming calls sometimes cause interruptions not only for the users but also the surrounding people. In this paper, we present a data-driven approach to infer the opportune moments for such phone call interruptions based on user's unavailability, i.e., when a user is unable to answer the incoming phone calls, by analyzing individual's past phone log data, and to discover the corresponding phone silent mode configuring rules for the purpose of minimizing call interruptions in an automated intelligent system. Experiments on the real mobile phone datasets show that our approach is able to identify the opportune moments for call interruptions and generates corresponding silent mode configuring rules by capturing the dominant behavior of individual users' at various times-of-the-day and days-of-the week.
Art gallery problem with rook and queen vision
Venue: arXiv cs.CC 2018
Year: 2018

How many chess rooks or queens does it take to guard all the squares of a given polyomino, the union of square tiles from a square grid? This question is a version of the art gallery problem in which the guards can "see" whichever squares the rook or queen attacks. We show that floor(n/2) rooks or floor(n/3) queens are sufficient and sometimes necessary to guard a polyomino with n tiles. We also prove that finding the minimum number of rooks or the minimum number of queens needed to guard a polyomino is NP-hard. These results also apply to d-dimensional rooks and queens on d-dimensional polycubes. We also use bipartite matching theorems to describe sets of non-attacking rooks on polyominoes.
Stochastic Control with Stale Information--Part I: Fully Observable Systems
Venue: arXiv cs.IT 2018
Year: 2018

In this study, we adopt age of information as a measure of the staleness of information, and take initial steps towards analyzing the control performance of stochastic systems with stale information. Our goals are to cast light on a fundamental limit on the information staleness that is required for a certain level of the control performance and to specify the corresponding stalest information pattern. In the asymptotic regime, such a limit asserts a critical information staleness that is required for stabilization. We achieve these goals by formulating the problem as a stochastic optimization problem and characterizing the associated optimal solutions. These solutions are in fact a control policy, which specifies the control inputs of the plant, and a queuing policy, which specifies the staleness of information at the controller.
Tracking the History and Evolution of Entities: Entity-centric Temporal Analysis of Large Social Media Archives
Venue: arXiv cs.SI 2018
Year: 2018

How did the popularity of the Greek Prime Minister evolve in 2015? How did the predominant sentiment about him vary during that period? Were there any controversial sub-periods? What other entities were related to him during these periods? To answer these questions, one needs to analyze archived documents and data about the query entities, such as old news articles or social media archives. In particular, user-generated content posted in social networks, like Twitter and Facebook, can be seen as a comprehensive documentation of our society, and thus meaningful analysis methods over such archived data are of immense value for sociologists, historians and other interested parties who want to study the history and evolution of entities and events. To this end, in this paper we propose an entity-centric approach to analyze social media archives and we define measures that allow studying how entities were reflected in social media in different time periods and under different aspects, like popularity, attitude, controversiality, and connectedness with other entities. A case study using a large Twitter archive of four years illustrates the insights that can be gained by such an entity-centric and multi-aspect analysis.
Towards a Ranking Model for Semantic Layers over Digital Archives
Venue: arXiv cs.IR 2018
Year: 2018

Archived collections of documents (like newspaper archives) serve as important information sources for historians, journalists, sociologists and other interested parties. Semantic Layers over such digital archives allow describing and publishing metadata and semantic information about the archived documents in a standard format (RDF), which in turn can be queried through a structured query language (e.g., SPARQL). This enables to run advanced queries by combining metadata of the documents (like publication date) and content-based semantic information (like entities mentioned in the documents). However, the results returned by structured queries can be numerous and also they all equally match the query. Thus, there is the need to rank these results in order to promote the most important ones. In this paper, we focus on this problem and propose a ranking model that considers and combines: i) the relativeness of documents to entities, ii) the timeliness of documents, and iii) the relations among the entities.
RELF: Robust Regression Extended with Ensemble Loss Function
Venue: arXiv cs.LG 2018
Year: 2018

Ensemble techniques are powerful approaches that combine several weak learners to build a stronger one. As a meta-learning framework, ensemble techniques can easily be applied to many machine learning methods. Inspired by ensemble techniques, in this paper we propose an ensemble loss functions applied to a simple regressor. We then propose a half-quadratic learning algorithm in order to find the parameter of the regressor and the optimal weights associated with each loss function. Moreover, we show that our proposed loss function is robust in noisy environments. For a particular class of loss functions, we show that our proposed ensemble loss function is Bayes consistent and robust. Experimental evaluations on several datasets demonstrate that our proposed ensemble loss function significantly improves the performance of a simple regressor in comparison with state-of-the-art methods.
Fine-Grained Library Customization
Venue: arXiv cs.SE 2018
Year: 2018

Code bloat widely exists in production-run software. Left untackled, it not only degrades software performance but also increases its attack surface. In this work, we conduct a case study to understand this issue in statically linked libraries. To be specific, we analyze midilib, a software package enclosing statically linked libraries. We show that it is possible to leverage dependence analysis to trim the resultless code statements re- siding in a target library. With this observation, we believe it is possible to build a tool to automatically cut off code pertaining to resultless operations.
The Impact of Position Errors on Crowd Simulation
Venue: arXiv cs.MA 2018
Year: 2018

In large crowd events, there is always a potential possibility that a stampede accident will occur. The accident may cause injuries or even death. Approaches for controlling crowd flows and predicting dangerous congestion spots would be a boon to on-site authorities to manage the crowd and to prevent fatal accidents. One of the most popular approaches is real-time crowd simulation based on position data from personal Global Positioning System (GPS) devices. However, the accuracy of spatial data varies for different GPS devices, and it is also affected by an environment in which an event takes place. In this paper, we would like to assess the effect of position errors on stampede prediction. We propose an Automatic Real-time dEtection of Stampedes (ARES) method to predict stampedes for large events. We implement three different stampede assessment methods in Menge framework and incorporate position errors. Our analysis suggests that the probability of simulated stampede changes significantly with the increase of the magnitude of position errors, which cannot be eliminated entirely with the help of classic techniques, such as the Kalman filter. Thus, it is our position that novel stampede assessment methods should be developed, focusing on the detection of position noise and the elimination of its effect.
Lightweight Structure Design Under Force Location Uncertainty
Venue: arXiv cs.GR 2018
Year: 2018

We introduce a lightweight structure optimization approach for problems in which there is uncertainty in the force locations. Such uncertainty may arise due to force contact locations that change during use or are simply unknown a priori. Given an input 3D model, regions on its boundary where arbitrary normal forces may make contact, and a total force-magnitude budget, our algorithm generates a minimum weight 3D structure that withstands any force configuration capped by the budget. Our approach works by repeatedly finding the most critical force configuration and altering the internal structure accordingly. A key issue, however, is that the critical force configuration changes as the structure evolves, resulting in a significant computational challenge. To address this, we propose an efficient critical instant analysis approach. Combined with a reduced order formulation, our method provides a practical solution to the structural optimization problem. We demonstrate our method on a variety of models and validate it with mechanical tests.
Learning sparse relational transition models
Venue: arXiv cs.LG 2018
Year: 2018

We present a representation for describing transition models in complex uncertain domains using relational rules. For any action, a rule selects a set of relevant objects and computes a distribution over properties of just those objects in the resulting state given their properties in the previous state. An iterative greedy algorithm is used to construct a set of deictic references that determine which objects are relevant in any given state. Feed-forward neural networks are used to learn the transition distribution on the relevant objects' properties. This strategy is demonstrated to be both more versatile and more sample efficient than learning a monolithic transition model in a simulated domain in which a robot pushes stacks of objects on a cluttered table.
Federating distributed storage for clouds in ATLAS
Venue: arXiv cs.DC 2018
Year: 2018

Input data for applications that run in cloud computing centres can be stored at distant repositories, often with multiple copies of the popular data stored at many sites. Locating and retrieving the remote data can be challenging, and we believe that federating the storage can address this problem. A federation would locate the closest copy of the data on the basis of GeoIP information. Currently we are using the dynamic data federation Dynafed, a software solution developed by CERN IT. Dynafed supports several industry standards for connection protocols like Amazon's S3, Microsoft's Azure, as well as WebDAV and HTTP. Dynafed functions as an abstraction layer under which protocol-dependent authentication details are hidden from the user, requiring the user to only provide an X509 certificate. We have setup an instance of Dynafed and integrated it into the ATLAS data distribution management system. We report on the challenges faced during the installation and integration. We have tested ATLAS analysis jobs submitted by the PanDA production system and we report on our first experiences with its operation.
Video-based Person Re-identification Using Spatial-Temporal Attention Networks
Venue: arXiv cs.CV 2018
Year: 2018

We consider the problem of video-based person re-identification. The goal is to identify a person from videos captured under different cameras. In this paper, we propose an efficient spatial-temporal attention based model for person re-identification from videos. Our method generates an attention score for each frame based on frame-level features. The attention scores of all frames in a video are used to produce a weighted feature vector for the input video. Unlike most existing deep learning methods that use global representation, our approach focuses on attention scores. Extensive experiments on two benchmark datasets demonstrate that our method achieves the state-of-the-art performance. This is a technical report.
Texture variation adaptive image denoising with nonlocal PCA
Venue: arXiv cs.CV 2018
Year: 2018

Image textures, as a kind of local variations, provide important information for human visual system. Many image textures, especially the small-scale or stochastic textures are rich in high-frequency variations, and are difficult to be preserved. Current state-of-the-art denoising algorithms typically adopt a nonlocal approach consisting of image patch grouping and group-wise denoising filtering. To achieve a better image denoising while preserving the variations in texture, we first adaptively group high correlated image patches with the same kinds of texture elements (texels) via an adaptive clustering method. This adaptive clustering method is applied in an over-clustering-and-iterative-merging approach, where its noise robustness is improved with a custom merging threshold relating to the noise level and cluster size. For texture-preserving denoising of each cluster, considering that the variations in texture are captured and wrapped in not only the between-dimension energy variations but also the within-dimension variations of PCA transform coefficients, we further propose a PCA-transform-domain variation adaptive filtering method to preserve the local variations in textures. Experiments on natural images show the superiority of the proposed transform-domain variation adaptive filtering to traditional PCA-based hard or soft threshold filtering. As a whole, the proposed denoising method achieves a favorable texture preserving performance both quantitatively and visually, especially for stochastic textures, which is further verified in camera raw image denoising.
Sub-O(log n) Out-of-Order Sliding-Window Aggregation
Venue: arXiv cs.DS 2018
Year: 2018

Sliding-window aggregation summarizes the most recent information in a data stream. Users specify how that summary is computed, usually as an associative binary operator because this is the most general known form for which it is possible to avoid naively scanning every window. For strictly in-order arrivals, there are algorithms with $O(1)$ time per window change assuming associative operators. Meanwhile, it is common in practice for streams to have data arriving slightly out of order, for instance, due to clock drifts or communication delays. Unfortunately, for out-of-order streams, one has to resort to latency-prone buffering or pay $O(\log n)$ time per insert or evict, where $n$ is the window size. This paper presents the design, analysis, and implementation of FiBA, a novel sliding-window aggregation algorithm with an amortized upper bound of $O(\log d)$ time per insert or evict, where $d$ is the distance of the inserted or evicted value to the closer end of the window. This means $O(1)$ time for in-order arrivals and nearly $O(1)$ time for slightly out-of-order arrivals, with a smooth transition towards $O(\log n)$ as $d$ approaches $n$. We also prove a matching lower bound on running time, showing optimality. Our algorithm is as general as the prior state-of-the-art: it requires associativity, but not invertibility nor commutativity. At the heart of the algorithm is a careful combination of finger-searching techniques, lazy rebalancing, and position-aware partial aggregates. We further show how to answer range queries that aggregate subwindows for window sharing. Finally, our experimental evaluation shows that FiBA performs well in practice and supports the theoretical findings.
HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion
Venue: arXiv cs.DC 2018
Year: 2018

Many important real-world applications-such as social networks or distributed data bases-can be modeled as hypergraphs. In such a model, vertices represent entities-such as users or data records-whereas hyperedges model a group membership of the vertices-such as the authorship in a specific topic or the membership of a data record in a specific replicated shard. To optimize such applications, we need an efficient and effective solution to the NP-hard balanced k-way hypergraph partitioning problem. However, existing hypergraph partitioners that scale to very large graphs do not effectively exploit the hypergraph structure when performing the partitioning decisions. We propose HYPE, a hypergraph partitionier that exploits the neighborhood relations between vertices in the hypergraph using an efficient implementation of neighborhood expansion. HYPE improves partitioning quality by up to 95% and reduces runtime by up to 39% compared to streaming partitioning.