OpenRaiser/Intern-Atlas huggingface dataset:
Deterministic Min-Cost Matching with Delays
Venue: arXiv cs.DS 2018
Year: 2018

We consider the online Minimum-Cost Perfect Matching with Delays (MPMD) problem introduced by Emek et al. (STOC 2016), in which a general metric space is given, and requests are submitted in different times in this space by an adversary. The goal is to match requests, while minimizing the sum of distances between matched pairs in addition to the time intervals passed from the moment each request appeared until it is matched. In the online Minimum-Cost Bipartite Perfect Matching with Delays (MBPMD) problem introduced by Ashlagi et al. (APPROX/RANDOM 2017), each request is also associated with one of two classes, and requests can only be matched with requests of the other class. Previous algorithms for the problems mentioned above, include randomized $O\left(\log n\right)$-competitive algorithms for known and finite metric spaces, $n$ being the size of the metric space, and a deterministic $O\left(m\right)$-competitive algorithm, $m$ being the number of requests. We introduce $O\left(m^{\log\left(\frac{3}{2}+ε\right)}\right)$-competitive deterministic algorithms for both problems and for any fixed $ε> 0$. In particular, for a small enough $ε$ the competitive ratio becomes $O\left(m^{0.59}\right)$. These are the first deterministic algorithms for the mentioned online matching problems, achieving a sub-linear competitive ratio. Our algorithms do not need to know the metric space in advance.
Context Tree for Adaptive Session-based Recommendation
Venue: arXiv cs.IR 2018
Year: 2018

There has been growing interests in recent years from both practical and research perspectives for session-based recommendation tasks as long-term user profiles do not often exist in many real-life recommendation applications. In this case, recommendations for user's immediate next actions need to be generated based on patterns in anonymous short sessions. An often overlooked aspect is that new items with limited observations arrive continuously in many domains (e.g. news and discussion forums). Therefore, recommendations need to be adaptive to such frequent changes. In this paper, we benchmark a new nonparametric method called context tree (CT) against various state-of-the-art methods on extensive datasets for session-based recommendation task. Apart from the standard static evaluation protocol adopted by previous literatures, we include an adaptive configuration to mimic the situation when new items with limited observations arrives continuously. Our results show that CT outperforms two best-performing approaches (recurrent neural network; heuristic-based nearest neighbor) in majority of the tested configurations and datasets. We analyze reasons for this and demonstrate that it is because of the better adaptation to changes in the domain, as well as the remarkable capability to learn static sequential patterns. Moreover, our running time analysis illustrates the efficiency of using CT as other nonparametric methods.
Distributed Kalman Filter for A Class of Nonlinear Uncertain Systems: An Extended State Method
Venue: arXiv cs.SY 2018
Year: 2018

This paper studies the distributed state estimation problem for a class of discrete-time stochastic systems with nonlinear uncertain dynamics over time-varying topologies of sensor networks. An extended state vector consisting of the original state and the nonlinear dynamics is constructed. By analyzing the extended system, we provide a design method for the filtering gain and fusion matrices, leading to the extended state distributed Kalman filter. It is shown that the proposed filter can provide the upper bound of estimation covariance in real time, which means the estimation accuracy can be evaluated online.It is proven that the estimation covariance of the filter is bounded under rather mild assumptions, i.e., collective observability of the system and jointly strong connectedness of network topologies. Numerical simulation shows the effectiveness of the proposed filter.
Air-Ground Integrated Vehicular Network Slicing with Content Pushing and Caching
Venue: arXiv cs.NI 2018
Year: 2018

