April 2, 2020

3100 words 15 mins read

Paper Group ANR 385

Rolling Horizon Evolutionary Algorithms for General Video Game Playing. Deep Multi-Facial Patches Aggregation Network For Facial Expression Recognition. Word Sense Disambiguation for 158 Languages using Word Embeddings Only. Bounded Incentives in Manipulating the Probabilistic Serial Rule. Learning Whole-body Motor Skills for Humanoids. A Finite St …

Rolling Horizon Evolutionary Algorithms for General Video Game Playing


Title	Rolling Horizon Evolutionary Algorithms for General Video Game Playing
Authors	Raluca D. Gaina, Sam Devlin, Simon M. Lucas, Diego Perez-Liebana
Abstract	Game-playing Evolutionary Algorithms, specifically Rolling Horizon Evolutionary Algorithms, have recently managed to beat the state of the art in performance across many games. However, the best results per game are highly dependent on the specific configuration of modifications and hybrids introduced over several works, each described as parameters in the algorithm. However, the search for the best parameters has been reduced to several human-picked combinations, as the possibility space has grown beyond exhaustive search. This paper presents the state of the art in Rolling Horizon Evolutionary algorithms, combining all modifications described in literature and some additional ones for a large resultant hybrid. It then uses a parameter optimiser, the N-Tuple Bandit Evolutionary Algorithm, to find the best combination of parameters in 20 games with various properties from the General Video Game AI Framework. We highlight the noisy optimisation problem resultant, as both the games and the algorithm being optimised are stochastic. We then analyse the algorithm’s parameters and interesting combinations revealed through the parameter optimisation process. Lastly, we show that it is possible to automatically explore a large parameter space and find configurations which outperform the state of the art on several games.
Tasks
Published	2020-03-27
URL	https://arxiv.org/abs/2003.12331v1
PDF	https://arxiv.org/pdf/2003.12331v1.pdf
PWC	https://paperswithcode.com/paper/rolling-horizon-evolutionary-algorithms-for
Repo
Framework

Deep Multi-Facial Patches Aggregation Network For Facial Expression Recognition


Title	Deep Multi-Facial Patches Aggregation Network For Facial Expression Recognition
Authors	Ahmed Rachid Hazourli, Amine Djeghri, Hanan Salam, Alice Othmani
Abstract	In this paper, we propose an approach for Facial Expressions Recognition (FER) based on a deep multi-facial patches aggregation network. Deep features are learned from facial patches using deep sub-networks and aggregated within one deep architecture for expression classification . Several problems may affect the performance of deep-learning based FER approaches, in particular, the small size of existing FER datasets which might not be sufficient to train large deep learning networks. Moreover, it is extremely time-consuming to collect and annotate a large number of facial images. To account for this, we propose two data augmentation techniques for facial expression generation to expand FER labeled training datasets. We evaluate the proposed framework on three FER datasets. Results show that the proposed approach achieves state-of-art FER deep learning approaches performance when the model is trained and tested on images from the same dataset. Moreover, the proposed data augmentation techniques improve the expression recognition rate, and thus can be a solution for training deep learning FER models using small datasets. The accuracy degrades significantly when testing for dataset bias.
Tasks	Data Augmentation, Facial Expression Recognition
Published	2020-02-20
URL	https://arxiv.org/abs/2002.09298v1
PDF	https://arxiv.org/pdf/2002.09298v1.pdf
PWC	https://paperswithcode.com/paper/deep-multi-facial-patches-aggregation-network
Repo
Framework

Word Sense Disambiguation for 158 Languages using Word Embeddings Only


