OpenRaiser/Intern-Atlas huggingface dataset:
Incomplete Nested Dissection
Venue: arXiv cs.DS 2018
Year: 2018

We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticity problems, and can be viewed as extensions of graph Laplacians into higher dimensions. Faster solvers for the 2-D variants of such systems have been studied using generalizations of tools for solving graph Laplacians [Daitch-Spielman CSC'07, Shklarski-Toledo SIMAX'08]. Given a 3-dimensional truss over $n$ vertices which is formed from a union of $k$ convex structures (tetrahedral meshes) with bounded aspect ratios, whose individual tetrahedrons are also in some sense well-conditioned, our algorithm solves a linear system in the associated stiffness matrix up to accuracy $ε$ in time $O(k^{1/3} n^{5/3} \log (1 / ε))$. This asymptotically improves the running time $O(n^2)$ by Nested Dissection for all $k \ll n$. We also give a result that improves on Nested Dissection even when we allow any aspect ratio for each of the $k$ convex structures (but we still require well-conditioned individual tetrahedrons). In this regime, we improve on Nested Dissection for $k \ll n^{1/44}$. The key idea of our algorithm is to combine nested dissection and support theory. Both of these techniques for solving linear systems are well studied, but usually separately. Our algorithm decomposes a 3-dimensional truss into separate and balanced regions with small boundaries. We then bound the spectrum of each such region separately, and utilize such bounds to obtain improved algorithms by preconditioning with partial states of separator-based Gaussian elimination.
Complex Relations in a Deep Structured Prediction Model for Fine Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Many deep learning architectures for semantic segmentation involve a Fully Convolutional Neural Network (FCN) followed by a Conditional Random Field (CRF) to carry out inference over an image. These models typically involve unary potentials based on local appearance features computed by FCNs, and binary potentials based on the displacement between pixels. We show that while current methods succeed in segmenting whole objects, they perform poorly in situations involving a large number of object parts. We therefore suggest incorporating into the inference algorithm additional higher-order potentials inspired by the way humans identify and localize parts. We incorporate two relations that were shown to be useful to human object identification - containment and attachment - into the energy term of the CRF and evaluate their performance on the Pascal VOC Parts dataset. Our experimental results show that the segmentation of fine parts is positively affected by the addition of these two relations, and that the segmentation of fine parts can be further influenced by complex structural features.
Simple and practical algorithms for $\ell_p$-norm low-rank approximation
Venue: arXiv cs.LG 2018
Year: 2018

We propose practical algorithms for entrywise $\ell_p$-norm low-rank approximation, for $p = 1$ or $p = \infty$. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approximations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain $(1 + \varepsilon)$-OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desiderata only assuming algorithm's hyperparameters are known a priori---or are at least approximable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46].
Energy Efficient Delay Sensitive Optimization in SWIPT-MIMO
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we consider joint antenna selection and optimal beamforming for energy efficient delay minimization. We assume multiple-input multi-output (MIMO) system with full duplex simultaneous wireless information and power transfer (FD-SWIPT) where each sensor is equipped with a power splitting (PS) system and can simultaneously receive both energy and information from the aggregator (AGG). We show that the antenna selection and beamforming power control policies are adaptive to the energy state information (ESI), the queue state information (QSI) and the channel state information (CSI). We develop an analytical framework for energy efficient delay-optimal control problem based on the theory of infinite horizon partially observable Markov decision process (POMDP). The infinite-horizon POMDP problem is transformed into an equivalent value Bellman program and solved by near-optimal point-based Heuristic Search Value Iteration (PB-HSVI) method under specific standard conditions. The proposed solution outcome is a set of sub-optimal antenna selection and beamforming control policies. Simulation results reveal an effective trade-off between the contradictory objectives (i.e. delay and power consumption) and show the enhancement in delay by using FD-SWIPT systems in comparison to Half Duplex (HD)-SWIPT systems.
WSD algorithm based on a new method of vector-word contexts proximity calculation via epsilon-filtration
Venue: arXiv cs.IR 2018
Year: 2018