In this paper, an Air-Ground Integrated VEhicular Network (AGIVEN) architecture is proposed, where the aerial High Altitude Platforms (HAPs) proactively push contents to vehicles through large-area broadcast while the ground roadside units (RSUs) provide high-rate unicast services on demand. To efficiently manage the multi-dimensional heterogeneous resources, a service-oriented network slicing approach is introduced, where the AGIVEN is virtually divided into multiple slices and each slice supports a specific application with guaranteed quality of service (QoS). Specifically, the fundamental problem of multi-resource provisioning in AGIVEN slicing is investigated, by taking into account typical vehicular applications of location-based map and popularity-based content services. For the location-based map service, the capability of HAP-vehicle proactive pushing is derived with respect to the HAP broadcast rate and vehicle cache size, wherein a saddle point exists indicating the optimal communication-cache resource trading. For the popular contents of common interests, the average on-board content hit ratio is obtained, with HAPs pushing newly generated contents to keep on-board cache fresh. Then, the minimal RSU transmission rate is derived to meet the average delay requirements of each slice. The obtained analytical results reveal the service-dependent resource provisioning and trading relationships among RSU transmission rate, HAP broadcast rate, and vehicle cache size, which provides guidelines for multi-resource network slicing in practice. Simulation results demonstrate that the proposed AGIVEN network slicing approach matches the multi-resources across slices, whereby the RSU transmission rate can be saved by 40% while maintaining the same QoS.
A Cost-based Storage Format Selector for Materialization in Big Data Frameworks
Venue: arXiv cs.DC 2018
Year: 2018

Modern big data frameworks (such as Hadoop and Spark) allow multiple users to do large-scale analysis simultaneously. Typically, users deploy Data-Intensive Workflows (DIWs) for their analytical tasks. These DIWs of different users share many common parts (i.e, 50-80%), which can be materialized to reuse them in future executions. The materialization improves the overall processing time of DIWs and also saves computational resources. Current solutions for materialization store data on Distributed File Systems (DFS) by using a fixed data format. However, a fixed choice might not be the optimal one for every situation. For example, it is well-known that different data fragmentation strategies (i.e., horizontal, vertical or hybrid) behave better or worse according to the access patterns of the subsequent operations. In this paper, we present a cost-based approach which helps deciding the most appropriate storage format in every situation. A generic cost-based storage format selector framework considering the three fragmentation strategies is presented. Then, we use our framework to instantiate cost models for specific Hadoop data formats (namely SequenceFile, Avro and Parquet), and test it with realistic use cases. Our solution gives on average 33% speedup over SequenceFile, 11% speedup over Avro, 32% speedup over Parquet, and overall, it provides upto 25% performance gain.
Gear Training: A new way to implement high-performance model-parallel training
Venue: arXiv cs.LG 2018
Year: 2018

The training of Deep Neural Networks usually needs tremendous computing resources. Therefore many deep models are trained in large cluster instead of single machine or GPU. Though major researchs at present try to run whole model on all machines by using asynchronous asynchronous stochastic gradient descent (ASGD), we present a new approach to train deep model parallely -- split the model and then seperately train different parts of it in different speed.
State Classification with CNN
Venue: arXiv cs.CV 2018
Year: 2018

There is a plenty of research going on in field of object recognition, but object state recognition has not been addressed as much. There are many important applications which can utilize object state recognition, such as, in robotics, to decide for how to grab an object. A convolution neural network was designed to classify an image to one of its states. The approach used for training is transfer learning with Inception v3 module of GoogLeNet used as the pre-trained model. The model was trained on images of 18 cooking objects and tested on another set of cooking objects. The model was able to classify those images with 76% accuracy.
Quantitative Phase Imaging and Artificial Intelligence: A Review
Venue: arXiv cs.CV 2018
Year: 2018