Title	Word Sense Disambiguation for 158 Languages using Word Embeddings Only
Authors	Varvara Logacheva, Denis Teslenko, Artem Shelmanov, Steffen Remus, Dmitry Ustalov, Andrey Kutuzov, Ekaterina Artemova, Chris Biemann, Simone Paolo Ponzetto, Alexander Panchenko
Abstract	Disambiguation of word senses in context is easy for humans, but is a major challenge for automatic approaches. Sophisticated supervised and knowledge-based models were developed to solve this task. However, (i) the inherent Zipfian distribution of supervised training instances for a given word and/or (ii) the quality of linguistic knowledge representations motivate the development of completely unsupervised and knowledge-free approaches to word sense disambiguation (WSD). They are particularly useful for under-resourced languages which do not have any resources for building either supervised and/or knowledge-based models. In this paper, we present a method that takes as input a standard pre-trained word embedding model and induces a fully-fledged word sense inventory, which can be used for disambiguation in context. We use this method to induce a collection of sense inventories for 158 languages on the basis of the original pre-trained fastText word embeddings by Grave et al. (2018), enabling WSD in these languages. Models and system are available online.
Tasks	Word Embeddings, Word Sense Disambiguation
Published	2020-03-14
URL	https://arxiv.org/abs/2003.06651v1
PDF	https://arxiv.org/pdf/2003.06651v1.pdf
PWC	https://paperswithcode.com/paper/word-sense-disambiguation-for-158-languages
Repo
Framework

Bounded Incentives in Manipulating the Probabilistic Serial Rule


Title	Bounded Incentives in Manipulating the Probabilistic Serial Rule
Authors	Zihe Wang, Zhide Wei, Jie Zhang
Abstract	The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not incentive-compatible, thereby these desirable properties only hold for the agents’ declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is $\frac{3}{2}$. That is, no agent can misreport its preferences such that its utility becomes more than 1.5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents’ reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agent’s utility gain on average by experiments. The experiments show that an agent’ incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible.
Tasks
Published	2020-01-28
URL	https://arxiv.org/abs/2001.10640v1
PDF	https://arxiv.org/pdf/2001.10640v1.pdf
PWC	https://paperswithcode.com/paper/bounded-incentives-in-manipulating-the
Repo
Framework

Learning Whole-body Motor Skills for Humanoids


Title	Learning Whole-body Motor Skills for Humanoids
Authors	Chuanyu Yang, Kai Yuan, Wolfgang Merkt, Taku Komura, Sethu Vijayakumar, Zhibin Li
Abstract	This paper presents a hierarchical framework for Deep Reinforcement Learning that acquires motor skills for a variety of push recovery and balancing behaviors, i.e., ankle, hip, foot tilting, and stepping strategies. The policy is trained in a physics simulator with realistic setting of robot model and low-level impedance control that are easy to transfer the learned skills to real robots. The advantage over traditional methods is the integration of high-level planner and feedback control all in one single coherent policy network, which is generic for learning versatile balancing and recovery motions against unknown perturbations at arbitrary locations (e.g., legs, torso). Furthermore, the proposed framework allows the policy to be learned quickly by many state-of-the-art learning algorithms. By comparing our learned results to studies of preprogrammed, special-purpose controllers in the literature, self-learned skills are comparable in terms of disturbance rejection but with additional advantages of producing a wide range of adaptive, versatile and robust behaviors.
Tasks
Published	2020-02-07
URL	https://arxiv.org/abs/2002.02991v1
PDF	https://arxiv.org/pdf/2002.02991v1.pdf
PWC	https://paperswithcode.com/paper/learning-whole-body-motor-skills-for
Repo
Framework

A Finite State Transducer Based Morphological Analyzer of Maithili Language


Title	A Finite State Transducer Based Morphological Analyzer of Maithili Language
Authors	Raza Rahi, Sumant Pushp, Arif Khan, Smriti Kumar Sinha
Abstract	Morphological analyzers are the essential milestones for many linguistic applications like; machine translation, word sense disambiguation, spells checkers, and search engines etc. Therefore, development of an effective morphological analyzer has a greater impact on the computational recognition of a language. In this paper, we present a finite state transducer based inflectional morphological analyzer for a resource poor language of India, known as Maithili. Maithili is an eastern Indo-Aryan language spoken in the eastern and northern regions of Bihar in India and the southeastern plains, known as tarai of Nepal. This work can be recognized as the first work towards the computational development of Maithili which may attract researchers around the country to up-rise the language to establish in computational world.
Tasks	Machine Translation, Word Sense Disambiguation
Published	2020-02-29
URL	https://arxiv.org/abs/2003.00234v1
PDF	https://arxiv.org/pdf/2003.00234v1.pdf
PWC	https://paperswithcode.com/paper/a-finite-state-transducer-based-morphological
Repo
Framework