The problem of word sense disambiguation (WSD) is considered in the article. Given a set of synonyms (synsets) and sentences with these synonyms. It is necessary to select the meaning of the word in the sentence automatically. 1285 sentences were tagged by experts, namely, one of the dictionary meanings was selected by experts for target words. To solve the WSD-problem, an algorithm based on a new method of vector-word contexts proximity calculation is proposed. In order to achieve higher accuracy, a preliminary epsilon-filtering of words is performed, both in the sentence and in the set of synonyms. An extensive program of experiments was carried out. Four algorithms are implemented, including a new algorithm. Experiments have shown that in a number of cases the new algorithm shows better results. The developed software and the tagged corpus have an open license and are available online. Wiktionary and Wikisource are used. A brief description of this work can be viewed in slides (https://goo.gl/9ak6Gt). Video lecture in Russian on this research is available online (https://youtu.be/-DLmRkepf58).
Coarse-to-fine Seam Estimation for Image Stitching
Venue: arXiv cs.CV 2018
Year: 2018

Seam-cutting and seam-driven techniques have been proven effective for handling imperfect image series in image stitching. Generally, seam-driven is to utilize seam-cutting to find a best seam from one or finite alignment hypotheses based on a predefined seam quality metric. However, the quality metrics in most methods are defined to measure the average performance of the pixels on the seam without considering the relevance and variance among them. This may cause that the seam with the minimal measure is not optimal (perception-inconsistent) in human perception. In this paper, we propose a novel coarse-to-fine seam estimation method which applies the evaluation in a different way. For pixels on the seam, we develop a patch-point evaluation algorithm concentrating more on the correlation and variation of them. The evaluations are then used to recalculate the difference map of the overlapping region and reestimate a stitching seam. This evaluation-reestimation procedure iterates until the current seam changes negligibly comparing with the previous seams. Experiments show that our proposed method can finally find a nearly perception-consistent seam after several iterations, which outperforms the conventional seam-cutting and other seam-driven methods.
Vehicular Communication Networks in Automated Driving Era
Venue: arXiv cs.NI 2018
Year: 2018

Embedded with advanced sensors, cameras and processors, the emerging automated driving vehicles are capable of sensing the environment and conducting automobile operation, paving the way to modern intelligent transportation systems (ITS) with high safety and efficiency. On the other hand, vehicular communication networks (VCNs) connect vehicles, infrastructures, clouds, and all other devices with communication modules, whereby vehicles can obtain local and global information to make intelligent operation decisions. Although the sensing-based automated driving technologies and VCNs have been investigated independently, their interactions and mutual benefits are still underdeveloped. In this article, we argue that VCNs have attractive potentials to enhance the on-board sensing-based automated vehicles from different perspectives, such as driving safety, transportation efficiency, as well as customer experiences. A case study is conducted to demonstrate that the traffic jam can be relieved at intersections with automated driving vehicles coordinated with each other through VCNs. Furthermore, we highlight the critical yet interesting issues for future research, based on the specific requirements posed by automated driving on VCNs.
Evaluating Non-Motorized Transport Popularity of Urban Roads by Sports GPS Tracks
Venue: arXiv cs.CY 2018
Year: 2018

Non-motorized transport is becoming increasingly important in urban development of cities in China. How to evaluate the non-motorized transport popularity of urban roads is an interesting question to study. The great amount of tracking data generated by smart mobile devices give us opportunities to solve this problem. This study aims to provide a data driven method for evaluating the popularity (walkability and bikeability) of urban non-motorized transport system. This paper defines a p-index to evaluate the popular degree of road segments which is based on the cycling, running, and walking GPS track data from outdoor activities logging applications. According to the p-index definition, this paper evaluates the non-motorized transport popularity of urban area in Wuhan city within different temporal periods.
Observation-Enhanced QoS Analysis of Component-Based Systems
Venue: arXiv cs.SE 2018
Year: 2018

We present a new method for the accurate analysis of the quality-of-service (QoS) properties of component-based systems. Our method takes as input a QoS property of interest and a high-level continuous-time Markov chain (CTMC) model of the analysed system, and refines this CTMC based on observations of the execution times of the system components. The refined CTMC can then be analysed with existing probabilistic model checkers to accurately predict the value of the QoS property. The paper describes the theoretical foundation underlying this model refinement, the tool we developed to automate it, and two case studies that apply our QoS analysis method to a service-based system implemented using public web services and to an IT support system at a large university, respectively. Our experiments show that traditional CTMC-based QoS analysis can produce highly inaccurate results and may lead to invalid engineering and business decisions. In contrast, our new method reduced QoS analysis errors by 84.4-89.6% for the service-based system and by 94.7-97% for the IT support system, significantly lowering the risk of such invalid decisions.
Reliable Dispatch of Renewable Generation via Charging of Dynamic PEV Populations
Venue: arXiv cs.SY 2018
Year: 2018

The inherent storage of plug-in electric vehicles is likely to foster the integration of intermittent generation from renewable energy sources into existing power systems. In the present paper, we propose a three-stage scheme to the end of achieving dispatchability of a system composed of plug-in electric vehicles and intermittent generation. The main difficulties in dispatching such a system are the uncertainties inherent to intermittent generation and the time-varying aggregation of vehicles. We propose to address the former by means of probabilistic forecasts and we approach the latter with separate stage-specific models. Specifically, we first compute a dispatch schedule, using probabilistic forecasts together with an aggregated dynamic model of the system. The power output of the single devices are set subsequently, using deterministic forecasts and device-specific models. We draw upon a simulation study based on real data of generation and vehicle traffic to validate our findings.
When Cultures Meet: Modelling Cross-Cultural Knowledge Spaces
Venue: arXiv cs.HC 2018
Year: 2018

Cross cultural research projects are becoming a norm in our global world. More and more projects are being executed using teams from eastern and western cultures. Cultural competence might help project managers to achieve project goals and avoid potential risks in cross cultural project environments and would also support them to promote creativity and motivation through flexible leadership. In our paper we introduce an idea for constructing an information system, a cross cultural knowledge space, which could support cross cultural communication, collaborative learning experiences and time based project management functions. The case cultures in our project are Finnish and Japanese. The system can be used both in virtual and in physical spaces for example to clarify cultural business etiquette. The core of our system design will be based on cross cultural ontology, and the system implementation on XML technologies. Our approach is a practical, step by step example of constructive research. In our paper we shortly describe Hofstede's dimensions for assessing cultures as one example of a larger framework for our study. We also discuss the concept of time in cultural context.
An infinite-server queueing model MMAPkGk in semi-Markov random environment with marked MAP arrival and subject to catastrophes
Venue: arXiv cs.PF 2018
Year: 2018

In the present paper the infinite-server MMAPkGk queueing model with random resource vector of customers, marked MAP arrival and semi-Markov (SM) arrival of catastrophes is considered. The joint generating functions (PGF) of transient and stationary distributions of number of busy servers and numbers of different types served customers, as well as Laplace transformations (LT) of joint distributions of total accumulated resources in the model at moment and total accumulated resources of served customers during time interval are found. The basic differential and renewal equations for transient and stationary PGF of queue sizes of customers are found.
Johnson-Mehl Cell-based Analysis of UL Cellular Network with Coupled User and BS Locations
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we analyze the performance of the uplink (UL) of a cellular network where the base station (BS) locations follow a homogeneous Poisson point process (PPP), and the locations of users and BSs are spatially coupled. In order to capture this coupling, we consider that users attached to a BS are located uniformly at random independently of each other in the Johnson-Mehl (JM) cell of that BS. For this system model, we derive analytical expressions for the UL signal to interference ratio (SIR) coverage probability and average spectral efficiency (SE) of a typical user in the network. One of the key intermediate steps in our analysis is the approximate, but accurate, characterization of the area distribution of a typical JM cell. Another key intermediate step is the accurate statistical characterization of the point process formed by the interfering users that subsequently enables the coverage probability analysis. We present coverage probability and SE results for a typical user and study the interplay between different system parameters.
Detecting Homoglyph Attacks with a Siamese Neural Network
Venue: arXiv cs.CR 2018
Year: 2018

A homoglyph (name spoofing) attack is a common technique used by adversaries to obfuscate file and domain names. This technique creates process or domain names that are visually similar to legitimate and recognized names. For instance, an attacker may create malware with the name svch0st.exe so that in a visual inspection of running processes or a directory listing, the process or file name might be mistaken as the Windows system process svchost.exe. There has been limited published research on detecting homoglyph attacks. Current approaches rely on string comparison algorithms (such as Levenshtein distance) that result in computationally heavy solutions with a high number of false positives. In addition, there is a deficiency in the number of publicly available datasets for reproducible research, with most datasets focused on phishing attacks, in which homoglyphs are not always used. This paper presents a fundamentally different solution to this problem using a Siamese convolutional neural network (CNN). Rather than leveraging similarity based on character swaps and deletions, this technique uses a learned metric on strings rendered as images: a CNN learns features that are optimized to detect visual similarity of the rendered strings. The trained model is used to convert thousands of potentially targeted process or domain names to feature vectors. These feature vectors are indexed using randomized KD-Trees to make similarity searches extremely fast with minimal computational processing. This technique shows a considerable 13% to 45% improvement over baseline techniques in terms of area under the receiver operating characteristic curve (ROC AUC). In addition, we provide both code and data to further future research.
The detection of professional fraud in automobile insurance using social network analysis
Venue: arXiv cs.SI 2018
Year: 2018

The Automobile Insurance Fraud is one of the main challenges for insurance companies. This form of fraud is performed either opportunistic or professional occurring through group cooperation that leads to greater financial losses, while most presented methods thus far are unsuited for flagging these groups. The article has put forward a new approach for identification, representation, and analysis of organized fraudulent groups in automobile insurance through focusing on structural aspects of networks, and cycles in particular, that demonstrate the occurrence of potential fraud. Suspicious groups have been detected by applying cycle detection algorithms (using both DFS, BFS trees), afterward, the probability of being fraudulent for suspicious components were investigated to reveal fraudulent groups with the maximum likelihood, and their reviews were prioritized. The actual data of Iran Insurance Company is used for evaluating the provided approach. As a result, the detection of cycles is not only more efficient, accurate, but also less time-consuming in comparison with previous methods for finding such groups.
Semi-Random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
Venue: arXiv cs.DS 2018
Year: 2018

The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph are a $O(\sqrt{\log n})$-approximation algorithm due to Feige, Hajiaghayi and Lee [SIAM J. Comp., 2008], and $O(\sqrt{OPT \log d})$ bound in graphs having vertex degrees at most $d$, due to Louis, Raghavendra and Vempala [FOCS 2013]. We study a natural semi-random model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bi-criteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph. In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semi-random graphs with planted sparse edge cuts. To the best of our knowledge, our model of semi-random graphs with planted sparse vertex cuts has not been studied before.
Geographical Hidden Markov Tree for Flood Extent Mapping (With Proof Appendix)
Venue: arXiv cs.LG 2018
Year: 2018

Flood extent mapping plays a crucial role in disaster management and national water forecasting. Unfortunately, traditional classification methods are often hampered by the existence of noise, obstacles and heterogeneity in spectral features as well as implicit anisotropic spatial dependency across class labels. In this paper, we propose geographical hidden Markov tree, a probabilistic graphical model that generalizes the common hidden Markov model from a one dimensional sequence to a two dimensional map. Anisotropic spatial dependency is incorporated in the hidden class layer with a reverse tree structure. We also investigate computational algorithms for reverse tree construction, model parameter learning and class inference. Extensive evaluations on both synthetic and real world datasets show that proposed model outperforms multiple baselines in flood mapping, and our algorithms are scalable on large data sizes.
Modular Decomposition of Graphs and the Distance Preserving Property
Venue: arXiv cs.DM 2018
Year: 2018

Given a graph $G$, a subgraph $H$ is isometric if $d_H(u,v) = d_G(u,v)$ for every pair $u,v\in V(H)$, where $d$ is the distance function. A graph $G$ is distance preserving (dp) if it has an isometric subgraph of every possible order. A graph is sequentially distance preserving (sdp) if its vertices can be ordered such that deleting the first $i$ vertices results in an isometric subgraph, for all $i\ge1$. We introduce a generalisation of the lexicographic product of graphs, which can be used to non-trivially describe graphs. This generalisation is the inverse of the modular decomposition of graphs, which divides the graph into disjoint clusters called modules. Using these operations, we give a necessary and sufficient condition for graphs to be dp. Finally, we show that the Cartesian product of a dp graph and an sdp graph is dp.
Fast Neural Machine Translation Implementation
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes the submissions to the efficiency track for GPUs at the Workshop for Neural Machine Translation and Generation by members of the University of Edinburgh, Adam Mickiewicz University, Tilde and University of Alicante. We focus on efficient implementation of the recurrent deep-learning model as implemented in Amun, the fast inference engine for neural machine translation. We improve the performance with an efficient mini-batching algorithm, and by fusing the softmax operation with the k-best extraction algorithm. Submissions using Amun were first, second and third fastest in the GPU efficiency track.
Meta Transfer Learning for Facial Emotion Recognition
Venue: arXiv cs.CV 2018
Year: 2018

The use of deep learning techniques for automatic facial expression recognition has recently attracted great interest but developed models are still unable to generalize well due to the lack of large emotion datasets for deep learning. To overcome this problem, in this paper, we propose utilizing a novel transfer learning approach relying on PathNet and investigate how knowledge can be accumulated within a given dataset and how the knowledge captured from one emotion dataset can be transferred into another in order to improve the overall performance. To evaluate the robustness of our system, we have conducted various sets of experiments on two emotion datasets: SAVEE and eNTERFACE. The experimental results demonstrate that our proposed system leads to improvement in performance of emotion recognition and performs significantly better than the recent state-of-the-art schemes adopting fine-\ tuning/pre-trained approaches.