Recent advances in quantitative phase imaging (QPI) and artificial intelligence (AI) have opened up the possibility of an exciting frontier. The fast and label-free nature of QPI enables the rapid generation of large-scale and uniform-quality imaging data in two, three, and four dimensions. Subsequently, the AI-assisted interrogation of QPI data using data-driven machine learning techniques results in a variety of biomedical applications. Also, machine learning enhances QPI itself. Herein, we review the synergy between QPI and machine learning with a particular focus on deep learning. Further, we provide practical guidelines and perspectives for further development.
CT-Realistic Lung Nodule Simulation from 3D Conditional Generative Adversarial Networks for Robust Lung Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Data availability plays a critical role for the performance of deep learning systems. This challenge is especially acute within the medical image domain, particularly when pathologies are involved, due to two factors: 1) limited number of cases, and 2) large variations in location, scale, and appearance. In this work, we investigate whether augmenting a dataset with artificially generated lung nodules can improve the robustness of the progressive holistically nested network (P-HNN) model for pathological lung segmentation of CT scans. To achieve this goal, we develop a 3D generative adversarial network (GAN) that effectively learns lung nodule property distributions in 3D space. In order to embed the nodules within their background context, we condition the GAN based on a volume of interest whose central part containing the nodule has been erased. To further improve realism and blending with the background, we propose a novel multi-mask reconstruction loss. We train our method on over 1000 nodules from the LIDC dataset. Qualitative results demonstrate the effectiveness of our method compared to the state-of-art. We then use our GAN to generate simulated training images where nodules lie on the lung border, which are cases where the published P-HNN model struggles. Qualitative and quantitative results demonstrate that armed with these simulated images, the P-HNN model learns to better segment lung regions under these challenging situations. As a result, our system provides a promising means to help overcome the data paucity that commonly afflicts medical imaging.
Enabling Strong Privacy Preservation and Accurate Task Allocation for Mobile Crowdsensing
Venue: arXiv cs.CR 2018
Year: 2018

Mobile crowdsensing engages a crowd of individuals to use their mobile devices to cooperatively collect data about social events and phenomena for special interest customers. It can reduce the cost on sensor deployment and improve data quality with human intelligence. To enhance data trustworthiness, it is critical for service provider to recruit mobile users based on their personal features, e.g., mobility pattern and reputation, but it leads to the privacy leakage of mobile users. Therefore, how to resolve the contradiction between user privacy and task allocation is challenging in mobile crowdsensing. In this paper, we propose SPOON, a strong privacy-preserving mobile crowdsensing scheme supporting accurate task allocation from geographic information and credit points of mobile users. In SPOON, the service provider enables to recruit mobile users based on their locations, and select proper sensing reports according to their trust levels without invading user privacy. By utilizing proxy re-encryption and BBS+ signature, sensing tasks are protected and reports are anonymized to prevent privacy leakage. In addition, a privacy-preserving credit management mechanism is introduced to achieve decentralized trust management and secure credit proof for mobile users. Finally, we show the security properties of SPOON and demonstrate its efficiency on computation and communication.
The Optimal DoF Region for the Two-User Non-Coherent SIMO Multiple-Access Channel
Venue: arXiv cs.IT 2018
Year: 2018

The optimal degree-of-freedom (DoF) region of the non-coherent multiple-access channels is still unknown in general. In this paper, we make some progress by deriving the entire optimal DoF region in the case of the two-user single-input multiple-output (SIMO) generic block fading channels. The achievability is based on a simple training-based scheme. The novelty of our result lies in the converse using a genie-aided bound and the duality upper bound. As a by-product, our result generalizes previous proofs for the single-user Rayleigh block fading channels.
Regions of Attraction Approximation Using Individual Invariance
Venue: arXiv cs.SY 2018
Year: 2018

Approximating regions of attraction in nonlinear systems require extensive computational and analytical efforts. In this paper, nonlinear vector fields are recasted as sum of vectors where each individual vector is used to construct an artificial system. The theoretical foundation is provided for a theorem in individual invariance to relate regions of attraction of artificial systems to the original vector field's region of attraction which leads to significant simplification in approximating regions of attraction. Several second order examples are used to demonstrate the effectiveness of this theorem. It is also proposed to use this theorem for the transient stability problem in power systems where an algorithm is presented to identify the critical clearing time through sequences of function evaluations. The algorithm is successfully applied on the 3-machine 9-bus system as well as the IEEE 39-bus New England system giving accurate and realistic estimations of the critical clearing time.
"AIded with emotions" - a new design approach towards affective computer systems
Venue: arXiv cs.HC 2018
Year: 2018