Minimum adjusted Rand index for two clusterings of a given size


Title	Minimum adjusted Rand index for two clusterings of a given size
Authors	José E. Chacón, Ana I. Rastrojo
Abstract	In an unpublished presentation, Steinley reported that the minimum adjusted Rand index for the comparison of two clusterings of size $r$ is $-1/r$. However, in a subsequent paper Chac'on noted that this apparent bound can be lowered. Here, it is shown that the lower bound proposed by Chac'on is indeed the minimum possible one. The result is even more general, since it is valid for two clusterings of possibly different sizes.
Tasks
Published	2020-02-10
URL	https://arxiv.org/abs/2002.03677v1
PDF	https://arxiv.org/pdf/2002.03677v1.pdf
PWC	https://paperswithcode.com/paper/minimum-adjusted-rand-index-for-two
Repo
Framework

Adversarial Robustness on In- and Out-Distribution Improves Explainability


Title	Adversarial Robustness on In- and Out-Distribution Improves Explainability
Authors	Maximilian Augustin, Alexander Meinke, Matthias Hein
Abstract	Neural networks have led to major improvements in image classification but suffer from being non-robust to adversarial changes, unreliable uncertainty estimates on out-distribution samples and their inscrutable black-box decisions. In this work we propose RATIO, a training procedure for Robustness via Adversarial Training on In- and Out-distribution, which leads to robust models with reliable and robust confidence estimates on the out-distribution. RATIO has similar generative properties to adversarial training so that visual counterfactuals produce class specific features. While adversarial training comes at the price of lower clean accuracy, RATIO achieves state-of-the-art $l_2$-adversarial robustness on CIFAR10 and maintains better clean accuracy.
Tasks	Image Classification
Published	2020-03-20
URL	https://arxiv.org/abs/2003.09461v1
PDF	https://arxiv.org/pdf/2003.09461v1.pdf
PWC	https://paperswithcode.com/paper/adversarial-robustness-on-in-and-out
Repo
Framework

Isolation Mondrian Forest for Batch and Online Anomaly Detection


Title	Isolation Mondrian Forest for Batch and Online Anomaly Detection
Authors	Haoran Ma, Benyamin Ghojogh, Maria N. Samad, Dongyu Zheng, Mark Crowley
Abstract	We propose a new method, named isolation Mondrian forest (iMondrian forest), for batch and online anomaly detection. The proposed method is a novel hybrid of isolation forest and Mondrian forest which are existing methods for batch anomaly detection and online random forest, respectively. iMondrian forest takes the idea of isolation, using the depth of a node in a tree, and implements it in the Mondrian forest structure. The result is a new data structure which can accept streaming data in an online manner while being used for anomaly detection. Our experiments show that iMondrian forest mostly performs better than isolation forest in batch settings and has better or comparable performance against other batch and online anomaly detection methods.
Tasks	Anomaly Detection
Published	2020-03-08
URL	https://arxiv.org/abs/2003.03692v1
PDF	https://arxiv.org/pdf/2003.03692v1.pdf
PWC	https://paperswithcode.com/paper/isolation-mondrian-forest-for-batch-and
Repo
Framework

Fast Rates for Online Prediction with Abstention


Title	Fast Rates for Online Prediction with Abstention
Authors	Gergely Neu, Nikita Zhivotovskiy
Abstract	In the setting of sequential prediction of individual ${0, 1}$-sequences with expert advice, we show that by allowing the learner to abstain from the prediction by paying a cost marginally smaller than $\frac 12$ (say, $0.49$), it is possible to achieve expected regret bounds that are independent of the time horizon $T$. We exactly characterize the dependence on the abstention cost $c$ and the number of experts $N$ by providing matching upper and lower bounds of order $\frac{\log N}{1-2c}$, which is to be contrasted with the best possible rate of $\sqrt{T\log N}$ that is available without the option to abstain. We also discuss various extensions of our model, including a setting where the sequence of abstention costs can change arbitrarily over time, where we show regret bounds interpolating between the slow and the fast rates mentioned above, under some natural assumptions on the sequence of abstention costs.
Tasks
Published	2020-01-28
URL	https://arxiv.org/abs/2001.10623v1
PDF	https://arxiv.org/pdf/2001.10623v1.pdf
PWC	https://paperswithcode.com/paper/fast-rates-for-online-prediction-with
Repo
Framework