As technologies become more and more pervasive, there is a need for considering the affective dimension of interaction with computer systems to make them more human-like. Current demands for this matter include accurate emotion recognition, reliable emotion modeling, and use of unobtrusive, easily accessible and preferably wearable measurement devices. While AI methods provide many possibilities for better affective information processing, it is not a common scenario for both emotion recognition and modeling to be integrated in the design phase. To address this concern, we propose a new approach based on affective design patterns in the context of video games, together with summary of experiments conducted to test the preliminary hypotheses.
Compositional Discovery of Workflow Nets from Event Logs Using Morphisms
Venue: arXiv cs.MA 2018
Year: 2018

This paper presents a modular approach to discover process models for multi-agent systems from event logs. System event logs are filtered according to individual agent behavior. We discover workflow nets for each agent using existing process discovery algorithms. We consider asynchronous interactions among agents. Given a specification of an interaction protocol, we propose a general scheme of workflow net composition. By using morphisms, we prove that this composition preserves soundness of components. A quality evaluation shows the increase in the precision of models discovered by the proposed approach.
Learning Multilingual Topics from Incomparable Corpus
Venue: arXiv cs.CL 2018
Year: 2018

Multilingual topic models enable crosslingual tasks by extracting consistent topics from multilingual corpora. Most models require parallel or comparable training corpora, which limits their ability to generalize. In this paper, we first demystify the knowledge transfer mechanism behind multilingual topic models by defining an alternative but equivalent formulation. Based on this analysis, we then relax the assumption of training data required by most existing models, creating a model that only requires a dictionary for training. Experiments show that our new method effectively learns coherent multilingual topics from partially and fully incomparable corpora with limited amounts of dictionary resources.
Integrated Semi-definite Relaxation Receiver for LDPC-Coded MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

Semi-definite relaxation (SDR) detector has been demonstrated to be successful in approaching maximum likelihood (ML) performance while the time complexity is only polynomial. We propose a new receiver jointly utilizing the forward error correction (FEC) code information in the SDR detection process. Strengthened by code constraints, the joint SDR detector substantially improves the overall receiver performance. For further performance boost, the ML-SDR detector is adapted to MAP-SDR detector by incorporating a priori information in the cost function. Under turbo principle, MAP-SDR detector takes in soft information from decoder and outputs extrinsic information with much improved reliability. We also propose a simplified SDR turbo receiver that solves only one SDR per codeword instead of solving multiple SDRs in the iterative turbo processing. This scheme significantly reduces the time complexity of SDR turbo receiver, while the error performance remains similar as before. In fact, our simplified scheme is generic and it can be applied to any list-based iterative receivers.
Transceiver Design for GFDM with Index Modulation in Multi-user Networks
Venue: arXiv cs.IT 2018
Year: 2018

Index modulation (IM) techniques can be applied to the different media in order to achieve spectral- and energy-efficient communication as well as to the indices of the subcarriers of a generalized frequency division multiplexing (GFDM) data block. In this work, a novel transceiver architecture for multi-user GFDM-IM system is introduced. The performance of the GFDM-IM is studied by considering the bit error rate (BER) as performance metric. It is shown that better BER performance than the classical GFDM and the orthogonal frequency division multiplexing (OFDM) with IM can be achieved by employing IM to the GFDM.
Continuous and Orientation-preserving Correspondences via Functional Maps
Venue: arXiv cs.GR 2018
Year: 2018