CRATOS: Cognition of Reliable Algorithm for Time-series Optimal Solution


Title	CRATOS: Cognition of Reliable Algorithm for Time-series Optimal Solution
Authors	Ziling Wu, Ping Liu, Zheng Hu, Jun Wang
Abstract	Anomaly detection of time series plays an important role in reliability systems engineering. However, in practical application, there is no precisely defined boundary between normal and anomalous behaviors in different application scenarios. Therefore, different anomaly detection algorithms and processes ought to be adopted for time series in different situation. Although such strategy improve the accuracy of anomaly detection, it takes a lot of time for engineers to configure millions of different algorithms to different series, which greatly increases the development and maintenance cost of anomaly detection processes. In this paper, we propose CRATOS which is a self-adapt algorithms that extract features for time series, and then cluster series with similar features into one group. For each group we utilize evolution algorithm to search the best anomaly detection methods and processes. Our methods can significantly reduce the cost of development and maintenance. According to our experiments, our clustering methods achieves the state-of-art results. Compared with the accuracy (93.4%) of the anomaly detection algorithms that engineers configure for different time series manually, our algorithms is not far behind in detecting accuracy (85.1%).
Tasks	Anomaly Detection, Time Series
Published	2020-03-03
URL	https://arxiv.org/abs/2003.01412v2
PDF	https://arxiv.org/pdf/2003.01412v2.pdf
PWC	https://paperswithcode.com/paper/cratos-cogination-of-reliable-algorithm-for
Repo
Framework

Multi-Participant Multi-Class Vertical Federated Learning


Title	Multi-Participant Multi-Class Vertical Federated Learning
Authors	Siwei Feng, Han Yu
Abstract	Federated learning (FL) is a privacy-preserving paradigm for training collective machine learning models with locally stored data from multiple participants. Vertical federated learning (VFL) deals with the case where participants sharing the same sample ID space but having different feature spaces, while label information is owned by one participant. Current studies of VFL only support two participants, and mostly focus on binaryclass logistic regression problems. In this paper, we propose the Multi-participant Multi-class Vertical Federated Learning (MMVFL) framework for multi-class VFL problems involving multiple parties. Extending the idea of multi-view learning (MVL), MMVFL enables label sharing from its owner to other VFL participants in a privacypreserving manner. To demonstrate the effectiveness of MMVFL, a feature selection scheme is incorporated into MMVFL to compare its performance against supervised feature selection and MVL-based approaches. Experiment results on real-world datasets show that MMVFL can effectively share label information among multiple VFL participants and match multi-class classification performance of existing approaches.
Tasks	Feature Selection, MULTI-VIEW LEARNING
Published	2020-01-30
URL	https://arxiv.org/abs/2001.11154v1
PDF	https://arxiv.org/pdf/2001.11154v1.pdf
PWC	https://paperswithcode.com/paper/multi-participant-multi-class-vertical
Repo
Framework

Efficient convolutional neural networks for multi-planar lung nodule detection: improvement on small nodule identification


Title	Efficient convolutional neural networks for multi-planar lung nodule detection: improvement on small nodule identification
Authors	Sunyi Zheng, Ludo J. Cornelissen, Xiaonan Cui, Xueping Jing, Raymond N. J. Veldhuis, Matthijs Oudkerk, Peter M. A. van Ooijen
Abstract	We propose a multi-planar pulmonary nodule detection system using convolutional neural networks. The 2-D convolutional neural network model, U-net++, was trained by axial, coronal, and sagittal slices for the candidate detection task. All possible nodule candidates from the three different planes are combined. For false positive reduction, we apply 3-D multi-scale dense convolutional neural networks to efficiently remove false positive candidates. We use the public LIDC-IDRI dataset which includes 888 CT scans with 1186 nodules annotated by four radiologists. After ten-fold cross-validation, our proposed system achieves a sensitivity of 95.3% with 0.5 false positive/scan and a sensitivity of 96.2% with 1.0 false positive/scan. Although it is difficult to detect small nodules (i.e. nodules with a diameter < 6 mm), our designed CAD system reaches a sensitivity of 93.8% (94.6%) of these small nodules at an overall false positive rate of 0.5 (1.0) false positives/scan. At the nodule candidate detection stage, the proposed system detected 98.1% of nodules after merging the predictions from all three planes. Using only the 1 mm axial slices resulted in the detection of 91.1% of nodules, which is better than that of utilizing solely the coronal or sagittal slices. The results show that a multi-planar method is capable to detect more nodules compared to using a single plane. Our approach achieves state-of-the-art performance on this dataset, which demonstrates the effectiveness and efficiency of our developed CAD system for lung nodule detection.
Tasks	Lung Nodule Detection
Published	2020-01-13
URL	https://arxiv.org/abs/2001.04537v1
PDF	https://arxiv.org/pdf/2001.04537v1.pdf
PWC	https://paperswithcode.com/paper/efficient-convolutional-neural-networks-for-4
Repo
Framework

Semi-supervised Classification using Attention-based Regularization on Coarse-resolution Data


Title	Semi-supervised Classification using Attention-based Regularization on Coarse-resolution Data
Authors	Guruprasad Nayak, Rahul Ghosh, Xiaowei Jia, Varun Mithal, Vipin Kumar
Abstract	Many real-world phenomena are observed at multiple resolutions. Predictive models designed to predict these phenomena typically consider different resolutions separately. This approach might be limiting in applications where predictions are desired at fine resolutions but available training data is scarce. In this paper, we propose classification algorithms that leverage supervision from coarser resolutions to help train models on finer resolutions. The different resolutions are modeled as different views of the data in a multi-view framework that exploits the complementarity of features across different views to improve models on both views. Unlike traditional multi-view learning problems, the key challenge in our case is that there is no one-to-one correspondence between instances across different views in our case, which requires explicit modeling of the correspondence of instances across resolutions. We propose to use the features of instances at different resolutions to learn the correspondence between instances across resolutions using an attention mechanism.Experiments on the real-world application of mapping urban areas using satellite observations and sentiment classification on text data show the effectiveness of the proposed methods.
Tasks	MULTI-VIEW LEARNING, Sentiment Analysis
Published	2020-01-03
URL	https://arxiv.org/abs/2001.00994v1
PDF	https://arxiv.org/pdf/2001.00994v1.pdf
PWC	https://paperswithcode.com/paper/semi-supervised-classification-using
Repo
Framework

DiPE: Deeper into Photometric Errors for Unsupervised Learning of Depth and Ego-motion from Monocular Videos


Title	DiPE: Deeper into Photometric Errors for Unsupervised Learning of Depth and Ego-motion from Monocular Videos
Authors	Hualie Jiang, Laiyan Ding, Rui Huang
Abstract	Unsupervised learning of depth and ego-motion from unlabelled monocular videos has recently drawn attention as it has notable advantages than the supervised ones. It uses the photometric errors between the target view and the synthesized views from its adjacent source views as the loss. Although significant progress has been made, the learning still suffers from occlusion and scene dynamics. This paper shows that carefully manipulating photometric errors can tackle these difficulties better. The primary improvement is achieved by masking out the invisible or nonstationary pixels in the photometric error map using a statistical technique. With this outlier masking approach, the depth of objects that move in the opposite direction to the camera can be estimated more accurately. According to our best knowledge, such objects have not been seriously considered in the previous work, even though they pose a higher risk in applications like autonomous driving. We also propose an efficient weighted multi-scale scheme to reduce the artifacts in the predicted depth maps. Extensive experiments on the KITTI dataset show the effectiveness of the proposed approaches. The overall system achieves state-of-the-art performance on both depth and ego-motion estimation.
Tasks	Autonomous Driving, Motion Estimation
Published	2020-03-03
URL	https://arxiv.org/abs/2003.01360v1
PDF	https://arxiv.org/pdf/2003.01360v1.pdf
PWC	https://paperswithcode.com/paper/dipe-deeper-into-photometric-errors-for
Repo
Framework