We propose a method for efficiently computing orientation-preserving and approximately continuous correspondences between non-rigid shapes, using the functional maps framework. We first show how orientation preservation can be formulated directly in the functional (spectral) domain without using landmark or region correspondences and without relying on external symmetry information. This allows us to obtain functional maps that promote orientation preservation, even when using descriptors, that are invariant to orientation changes. We then show how higher quality, approximately continuous and bijective pointwise correspondences can be obtained from initial functional maps by introducing a novel refinement technique that aims to simultaneously improve the maps both in the spectral and spatial domains. This leads to a general pipeline for computing correspondences between shapes that results in high-quality maps, while admitting an efficient optimization scheme. We show through extensive evaluation that our approach improves upon state-of-the-art results on challenging isometric and non-isometric correspondence benchmarks according to both measures of continuity and coverage as well as producing semantically meaningful correspondences as measured by the distance to ground truth maps.
Computing directed path-width and directed tree-width of recursively defined digraphs
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we consider the directed path-width and directed tree-width of recursively defined digraphs. As an important combinatorial tool, we show how the directed path-width and the directed tree-width can be computed for the disjoint union, order composition, directed union, and series composition of two directed graphs. These results imply the equality of directed path-width and directed tree-width for all digraphs which can be defined by these four operations. This allows us to show a linear-time solution for computing the directed path-width and directed tree-width of all these digraphs. Since directed co-graphs are precisely those digraphs which can be defined by the disjoint union, order composition, and series composition our results imply the equality of directed path-width and directed tree-width for directed co-graphs and also a linear-time solution for computing the directed path-width and directed tree-width of directed co-graphs, which generalizes the known results for undirected co-graphs of Bodlaender and Moehring.
Colwell's Castle Defence: A Custom Game Using Dynamic Difficulty Adjustment to Increase Player Enjoyment
Venue: arXiv cs.HC 2018
Year: 2018

Dynamic Difficulty Adjustment (DDA) is a mechanism used in video games that automatically tailors the individual gaming experience to match an appropriate difficulty setting. This is generally achieved by removing pre-defined difficulty tiers such as Easy, Medium and Hard; and instead concentrates on balancing the gameplay to match the challenge to the individual's abilities. The work presented in this paper examines the implementation of DDA in a custom survival game developed by the author, namely Colwell's Castle Defence. The premise of this arcade-style game is to defend a castle from hordes of oncoming enemies. The AI system that we developed adjusts the enemy spawn rate based on the current performance of the player. Specifically, we read the Player Health and Gate Health at the end of each level and then assign the player with an appropriate difficulty tier for the proceeding level. We tested the impact of our technique on thirty human players and concluded, based on questionnaire feedback, that enabling the technique led to more enjoyable gameplay.
Second Language Acquisition Modeling: An Ensemble Approach
Venue: arXiv cs.CL 2018
Year: 2018

Accurate prediction of students knowledge is a fundamental building block of personalized learning systems. Here, we propose a novel ensemble model to predict student knowledge gaps. Applying our approach to student trace data from the online educational platform Duolingo we achieved highest score on both evaluation metrics for all three datasets in the 2018 Shared Task on Second Language Acquisition Modeling. We describe our model and discuss relevance of the task compared to how it would be setup in a production environment for personalized education.
Automatic Target Recovery for Hindi-English Code Mixed Puns
Venue: arXiv cs.CL 2018
Year: 2018

In order for our computer systems to be more human-like, with a higher emotional quotient, they need to be able to process and understand intrinsic human language phenomena like humour. In this paper, we consider a subtype of humour - puns, which are a common type of wordplay-based jokes. In particular, we consider code-mixed puns which have become increasingly mainstream on social media, in informal conversations and advertisements and aim to build a system which can automatically identify the pun location and recover the target of such puns. We first study and classify code-mixed puns into two categories namely intra-sentential and intra-word, and then propose a four-step algorithm to recover the pun targets for puns belonging to the intra-sentential category. Our algorithm uses language models, and phonetic similarity-based features to get the desired results. We test our approach on a small set of code-mixed punning advertisements, and observe that our system is successfully able to recover the targets for 67% of the puns.