title: L0-norm Constrained Autoencoders for Unsupervised Outlier Detection

text: Unsupervised outlier detection is commonly performed using reconstruction-based methods such as Principal Component Analysis. A recent problem in this field is the learning of low-dimensional nonlinear manifolds under L0-norm constraints for error terms. Despite significant efforts, no method that consistently treats such features exists. We propose a novel unsupervised outlier detection method, L0-norm Constrained Autoencoders (L0-AE), based on an autoencoder-based detector with L0-norm constraints for error terms. Unlike existing methods, the proposed optimization procedure of L0-AE provably guarantees the convergence of the objective function under a mild condition, while neither the relaxation of the L0-norm constraint nor the linearity of the latent manifold is enforced. Experimental results show that the proposed L0-AE is more robust and accurate than other reconstruction-based methods, as well as conventional methods such as Isolation Forest.


docid: iioqkydg

title: Protecting IP of Deep Neural Networks with Watermarking: A New Label Helps

text: Deep neural network (DNN) models have shown great success in almost every artificial area. It is a non-trivial task to build a good DNN model. Nowadays, various MLaaS providers have launched their cloud services, which trains DNN models for users. Once they are released, driven by potential monetary profit, the models may be duplicated, resold, or redistributed by adversaries, including greedy service providers themselves. To mitigate this threat, in this paper, we propose an innovative framework to protect the intellectual property of deep learning models, that is, watermarking the model by adding a new label to crafted key samples during training. The intuition comes from the fact that, compared with existing DNN watermarking methods, adding a new label will not twist the original decision boundary but can help the model learn the features of key samples better. We implement a prototype of our framework and evaluate the performance under three different benchmark datasets, and investigate the relationship between model accuracy, perturbation strength, and key samples’ length. Extensive experimental results show that, compared with the existing schemes, the proposed method performs better under small perturbation strength or short key samples’ length in terms of classification accuracy and ownership verification efficiency.


docid: xixmzqzn

title: Level Set Estimation with Search Space Warping

text: This paper proposes a new method of level set estimation through search space warping using Bayesian optimisation. Instead of a single solution, a level set offers a range of solutions each meeting the goal and thus provides useful knowledge in tolerance for industrial product design. The proposed warping scheme increases performance of existing level set estimation algorithms - in particular the ambiguity acquisition function. This is done by constructing a complex covariance function to warp the Gaussian Process. The covariance function is designed to expand regions deemed to have a high potential for being at the desired level whilst contracting others. Subsequently, Bayesian optimisation using this covariance function ensures that the level set is sampled more thoroughly. Experimental results demonstrate increased efficiency of level set discovery using the warping scheme. Theoretical analysis concerning warping the covariance function, maximum information gain and bounds on the cumulative regret are provided.


title: Balancing Between Accuracy and Fairness for Interactive Recommendation with Reinforcement Learning

text: Fairness in recommendation has attracted increasing attention due to bias and discrimination possibly caused by traditional recommenders. In Interactive Recommender Systems (IRS), user preferences and the system’s fairness status are constantly changing over time. Existing fairness-aware recommenders mainly consider fairness in static settings. Directly applying existing methods to IRS will result in poor recommendation. To resolve this problem, we propose a reinforcement learning based framework, FairRec, to dynamically maintain a long-term balance between accuracy and fairness in IRS. User preferences and the system’s fairness status are jointly compressed into the state representation to generate recommendations. FairRec aims at maximizing our designed cumulative reward that combines accuracy and fairness. Extensive experiments validate that FairRec can improve fairness, while preserving good recommendation quality.


title: Inferring Restricted Regular Expressions with Interleaving from Positive and Negative Samples

text: The presence of a schema for XML documents has numerous advantages. Unfortunately, many XML documents in practice are not accompanied by a schema or a valid schema. Therefore, it is essential to devise algorithms to infer schemas. The fundamental task in XML schema inference is to learn regular expressions. In this paper, we focus on learning the subclass of RE(&) called SIREs (the subclass of regular expressions with interleaving). Previous work in this direction lacks inference algorithms that support inference from positive and negative examples. We provide an algorithm to learn SIREs from positive and negative examples based on genetic algorithms and parallel techniques. Our algorithm also has better expansibility, which means that our algorithm not only supports learning with positive and negative examples, but also supports learning with positive or negative examples only. Experimental results demonstrate the effectiveness of our algorithm.


title: Adversarial Autoencoder and Multi-Task Semi-Supervised Learning for Multi-stage Process

text: In selection processes, decisions follow a sequence of stages. Early stages have more applicants and general information, while later stages have fewer applicants but specific data. This is represented by a dual funnel structure, in which the sample size decreases from one stage to the other while the information increases. Training classifiers for this case is challenging. In the early stages, the information may not contain distinct patterns to learn, causing underfitting. In later stages, applicants have been filtered out and the small sample can cause overfitting. We redesign the multi-stage problem to address both cases by combining adversarial autoencoders (AAE) and multi-task semi-supervised learning (MTSSL) to train an end-to-end neural network for all stages together. The AAE learns the representation of the data and performs data imputation in missing values. The generated dataset is fed to an MTSSL mechanism that trains all stages together, encouraging related tasks to contribute to each other using a temporal regularization structure. Using real-world data, we show that our approach outperforms other state-of-the-art methods with a gain of 4x over the standard case and a 12% improvement over the second-best method.


title: Negative Sampling for Hyperlink Prediction in Networks

text: While graphs capture pairwise relations between entities, hypergraphs deal with higher-order ones, thereby ensuring losslessness. However, in hyperlink (i.e., higher-order link) prediction, where hyperlinks and non-hyperlinks are treated as “positive” and “negative” classes respectively, hypergraphs suffer from the problem of extreme class imbalance. Given this context, “negative sampling”—under-sampling the negative class of non-hyperlinks—becomes mandatory for performing hyperlink prediction. No prior work on hyperlink prediction deals with this problem. In this work, which is the first of its kind, we deal with this problem in the context of hyperlink prediction. More specifically, we leverage graph sampling techniques for sampling non-hyperlinks in hyperlink prediction. Our analysis clearly establishes the effect of random sampling, which is the norm in both link- as well as hyperlink-prediction. Further, we formalize the notion of “hardness” of non-hyperlinks via a measure of density, and analyze its distribution over various negative sampling techniques. We experiment with some real-world hypergraph datasets and provide both qualitative and quantitative results on the effects of negative sampling. We also establish its importance in evaluating hyperlink prediction algorithms.


title: Bottom-Up and Top-Down Graph Pooling

text: Pooling layers are crucial components for efficient deep representation learning. As to graph data, however, it’s not trivial to decide which nodes to retain in order to represent the high-level structure of a graph. Recently many different graph pooling methods have been proposed. However, they all rely on local features to conduct global pooling over all nodes, which contradicts poolings in CNNs that only use local features to conduct local pooling. We analyze why this may hinder the performance of graph pooling, then propose a novel graph pooling method called Bottom-Up and Top-Down graph POOLing (BUTDPool). BUTDPool aims to learn a more fine-grained pooling criterion based on coarse global structure information produced by a bottom-up pooling layer, and can enhance local features with global features. Specifically, we propose to use one or multiple pooling layers with a relatively high retain ratio to produce a coarse high-level graph. Injecting the high-level information back into low-level representation, BUTDPool enhances learning a better pooling criterion. Experiments demonstrate the superior performance of the proposed method over compared methods.


title: Joint Relational Dependency Learning for Sequential Recommendation

text: Sequential recommendation leverages the temporal information of users’ transactions as transition dependencies for better inferring user preference, which has become increasingly popular in academic research and practical applications. Short-term transition dependencies contain the information of partial item orders, while long-term transition dependencies infer long-range user preference, the two dependencies are mutually restrictive and complementary. Although some work investigates unifying both long-term and short-term dependencies for better performance, they still neglect the fact that short-term interactions are multi-folds, which are either individual-level interactions or union-level interactions. Existing sequential recommendations mainly focus on user’s individual (i.e., individual-level) interactions but ignore the important collective influence at union-level. Since union-level interactions can reflect that human decisions are made based on multiple items he/she has already interacted, ignoring such interactions can result in the disability of capturing the collective influence between items. To alleviate this issue, we proposed a Joint Relational Dependency learning (JRD-L) for sequential recommendation that exploits both long-term and short-term preferences at individual-level and union-level. Specifically, JRD-L combines long-term user preferences with short-term interests by measuring short-term pair relations at individual-level and union-level. Moreover, JRD-L can alleviate the sparsity problem of union-level interactions by adding more descriptive details to each item, which is carried by individual-level relations. Extensive numerical experiments demonstrate JRD-L outperforms state-of-the-art baselines for the sequential recommendation.


title: dK-Microaggregation: Anonymizing Graphs with Differential Privacy Guarantees

text: With the advances of graph analytics, preserving privacy in publishing graph data becomes an important task. However, graph data is highly sensitive to structural changes. Perturbing graph data for achieving differential privacy inevitably leads to inject a large amount of noise and the utility of anonymized graphs is severely limited. In this paper, we propose a microaggregation-based framework for graph anonymization which meets the following requirements: (1) The topological structures of an original graph can be preserved at different levels of granularity; (2) [Formula: see text]-differential privacy is guaranteed for an original graph through adding controlled perturbation to its edges (i.e., edge privacy); (3) The utility of graph data is enhanced by reducing the magnitude of noise needed to achieve [Formula: see text]-differential privacy. Within the proposed framework, we further develop a simple yet effective microaggregation algorithm under a distance constraint. We have empirically verified the noise reduction and privacy guarantee of our proposed algorithm on three real-world graph datasets. The experiments show that our proposed framework can significantly reduce noise added to achieve [Formula: see text]-differential privacy over graph data, and thus enhance the utility of anonymized graphs.


title: MIRD-Net for Medical Image Segmentation

text: Medical image segmentation is a fundamental and challenging problem for analyzing medical images due to the approximate pixel values of adjacent tissues in boundary and the non-linear feature between pixels. Although fully convolutional neural networks such as U-Net has demonstrated impressive performance on medical image segmentation, distinguishing subtle features between different categories after pooling layers is still a difficult task, which affects the segmentation accuracy. In this paper, we propose a Mini-Inception-Residual-Dense (MIRD) network named MIRD-Net to deal with this problem. The key point of our proposed MIRD-Net is MIRD Block. It takes advantage of Inception, Residual Block (RB) and Dense Block (DB), aiming to make the network obtain more features to help improve the segmentation accuracy. There is no pooling layer in MIRD-Net. Such a design avoids loss of information during forward propagation. Experimental results show that our framework significantly outperforms U-Net in six different image segmentation tasks and its parameters are only about 1/50 of U-Net.


title: Quality-Aware Streaming Network Embedding with Memory Refreshing

text: Static network embedding has been widely studied to convert sparse structure information into a dense latent space. However, the majority of real networks are continuously evolving, and deriving the whole embedding for every snapshot is computationally intensive. To avoid recomputing the embedding over time, we explore streaming network embedding for two reasons: 1) to efficiently identify the nodes required to update the embeddings under multi-type network changes, and 2) to carefully revise the embeddings to maintain transduction over different parts of the network. Specifically, we propose a new representation learning framework, named Graph Memory Refreshing (GMR), to preserve both global types of structural information efficiently. We prove that GMR maintains the consistency of embeddings (crucial for network analysis) for isomorphic structures better than existing approaches. Experimental results demonstrate that GMR outperforms the baselines with much smaller time.


title: Drug-Disease Graph: Predicting Adverse Drug Reaction Signals via Graph Neural Network with Clinical Data

text: Adverse Drug Reaction (ADR) is a significant public health concern world-wide. Numerous graph-based methods have been applied to biomedical graphs for predicting ADRs in pre-marketing phases. ADR detection in post-market surveillance is no less important than pre-marketing assessment, and ADR detection with large-scale clinical data have attracted much attention in recent years. However, there are not many studies considering graph structures from clinical data for detecting an ADR signal, which is a pair of a prescription and a diagnosis that might be a potential ADR. In this study, we develop a novel graph-based framework for ADR signal detection using healthcare claims data. We construct a Drug-disease graph with nodes representing the medical codes. The edges are given as the relationships between two codes, computed using the data. We apply Graph Neural Network to predict ADR signals, using labels from the Side Effect Resource database. The model shows improved AUROC and AUPRC performance of 0.795 and 0.775, compared to other algorithms, showing that it successfully learns node representations expressive of those relationships. Furthermore, our model predicts ADR pairs that do not exist in the established ADR database, showing its capability to supplement the ADR database.


docid: hhqkibpv

title: Mining Locally Trending High Utility Itemsets

text: High utility itemset mining consists of identifying all the sets of items that appear together and yield a high profit in a customer transaction database. Recently, this problem was extended to discover trending high utility itemsets (itemsets that yield an increasing or decreasing profit over time). However, an important limitation of that problem is that it is assumed that trends remain stable over time. But in real-life, trends may change in different time intervals due to specific events. To identify time intervals where itemsets have increasing/decreasing trends in terms of utility, this paper proposes the problem of mining Locally Trending High Utility Itemsets (LTHUIs) and their Trending High Utility Periods (THUPs). Properties of the problem are studied and an efficient algorithm named LTHUI-Miner is proposed to enumerate all the LTHUIs and their THUPs. An experimental evaluation shows that the algorithm is efficient and can discover insightful patterns not found by previous algorithms.


title: Strong Baselines for Author Name Disambiguation with and Without Neural Networks

text: Author name disambiguation (AND) is one of the most vital problems in scientometrics, which has become a great challenge with the rapid growth of academic digital libraries. Existing approaches for this task substantially rely on complex clustering-like architectures, and they usually assume the number of clusters is known beforehand or predict the number by applying another model, which involve increasingly complex and time-consuming architectures. In this paper, we combine simple neural networks with two sets of heuristic rules to explore strong baselines for the author name disambiguation problem without any priori knowledge or estimation about cluster size, which frees the model from unnecessary complexity. On a popular benchmark dataset AMiner, our solution significantly outperforms several state-of-the-art methods both in performance and efficiency, and it still achieves comparable performance with many complex models when only using a group of rules. Experimental results also indicate that gains from sophisticated deep learning techniques are quite modest in the author name disambiguation problem.


title: Role Equivalence Attention for Label Propagation in Graph Neural Networks

text: Semi-supervised relational learning methods aim to classify nodes in a partially-labeled graph. While popular, existing methods using Graph Neural Networks (GNN) for semi-supervised relational learning have mainly focused on learning node representations by aggregating nearby attributes, and it is still challenging to leverage inferences about unlabeled nodes with few attributes—particularly when trying to exploit higher-order relationships in the network efficiently. To address this, we propose a Graph Neural Network architecture that incorporates patterns among the available class labels and uses (1) a Role Equivalence attention mechanism and (2) a mini-batch importance sampling method to improve efficiency when learning over high-order paths. In particular, our Role Equivalence attention mechanism is able to use nodes’ roles to learn how to focus on relevant distant neighbors, in order to adaptively reduce the increased noise that occurs when higher-order structures are considered. In experiments on six different real-world datasets, we show that our model (REGNN) achieves significant performance gains compared to other recent state-of-the-art baselines, particularly when higher-order paths are considered in the models.


title: Modelling Temporal Dynamics and Repeated Behaviors for Recommendation

text: Personalized recommendation has yield immense success in predicting user preference with heterogeneous implicit feedback (HIF), i.e., various user behaviors. However, existing studies consider less about the temporal dynamics and repeated patterns of HIF. They simply suppose: (1) a hard rule among user behaviors (e.g., add-to-cart must come before purchase and after view); (2) merge repeated behaviors into one (e.g., view several times is considered as view once only), thus failing to unveil user preferences from their real behaviors. To ease these issues, we, therefore, propose a novel end-to-end neural framework – TDRB, which automatically models the Temporal Dynamics and Repeated Behaviors to assist in capturing user preference, thus achieving more accurate recommendations. Empirical studies on three real-world datasets demonstrate the superiority of our proposed TDRB against other state-of-the-arts.


title: Fusion-Extraction Network for Multimodal Sentiment Analysis

text: Multiple modality data bring new challenges for sentiment analysis, as combining varieties of information in an effective manner is a rigorous task. Previous works do not effectively utilize the relationship and influence between texts and images. This paper proposes a fusion-extraction network model for multimodal sentiment analysis. First, our model uses an interactive information fusion mechanism to interactively learn the visual-specific textual representations and the textual-specific visual representations. Then, we propose an information extraction mechanism to extract valid information and filter redundant parts for the specific textual and visual representations. The experimental results on two public multimodal sentiment datasets show that our model outperforms existing state-of-the-art methods.


title: Hierarchical Gradient Smoothing for Probability Estimation Trees

text: Decision trees are still seeing use in online, non-stationary and embedded contexts, as well as for interpretability. For applications like ranking and cost-sensitive classification, probability estimation trees (PETs) are used. These are built using smoothing or calibration techniques. Older smoothing techniques used counts local to a leaf node, but a few more recent techniques consider the broader context of a node when doing estimation. We apply a recent advanced smoothing method called Hierarchical Dirichlet Process (HDP) to PETs, and then propose a novel hierarchical smoothing approach called Hierarchical Gradient Smoothing (HGS) as an alternative. HGS smooths leaf nodes up to all the ancestors, instead of recursively smoothing to the parent used by HDP. HGS is made faster by efficiently optimizing the Leave-One-Out Cross-Validation (LOOCV) loss measure using gradient descent, instead of sampling used in HDP. An extensive set of experiments are conducted on 143 datasets showing that our HGS estimates are not only more accurate but also do so within a fraction of HDP time. Besides, HGS makes a single tree almost as good as a Random Forest with 10 trees. For applications that require more interpretability and efficiency, a single decision tree plus HGS is more preferred.


title: Online Algorithms for Multiclass Classification Using Partial Labels

text: In this paper, we propose online algorithms for multiclass classification using partial labels. We propose two variants of Perceptron called Avg Perceptron and Max Perceptron to deal with the partially labeled data. We also propose Avg Pegasos and Max Pegasos, which are extensions of the Pegasos algorithm. We also provide mistake bounds for Avg Perceptron and regret bound for Avg Pegasos. We show the effectiveness of the proposed approaches by experimenting on various datasets and comparing them with the standard Perceptron and Pegasos. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this chapter (10.1007/978-3-030-47426-3_20) contains supplementary material, which is available to authorized users.


title: AutoSUM: Automating Feature Extraction and Multi-user Preference Simulation for Entity Summarization

text: With the growth of knowledge graphs, entity descriptions are becoming extremely lengthy. Entity summarization task, aiming to generate diverse, comprehensive and representative summaries for entities, has received an increasing interest recently. In most previous methods, features are usually extracted by the hand-crafted templates. Then the feature selection and multi-user preference simulation take place, depending too much on human expertise. In this paper, a novel integration method called AutoSUM is proposed for automatic feature extraction and multi-user preference simulation to overcome the drawbacks of previous methods. There are two modules in AutoSUM: extractor and simulator. The extractor module operates automatic feature extraction based on a BiLSTM with a combined input representation including word embeddings and graph embeddings. Meanwhile, the simulator module automates multi-user preference simulation based on a well-designed two-phase attention mechanism (i.e., entity-phase attention and user-phase attention). Experimental results demonstrate that AutoSUM produces the state-of-the-art performance on two widely used datasets (i.e., DBpedia and LinkedMDB) in both F-measure and MAP.


title: Assessing Centrality Without Knowing Connections

text: We consider the privacy-preserving computation of node influence in distributed social networks, as measured by egocentric betweenness centrality (EBC). Motivated by modern communication networks spanning multiple providers, we show for the first time how multiple mutually-distrusting parties can successfully compute node EBC while revealing only differentially-private information about their internal network connections. A theoretical utility analysis upper bounds a primary source of private EBC error—private release of ego networks—with high probability. Empirical results demonstrate practical applicability with a low 1.07 relative error achievable at strong privacy budget [Formula: see text] on a Facebook graph, and insignificant performance degradation as the number of network provider parties grows. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this chapter (10.1007/978-3-030-47436-2_12) contains supplementary material, which is available to authorized users.


docid: icpuvqds

title: Anomaly Detection via Neighbourhood Contrast

text: Relative scores such as Local Outlying Factor and mass ratio have been shown to be better scores than global scores in detecting anomalies. While this is true, our analysis reveals for the first time that these relative scores have a key shortcoming: anomalies have greatly different relative scores if they are located in different regions where the curvatures of the density surface are very different. As a result, the low-score anomalies could be ranked lower than some normal points. This revelation motivates (i) a new score called Neighbourhood Contrast (NC) which produces approximately the same high scores for all anomalies, regardless of varying curvatures of the density surface in different regions; and (ii) an anomaly detection method based on NC. Our experiments show that the proposed method which employs the new score significantly outperforms methods using the aforementioned relative scores on benchmark datasets.


title: An Empirical Model for n-gram Frequency Distribution in Large Corpora

text: Statistical multiword extraction methods can benefit from the knowledge on the n-gram ([Formula: see text]) frequency distribution in natural language corpora, for indexing and time/space optimization purposes. The appearance of increasingly large corpora raises new challenges on the investigation of the large scale behavior of the n-gram frequency distributions, not typically emerging on small scale corpora. We propose an empirical model, based on the assumption of finite n-gram language vocabularies, to estimate the number of distinct n-grams in large corpora, as well as the sizes of the equal-frequency n-gram groups, which occur in the lower frequencies starting from 1. The model was validated for n-grams with [Formula: see text], by a wide range of real corpora in English and French, from 60 million up to 8 billion words. These are full non-truncated corpora data, that is, their associated frequency data include the entire range of observed n-gram frequencies, from 1 up to the maximum. The model predicts the monotonic growth of the numbers of distinct n-grams until reaching asymptotic plateaux when the corpus size grows to infinity. It also predicts the non-monotonicity of the sizes of the equal-frequency n-gram groups as a function of the corpus size.


title: Long-Term Water Pipe Condition Assessment: A Semiparametric Model Using Gaussian Process and Survival Analysis

text: The maintenance and renewal of water mains demand substantial financial investments, and direct inspection of all water mains in a distribution system is extremely expensive. Therefore, a cost effective break mitigation technique such as a failure forecasting model that allows one to predict the water mains failure likelihood, would reduce the negative social impact and the cost to serve. We introduce a semiparametric Bayesian model for pipeline failure forecasting. The model is centred on a nonparametric Gaussian Process Regression (GPR), and uses a parametric survival model to capture the long-term survival probability using domain knowledge. The parametric element in our model allows the inclusion of survival probability, while the nonparametric part allows us to handle covariates and to employ incomplete prior knowledge about pipe failures. We apply our model to the proactive maintenance problem using a real dataset from a water utility in Australia. The results demonstrate that, our model performs better than competing models such as Support Vector Regression, Poisson regression, Weibull, Gradient Boosting, and GPR, leading to substantial savings on reactive repairs and maintenance. Our water pipeline failure prediction models have been deployed in three states across Australia, and are being monitored by each water authority.


title: Identifying Near-Miss Traffic Incidents in Event Recorder Data

text: Front video and sensor data captured by vehicle-mounted event recorders are used for not only traffic accident evidence but also safe-driving education as near-miss traffic incident data. However, most event recorder (ER) data shows only regular driving events. To utilize near-miss data for safe-driving education, we need to be able to easily and rapidly locate the appropriate data from large amounts of ER data through labels attached to the scenes/events of interest. This paper proposes a method that can automatically identify near-misses with objects such as pedestrians and bicycles by processing the ER data. The proposed method extracts two deep feature representations that consider car status and the environment surrounding the car. The first feature representation is generated by considering the temporal transitions of car status. The second one can extract the positional relationship between the car and surrounding objects by processing object detection results. Experiments on actual ER data demonstrate that the proposed method can accurately identify and tag near-miss events.


title: Semantics-Reconstructing Hashing for Cross-Modal Retrieval

text: Retrieval on Cross-modal data has attracted extensive attention as it enables fast searching across various data sources, such as texts, images and videos. As one of the typical techniques for cross-model searching, hashing methods project features with high dimension into short-length hash codes, thus effectively improving storage and retrieval efficiency. Recently, many efforts have been made to widely study supervised methods with promising performance. However, there still remain some problems. Conventionally, hash codes and projection functions are learnt by preserving the pairwise similarities between data items, which neglects the discriminative property of class associated with each data item. Most of the existing methods that utilise class labels also undertake the binary codes learning under a classification frame. The relations between binary codes and labels have not been well considered. To tackle these problems, we propose a shallow supervised hash learning method – Semantics-reconstructing Cross-modal Hashing (SCH), which reconstructs semantic representation and learns the hash codes for the entire dataset jointly. For the semantic reconstruction, the learned semantic representation is projected back into label space, extracting more semantic information. By leveraging reconstructed semantic representations, the hash codes are learnt by considering the underlying correlations between labels, hash codes and original features, resulting in a further performance improvement. Moreover, SCH learns the hash codes and functions without relaxing the binary constraints simultaneously, therefore, it further reduces the quantization errors. In addition, the linear computational complexity of its training makes it practicable to big data. Extensive experiments show that the proposed SCH can perform better than the state-of-the-art baselines.


title: JPLink: On Linking Jobs to Vocational Interest Types

text: Linking job seekers with relevant jobs requires matching based on not only skills, but also personality types. Although the Holland Code also known as RIASEC has frequently been used to group people by their suitability for six different categories of occupations, the RIASEC category labels of individual jobs are often not found in job posts. This is attributed to significant manual efforts required for assigning job posts with RIASEC labels. To cope with assigning massive number of jobs with RIASEC labels, we propose JPLink, a machine learning approach using the text content in job titles and job descriptions. JPLink exploits domain knowledge available in an occupation-specific knowledge base known as O*NET to improve feature representation of job posts. To incorporate relative ranking of RIASEC labels of each job, JPLink proposes a listwise loss function inspired by learning to rank. Both our quantitative and qualitative evaluations show that JPLink outperforms conventional baselines. We conduct an error analysis on JPLink’s predictions to show that it can uncover label errors in existing job posts.


title: MemMAP: Compact and Generalizable Meta-LSTM Models for Memory Access Prediction

text: With the rise of Big Data, there has been a significant effort in increasing compute power through GPUs, TPUs, and heterogeneous architectures. As a result, many applications are memory bound, i.e., they are bottlenecked by the movement of data from main memory to compute units. One way to address this issue is through data prefetching, which relies on accurate prediction of memory accesses. While recent deep learning models have performed well on sequence prediction problems, they are far too heavy in terms of model size and inference latency to be practical for data prefetching. Here, we propose extremely compact LSTM models that can predict the next memory access with high accuracy. Prior LSTM based work on access prediction has used orders of magnitude more parameters and developed one model for each application (trace). While one (specialized) model per application can result in more accuracy, it is not a scalable approach. In contrast, our models can predict for a class of applications by trading off specialization at the cost of few retraining steps at runtime, for a more generalizable compact meta-model. Our experiments on 13 benchmark applications demonstrate that three compact meta-models can obtain accuracy close to specialized models using few batches of retraining for majority of the applications.


title: ITGH: Information-Theoretic Granger Causal Inference on Heterogeneous Data

text: Granger causality for time series states that a cause improves the predictability of its effect. That is, given two time series x and y, we are interested in detecting the causal relations among them considering the previous observations of both time series. Although, most of the algorithms are designed for causal inference among homogeneous processes where only time series from a specific distribution (mostly Gaussian) are given, many applications generate a mixture of various time series from different distributions. We utilize Generalized Linear Models (GLM) to propose a general information-theoretic framework for causal inference on heterogeneous data sets. We regard the challenge of causality detection as a data compression problem employing the Minimum Description Length (MDL) principle. By balancing the goodness-of-fit and the model complexity we automatically find the causal relations. Extensive experiments on synthetic and real-world data sets confirm the advantages of our algorithm ITGH (for Information-Theoretic Granger causal inference on Heterogeneous data) compared to other algorithms.


title: Attention-Based Graph Evolution

text: Based on the recent success of deep generative models on continuous data, various new methods are being developed to generate discrete data such as graphs. However, these approaches focus on unconditioned generation, which limits their control over the generating procedure to produce graphs in context, thus limiting the applicability to real-world settings. To address this gap, we introduce an attention-based graph evolution model (AGE). AGE is a conditional graph generator based on the neural attention mechanism that can not only model graph evolution in both space and time, but can also model the transformation between graphs from one state to another. We evaluate AGE on multiple conditional graph-generation tasks, and our results show that it can generate realistic graphs conditioned on source graphs, outperforming existing methods in terms of quality and generality.


title: What’s in a Gist? Towards an Unsupervised Gist Representation for Few-Shot Large Document Classification

text: The gist can be viewed as an abstract concept that represents only the quintessential meaning derived from a single or multiple sources of information. We live in an age where vast quantities of information are widely available and easily accessible. Identifying the gist contextualises information which facilitates the fast disambiguation and prediction of related concepts bringing about a set of natural relationships defined between information sources. In this paper, we investigate and introduce a novel unsupervised gist extraction and quantification framework that represents a computational form of the gist based on notions from fuzzy trace theory. To evaluate our purposed framework, we apply the gist to the task of semantic similarity, specifically to few-shot large document classification where documents on average have a large number of words. The results show our proposed gist representation can effectively capture the essential information from a text document while dramatically reducing the features used.


title: Retrofitting Embeddings for Unsupervised User Identity Linkage

text: User Identity Linkage (UIL) is the problem of matching user identities across multiple online social networks (OSNs) which belong to the same person. The solutions to UIL problem facilitate cross-platform research on OSN users and enable many useful applications such as user profiling and recommendation. As the UIL labeled data are often lacking and costly to obtain, learning user embeddings for matching user identities using an unsupervised approach is therefore highly desired. In this paper, we propose a novel unsupervised UIL framework for enhancing existing user embedding-based UIL methods. Our proposed framework incorporates two key ideas, user-discriminative features and retrofitting embedding. The user-discriminative features enable us to differentiate a specific user identity from other users in its OSN. From the user-discriminative features, we derive pairs of similar user identities across OSNs for retrofitting the base user embeddings of existing UIL methods. Through extensive experiments on three real-world OSN datasets, we show that our framework can leverage user-discriminative features to improve the accuracy of different user embedding-based UIL methods significantly. The quantum of improvement can also be surprisingly good even for existing UIL methods with very poor matching accuracy. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this chapter (10.1007/978-3-030-47426-3_30) contains supplementary material, which is available to authorized users.


title: Learning Discriminative Neural Sentiment Units for Semi-supervised Target-Level Sentiment Classification

text: Target-level sentiment classification aims at assigning sentiment polarities to opinion targets in a sentence, for which it is significantly more challenging to obtain large-scale labeled data than sentence/document-level sentiment classification due to the intricate contexts and relations of the target words. To address this challenge, we propose a novel semi-supervised approach to learn sentiment-aware representations from easily accessible unlabeled data specifically for the fine-grained sentiment learning. This is very different from current popular semi-supervised solutions that use the unlabeled data via pretraining to generate generic representations for various types of downstream tasks. Particularly, we show for the first time that we can learn and detect some highly sentiment-discriminative neural units from the unsupervised pretrained model, termed neural sentiment units. Due to the discriminability, these sentiment units can be leveraged by downstream LSTM-based classifiers to generate sentiment-aware and context-dependent word representations to substantially improve their sentiment classification performance. Extensive empirical results on two benchmark datasets show that our approach (i) substantially outperforms state-of-the-art sentiment classifiers and (ii) achieves significantly better data efficiency.


title: Optimal Topology Search for Fast Model Averaging in Decentralized Parallel SGD

text: Distributed training of deep learning models on high-latency systems necessitates decentralized parallel SGD solutions. However, existing solutions suffer from slow convergence because of hand-crafted topologies. The question arises, “for decentralized parallel SGD, is it possible to learn a topology that provides faster model averaging compared to the hand-crafted counterparts?”. By leveraging spectral properties of the graph, we formulate the objective function for finding the topology that provides fast model averaging. Since direct optimization of the objective function is infeasible, we employ a local search algorithm guided by the objective function. We show through extensive empirical evaluation on image classification tasks that the model averaging based on learned topologies leads to fast convergence. An equally important aspect of the decentralized parallel SGD is the link weights for sparse model averaging. In contrast to setting weights via Metropolis-Hastings, we propose to use Laplacian link weights on the learned topologies, which provide a significant lift in performance.


title: MsFcNET: Multi-scale Feature-Crossing Attention Network for Multi-field Sparse Data

text: Feature engineering usually needs to excavate dense-and-implicit cross features from multi-filed sparse data. Recently, many state-of-the-art models have been proposed to achieve low-order and high-order feature interactions. However, most of them ignore the importance of cross features and fail to suppress the negative impact of useless features. In this paper, a novel multi-scale feature-crossing attention network (MsFcNET) is proposed to extract dense-and-implicit cross features and learn their importance in the different scales. The model adopts the DIA-LSTM units to construct a new attention calibration architecture, which can adaptively adjust the weights of features in the process of feature interactions. On the other hand, it also integrates a multi-scale feature-crossing module to strengthen the representation ability of cross features from multi-field sparse data. The extensive experimental results on three real-world prediction datasets demonstrate that our proposed model yields superior performance compared with the other state-of-the-art models.


title: Multi-view Deep Gaussian Process with a Pre-training Acceleration Technique

text: Deep Gaussian process (DGP) is one of the popular probabilistic modeling methods, which is powerful and widely used for function approximation and uncertainty estimation. However, the traditional DGP lacks consideration for multi-view cases in which data may come from different sources or be constructed by different types of features. In this paper, we propose a generalized multi-view DGP (MvDGP) to capture the characteristics of different views and model data in different views discriminately. In order to make the proposed model more efficient in training, we introduce a pre-training network in MvDGP and incorporate stochastic variational inference for fine-tuning. Experimental results on real-world data sets demonstrate that pre-trained MvDGP outperforms the state-of-the-art DGP models and deep neural networks, achieving higher computational efficiency than other DGP models.


title: Correlation Matters: Multi-scale Fine-Grained Contextual Information Extraction for Hepatic Tumor Segmentation

text: Automatic tumor segmentation has been used as a diagnostic aid in the identification of diseases such as tumors from liver CT scans, and their treatment. Owing to their success in computer vision tasks, the state-of-the-art Fully Convolutional Networks (FCNs) or U-Net based models have often been employed in many recent studies for automatic tumor segmentation to learn numerous weight-shared convolutional kernels and extract various semantic features. However, the correlation between different tumor regions in feature maps cannot be easily captured due to the lack of contextual dependencies, which in turn limits the representative capability of the adopted models and thus affects the accuracy of tumor segmentation results. To resolve this issue, we propose a novel framework for segmentation of tumors in liver CT scans, which can explicitly extract multi-scale fine-grained contextual information by adaptively aggregating local features with their global dependencies. The proposed multi-scale framework features a light model with a very few additional parameters, and also its visualization capability significantly boosts networks’ interpretability. Experimental results on a real-world liver tumor CT dataset illustrate that the proposed framework achieves the state-of-the-art performance in terms of a number of widely used evaluation criteria for the hepatic tumor segmentation task.


title: Hydrological Process Surrogate Modelling and Simulation with Neural Networks

text: Environmental sustainability is a major concern for urban and rural development. Actors and stakeholders need economic, effective and efficient simulations in order to predict and evaluate the impact of development on the environment and the constraints that the environment imposes on development. Numerical simulation models are usually computation expensive and require expert knowledge. We consider the problem of hydrological modelling and simulation. With a training set consisting of pairs of inputs and outputs from an off-the-shelves simulator, We show that a neural network can learn a surrogate model effectively and efficiently and thus can be used as a surrogate simulation model. Moreover, we argue that the neural network model, although trained on some example terrains, is generally capable of simulating terrains of different sizes and spatial characteristics.


title: Correlation-Aware Deep Generative Model for Unsupervised Anomaly Detection

text: Unsupervised anomaly detection aims to identify anomalous samples from highly complex and unstructured data, which is pervasive in both fundamental research and industrial applications. However, most existing methods neglect the complex correlation among data samples, which is important for capturing normal patterns from which the abnormal ones deviate. In this paper, we propose a method of Correlation aware unsupervised Anomaly detection via Deep Gaussian Mixture Model (CADGMM), which captures the complex correlation among data points for high-quality low-dimensional representation learning. More specifically, the relations among data samples are correlated firstly in forms of a graph structure, in which, the node denotes the sample and the edge denotes the correlation between two samples from the feature space. Then, a dual-encoder that consists of a graph encoder and a feature encoder, is employed to encode both the feature and correlation information of samples into the low-dimensional latent space jointly, followed by a decoder for data reconstruction. Finally, a separate estimation network as a Gaussian Mixture Model is utilized to estimate the density of the learned latent vector, and the anomalies can be detected by measuring the energy of the samples. Extensive experiments on real-world datasets demonstrate the effectiveness of the proposed method.


title: Using Bandits for Effective Database Activity Monitoring

text: Database activity monitoring systems aim to protect organizational data by logging users’ activity to Identify and document malicious activity. High-velocity streams and operating costs, restrict these systems to examining only a sample of the activity. Current solutions use manual policies to decide which transactions to monitor. This limits the diversity of the data collected, creating a “filter bubble” over representing specific subsets of the data such as high-risk users and under-representing the rest of the population which may never be sampled. In recommendation systems, Bandit algorithms have recently been used to address this problem. We propose addressing the sampling for database activity monitoring problem as a recommender system. In this work, we redefine the data sampling problem as a special case of the multi-armed bandit problem and present a novel algorithm, C–[Formula: see text]–Greedy, which combines expert knowledge with random exploration. We analyze the effect of diversity on coverage and downstream event detection using simulated data. In doing so, we find that adding diversity to the sampling using the bandit-based approach works well for this task, maximizing population coverage without decreasing the quality in terms of issuing alerts about events, and outperforming policies manually crafted by experts and other sampling methods.


title: Fast Community Detection with Graph Sparsification

text: A popular model for detecting community structure in large graphs is the Stochastic Block Model (SBM). The exact parameters to recover the community structure of a SBM has been well studied, and many methods have been proposed to recover a nodes’ community membership. A popular approach is to use spectral methods where the Graph Laplacian L of the given graph is created, and the Fiedler vector of the graph is found. This vector is then used to cluster nodes in the same community. While a robust method, it can be expensive to compute the Fiedler vector exactly. In this paper we examine the types of errors that can be tolerated using spectral methods while still recovering the communities. The two sources of error considered are: (i) dropping edges using different sparsification strategies; and (ii) inaccurately computing the eigenvectors. In this way, spectral clustering algorithms can be tuned to be far more efficient at detecting community structure for these community models.


title: Data Centers Job Scheduling with Deep Reinforcement Learning

text: Efficient job scheduling on data centers under heterogeneous complexity is crucial but challenging since it involves the allocation of multi-dimensional resources over time and space. To adapt the complex computing environment in data centers, we proposed an innovative Advantage Actor-Critic (A2C) deep reinforcement learning based approach called A2cScheduler for job scheduling. A2cScheduler consists of two agents, one of which, dubbed the actor, is responsible for learning the scheduling policy automatically and the other one, the critic, reduces the estimation error. Unlike previous policy gradient approaches, A2cScheduler is designed to reduce the gradient estimation variance and to update parameters efficiently. We show that the A2cScheduler can achieve competitive scheduling performance using both simulated workloads and real data collected from an academic data center.


docid: bahqogxm

title: PhosTransfer: A Deep Transfer Learning Framework for Kinase-Specific Phosphorylation Site Prediction in Hierarchy

text: Machine learning algorithms have been widely used for predicting kinase-specific phosphorylation sites. However, the scarcity of training data for specific kinases makes it difficult to train effective models for predicting their phosphorylation sites. In this paper, we propose a deep transfer learning framework, PhosTransfer, for improving kinase-specific phosphorylation site prediction. It banks on the hierarchical information encoded in the kinase classification tree (KCT) which involves four levels: kinase groups, families, subfamilies and protein kinases (PKs). With PhosTransfer, predictive models associated with tree nodes at higher levels, which are trained with more sufficient training data, can be transferred and reused as feature extractors for predictive models of tree nodes at a lower level. Out results indicate that models with deep transfer learning out-performed those without transfer learning for 73 out of 79 tested PKs. The positive effect of deep transfer learning is better demonstrated in the prediction of phosphosites for kinase nodes with less training data. These improved performances are further validated and explained by the visualisation of vector representations generated from hidden layers pre-trained at different KCT levels. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this chapter (10.1007/978-3-030-47436-2_29) contains supplementary material, which is available to authorized users.


title: A Distributed Coordinate Descent Algorithm for Learning Factorization Machine

text: Although much effort has been made to implement Factorization Machine (FM) on distributed frameworks, most of them achieve bad model performance or low efficiency. In this paper, we propose a new distributed block coordinate descent algorithm to learn FM. In addition, a distributed pre-computation mechanism incorporated with an optimized Parameter Server framework is designed to avoid the massive repetitive calculations and further reduce the communication cost. Systematically, we evaluate the proposed distributed algorithm on three different genres of datasets for prediction. The experimental results show that the proposed algorithm achieves significantly better performance (3.8%–6.0% RMSE) than the state-of-the-art baselines, and also achieves a 4.6–12.3[Formula: see text] speedup when reaching a comparable performance.


title: On the Performance of Oversampling Techniques for Class Imbalance Problems

text: Although over 90 oversampling approaches have been developed in the imbalance learning domain, most of the empirical study and application work are still based on the “classical” resampling techniques. In this paper, several experiments on 19 benchmark datasets are set up to study the efficiency of six powerful oversampling approaches, including both “classical” and new ones. According to our experimental results, oversampling techniques that consider the minority class distribution (new ones) perform better in most cases and RACOG gives the best performance among the six reviewed approaches. We further validate our conclusion on our real-world inspired vehicle datasets and also find applying oversampling techniques can improve the performance by around 10%. In addition, seven data complexity measures are considered for the initial purpose of investigating the relationship between data complexity measures and the choice of resampling techniques. Although no obvious relationship can be abstracted in our experiments, we find F1v value, a measure for evaluating the overlap which most researchers ignore, has a strong negative correlation with the potential AUC value (after resampling).


title: Deep Cost-Sensitive Kernel Machine for Binary Software Vulnerability Detection

text: Owing to the sharp rise in the severity of the threats imposed by software vulnerabilities, software vulnerability detection has become an important concern in the software industry, such as the embedded systems industry, and in the field of computer security. Software vulnerability detection can be carried out at the source code or binary level. However, the latter is more impactful and practical since when using commercial software, we usually only possess binary software. In this paper, we leverage deep learning and kernel methods to propose the Deep Cost-sensitive Kernel Machine, a method that inherits the advantages of deep learning methods in efficiently tackling structural data and kernel methods in learning the characteristic of vulnerable binary examples with high generalization capacity. We conduct experiments on two real-world binary datasets. The experimental results have shown a convincing outperformance of our proposed method over the baselines.


title: Efficient Database Search via Tensor Distribution Bucketing

text: In mass spectrometry-based proteomics, one needs to search billions of mass spectra against the human proteome with billions of amino acids, where many of the amino acids go through post-translational modifications. In order to account for novel modifications, we need to search all the spectra against all the peptides using a joint probabilistic model that can be learned from training data. Assuming M spectra and N possible peptides, currently the state of the art search methods have runtime of O(MN). Here, we propose a novel bucketing method that sends pairs with high likelihood under the joint probabilistic model to the same bucket with higher probability than those pairs with low likelihood. We demonstrate that the runtime of this method grows sub-linearly with the data size, and our results show that our method is orders of magnitude faster than methods from the locality sensitive hashing literature. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this chapter (10.1007/978-3-030-47436-2_26) contains supplementary material, which is available to authorized users.


title: A Proximity Weighted Evidential k Nearest Neighbor Classifier for Imbalanced Data

text: In k Nearest Neighbor (kNN) classifier, a query instance is classified based on the most frequent class of its nearest neighbors among the training instances. In imbalanced datasets, kNN becomes biased towards the majority instances of the training space. To solve this problem, we propose a method called Proximity weighted Evidential kNN classifier. In this method, each neighbor of a query instance is considered as a piece of evidence from which we calculate the probability of class label given feature values to provide more preference to the minority instances. This is then discounted by the proximity of the neighbor to prioritize the closer instances in the local neighborhood. These evidences are then combined using Dempster-Shafer theory of evidence. A rigorous experiment over 30 benchmark imbalanced datasets shows that our method performs better compared to 12 popular methods. In pairwise comparison of these 12 methods with our method, in the best case, our method wins in 29 datasets, and in the worst case it wins in least 19 datasets. More importantly, according to Friedman test the proposed method ranks higher than all other methods in terms of AUC at 5% level of significance.


title: Optimal Subgroup Discovery in Purely Numerical Data

text: Subgroup discovery in labeled data is the task of discovering patterns in the description space of objects to find subsets of objects whose labels show an interesting distribution, for example the disproportionate representation of a label value. Discovering interesting subgroups in purely numerical data - attributes and target label - has received little attention so far. Existing methods make use of discretization methods that lead to a loss of information and suboptimal results. This is the case for the reference algorithm SD-Map*. We consider here the discovery of optimal subgroups according to an interestingness measure in purely numerical data. We leverage the concept of closed interval patterns and advanced enumeration and pruning techniques. The performances of our algorithm are studied empirically and its added-value w.r.t. SD-Map* is illustrated.


docid: muivhebw

title: Tendi: Tensor Disaggregation from Multiple Coarse Views

text: Multidimensional data appear in various interesting applications, e.g., sales data indexed by stores, items, and time. Oftentimes, data are observed aggregated over multiple data atoms, thus exhibit low resolution. Temporal aggregation is most common, but many datasets are also aggregated over other attributes. Multidimensional data, in particular, are sometimes available in multiple coarse views, aggregated across different dimensions – especially when sourced by different agencies. For instance, item sales can be aggregated temporally, and over groups of stores based on their location or affiliation. However, data in finer granularity significantly benefit forecasting and data analytics, prompting increasing interest in data disaggregation methods. In this paper, we propose Tendi, a principled model that efficiently disaggregates multidimensional (tensor) data from multiple views, aggregated over different dimensions. Tendi employs coupled tensor factorization to fuse the multiple views and provide recovery guarantees under realistic conditions. We also propose a variant of Tendi, called TendiB, which performs the disaggregation task without any knowledge of the aggregation mechanism. Experiments on real data from different domains demonstrate the high effectiveness of the proposed methods.


The authors reply


title: Amplifying Panic and Facilitating Prevention: Multifaceted Effects of Traditional and Social Media Use During the 2015 MERS Crisis in South Korea

text: In the context of the 2015 Middle East respiratory syndrome (MERS) outbreak in South Korea, this study examines the multifaceted effects of media use considering the current complex media environment. Analysis of a two-wave online panel survey found that traditional media use had a positive influence on MERS knowledge while social media use did not. However, knowledge did not facilitate preventive behaviors. In contrast, negative emotional responses due to media use stimulated desirable behaviors. Furthermore, social media use directly influenced behavioral responses but traditional media use did not show the same effects. Different functions of traditional and social media during an epidemic are discussed.


title: A discourse analysis of Ebola in South African newspapers (2014–2015)

text: The 2014 Ebola outbreak in three African states transformed the virus into a social reality in which media representations contributed to globalised hysteria and had rhetorical effects. This study investigated representations of the Ebola virus/disease in South African news reports (March 2014–June 2015). Four discourses were found to operate within the globalised social context: threat to humanity, predation, invasion, and conspiracy. The South African reportage framed Ebola as a predator and criminal rather than using stock warfare imagery. Representations indicated alignment with phobic high-income countries and colonial hegemony.


title: Community Analysis of a Crisis Response Network

text: This article distinguishes between clique family subgroups and communities in a crisis response network. Then, we examine the way organizations interacted to achieve a common goal by employing community analysis of an epidemic response network in Korea in 2015. The results indicate that the network split into two groups: core response communities in one group and supportive functional communities in the other. The core response communities include organizations across government jurisdictions, sectors, and geographic locations. Other communities are confined geographically, homogenous functionally, or both. We also find that whenever intergovernmental relations were present in communities, the member connectivity was low, even if intersectoral relations appeared together within them.


docid: eveoyytw

title: Limited Two-Way Deterministic Finite Automata with Advice

text: External assistance in the form of strings called advice is given to an automaton in order to make it a non-uniform model of computation. Automata with advice are then examined to better understand the limitations imposed by uniformity, which is a typical property shared by all feasible computational models. The main contribution of this paper is to introduce and investigate an extension of the model introduced by Küçük et al. [6]. The model is called circular deterministic finite automaton with advice tape (cdfat). In this model the input head is allowed to pass over input multiple times. The number of allowed passes over the input, which is typically a function of input length, is considered as a resource besides the advice amount. The results proved for the model include a hierarchy for cdfat with real-time heads, simulation of 1w/1w cdfat by 1w/rt cdfat, lower bounds of resources provided to a cdfat in order to make it powerful enough to recognize any language, utilizable advice limit regardless of the allowed pass limit, a relation between utilizable pass limit and advice limit, and some closure properties.


title: The New Complexity Landscape Around Circuit Minimization

text: We survey recent developments related to the Minimum Circuit Size Problem.


title: Ordered Semiautomatic Rings with Applications to Geometry

text: The present work looks at semiautomatic rings with automatic addition and comparisons which are dense subrings of the real numbers and asks how these can be used to represent geometric objects such that certain operations and transformations are automatic. The underlying ring has always to be a countable dense subring of the real numbers and additions and comparisons and multiplications with constants need to be automatic. It is shown that the ring can be selected such that equilateral triangles can be represented and rotations by [Formula: see text] are possible, while the standard representation of the b-adic rationals does not allow this.


title: Cyclic Shift on Multi-component Grammars

text: Multi-component grammars, known in the literature as “multiple context-free grammars” and “linear context-free rewriting systems”, describe the structure of a string by defining the properties of k-tuples of its substrings, in the same way as ordinary formal grammars (Chomsky’s “context-free”) define properties of substrings. It is shown that, for every fixed k, the family of languages described by k-component grammars is closed under the cyclic shift operation. On the other hand, the subfamily defined by well-nested k-component grammars is not closed under the cyclic shift, yet their cyclic shifts are always defined by well-nested [Formula: see text]-component grammars.


title: Reducing the Ambiguity of Parikh Matrices

text: The Parikh matrix mapping allows us to describe words using matrices. Although compact, this description comes with a level of ambiguity since a single matrix may describe multiple words. This work looks at how considering the Parikh matrices of various transformations of a given word can decrease that ambiguity. More specifically, for any word, we study the Parikh matrix of its Lyndon conjugate as well as that of its projection to a smaller alphabet. Our results demonstrate that ambiguity can often be reduced using these concepts, and we give conditions on when they succeed.


title: Complexity Issues of String to Graph Approximate Matching

text: The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, in this latter case, which edit operations are considered and where are allowed. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only on the graph labels or both on the graph labels and the query string. We introduce a variant of the problem that asks whether there exists a path in a graph that represents a query string with any number of edit operations and we show that is NP-complete, even when labels have length one and in the case the alphabet is binary. Moreover, when it is parameterized by the length of the input string and graph labels have length one, we show that the problem is fixed-parameter tractable and it is unlikely to admit a polynomial kernel. The NP-completeness of this problem leads to the inapproximability (within any factor) of the approximate matching when edit operations are allowed only on the graph labels. Moreover, we show that the variants of approximate string matching to graph we consider are not fixed-parameter tractable, when the parameter is the number of edit operations, even for graphs that have distance one from a DAG. The reduction for this latter result allows us to prove the inapproximability of the variant where edit operations can be applied both on the query string and on graph labels.


title: Approaching Arithmetic Theories with Finite-State Automata

text: The automata-theoretic approach provides an elegant method for deciding linear arithmetic theories. This approach has recently been instrumental for settling long-standing open problems about the complexity of deciding the existential fragments of Büchi arithmetic and linear arithmetic over p-adic fields. In this article, which accompanies an invited talk, we give a high-level exposition of the NP upper bound for existential Büchi arithmetic, obtain some derived results, and further discuss some open problems.


title: Nonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle

text: We construct a new family of Cayley automatic representations of semidirect products [Formula: see text] for which none of the projections of the normal subgroup [Formula: see text] onto each of its cyclic components is finite automaton recognizable. For [Formula: see text] we describe a family of matrices from [Formula: see text] corresponding to these representations. We are motivated by a problem of characterization of all possible Cayley automatic representations of these groups.


title: Lyndon Words versus Inverse Lyndon Words: Queries on Suffixes and Bordered Words

text: The Lyndon factorization of a word has been extensively studied in different contexts and several variants of it have been proposed. In particular, the canonical inverse Lyndon factorization [Formula: see text], introduced in [5], maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the purpose of exploring its use in string queries. As a main result, we prove an upper bound on the length of the longest common extension (or longest common prefix) for two factors of a word w. This bound is at most the maximum length of two consecutive factors of [Formula: see text]. A tool used in the proof is a property that we state for factors with nonempty borders in [Formula: see text]: a nonempty border of a factor [Formula: see text] cannot be a prefix of the next factor [Formula: see text]. Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w, and sorting of local suffixes, i.e., suffixes of the factors in [Formula: see text]. Finally, given a word w and a factor x of w, we prove that their Lyndon factorizations share factors, except for the first and last term of the Lyndon factorization of x. This property suggests that, given two words sharing a common overlap, their Lyndon factorizations could be used to capture the common overlap of these two words.


docid: jcgvravf

title: Alternating Finite Automata with Limited Universal Branching

text: We consider measures that limit universal parallelism in computations of an alternating finite automaton (AFA). Maximum pared tree width counts the largest number of universal branches in any computation and acceptance width counts the number of universal branches in the best accepting computation, i.e., in the accepting computation with least universal parallelism. We give algorithms to decide whether the maximum pared tree width or the acceptance width of an AFA are bounded by an integer k. For a constant k the algorithm for maximum pared tree width operates in polynomial time. An AFA with m states and acceptance width k can be converted to an NFA with [Formula: see text] states. We consider corresponding lower bounds for the transformation. The tree width of an AFA counts the number of all (existential and universal) branches of the computation. We give upper and lower bounds for converting an AFA of bounded tree width to a DFA.


title: On the Weisfeiler-Leman Dimension of Fractional Packing

text: The k-dimensional Weisfeiler-Leman procedure ([Formula: see text]) has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are [Formula: see text]-equivalent if dimention k does not suffice to distinguish them. [Formula: see text]-equivalence is known as fractional isomorphism of graphs, and the [Formula: see text]-equivalence relation becomes finer as k increases. We investigate to what extent standard graph parameters are preserved by [Formula: see text]-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of [Formula: see text]-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.


title: Simplified Parsing Expression Derivatives

text: This paper presents a new derivative parsing algorithm for parsing expression grammars; this new algorithm is both simpler and faster than the existing parsing expression derivative algorithm presented by Moss [12]. This new algorithm improves on the worst-case space and runtime bounds of the previous algorithm by a linear factor, as well as decreasing runtime by about half in practice.


title: Recompression: Technique for Word Equations and Compressed Data

text: In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation [Formula: see text], where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space. The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications.


title: How to Prove that a Language Is Regular or Star-Free?

text: This survey article presents some standard and less standard methods used to prove that a language is regular or star-free.


title: On the Size of Depth-Two Threshold Circuits for the Inner Product Mod 2 Function

text: In this paper, we study the size of depth-two threshold circuits computing the inner product mod 2 function [Formula: see text] (mod 2). First, we reveal that [Formula: see text] can be computed by a depth-two threshold circuit of size significantly smaller than a folklore construction of size [Formula: see text]. Namely, we give a construction of such a circuit (denoted by [Formula: see text] circuit) of size [Formula: see text]. We also give an upper bound of [Formula: see text] for the case that the weights of the top threshold gate are polynomially bounded (denoted by [Formula: see text] circuit). Second, we give new lower bounds on the size of depth-two circuits of some special form; the top gate is an unbounded weight threshold gate and the bottom gates are symmetric gates (denoted by [Formula: see text] circuit). We show that any such circuit computing [Formula: see text] has size [Formula: see text] for every constant [Formula: see text]. This improves the previous bound of [Formula: see text] based on the sign-rank method due to Forster et al. [JCSS ’02, FSTTCS ’01]. Our technique has a unique feature that the lower bound is obtained by giving an explicit feasible solution to (the dual of) a certain linear programming problem. In fact, the problem itself was presented by the author over a decade ago [MFCS ’05], and finding a good solution is an actual contribution of this work.


docid: vwgfffnh

title: Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions

text: This paper defines boolean monadic recursive schemes (BMRSs), a restriction on recursive programs, and shows that when interpreted as transductions on strings they describe exactly the subsequential functions. We discuss how this new result furthers the study of the connections between logic, formal languages and functions, and automata.


title: Complexity of Automatic Sequences

text: Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties like the relationships with kernel and morphic sequences. There exist automatic sequences for which the one complexity is exponentially greater than the other one, in both directions. For both complexity measures we investigate the effect of taking basic operations on sequences like removing or adding an element in front, and observe that these operations may increase the complexity by at most a quadratic factor.


title: Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas

text: We study the computational complexity of finite intersections and unions of deterministic context-free languages. Earlier, Wotschke (1978) demonstrated that intersections of [Formula: see text] deterministic context-free languages are in general more powerful than intersections of d deterministic context-free languages for any positive integer d based on the hierarchy separation of Liu and Weiner (1973). The argument of Liu and Weiner, however, works only on bounded languages of particular forms, and therefore Wotschke’s result cannot be extended to disprove any other language to be written in the form of an intersection of d deterministic context-free languages. To deal with the non-membership of a wide range of languages, we circumvent their proof argument and instead devise a new, practical technical tool: a pumping lemma for finite unions of deterministic context-free languages. Since the family of deterministic context-free languages is closed under complementation, this pumping lemma enables us to show a non-membership relation of languages made up with finite intersections of even non-bounded languages as well. We also refer to a relationship to Hibbard’s limited automata.


title: Complete Variable-Length Codes: An Excursion into Word Edit Operations

text: Given an alphabet A and a binary relation [Formula: see text], a language [Formula: see text] is [Formula: see text]-independent if [Formula: see text]; X is [Formula: see text]-closed if [Formula: see text]. The language X is complete if any word over A is a factor of some concatenation of words in X. Given a family of languages [Formula: see text] containing X, X is maximal in [Formula: see text] if no other set of [Formula: see text] can strictly contain X. A language [Formula: see text] is a variable-length code if any equation among the words of X is necessarily trivial. The study discusses the relationship between maximality and completeness in the case of [Formula: see text]-independent or [Formula: see text]-closed variable-length codes. We focus to the binary relations by which the images of words are computed by deleting, inserting, or substituting some characters.


docid: cfvekouq

title: Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases

text: This paper surveys some results regarding decision problems for probabilistic and max-plus automata, such as containment and equivalence. Probabilistic and max-plus automata are part of the general family of weighted automata, whose semantics are maps from words to real values. Given two weighted automata, the equivalence problem asks whether their semantics are the same, and the containment problem whether one is point-wise smaller than the other one. These problems have been studied intensively and this paper will review some techniques used to show (un)decidability and state a list of open questions that still remain.


title: Context-Sensitive Fusion Grammars Are Universal

text: Context-sensitive fusion grammars are a special case of context-dependent fusion grammars where a rule has only a single positive context condition instead of finite sets of positive and negative context conditions. They generate hypergraph languages from start hypergraphs via successive applications of context-sensitive fusion rules and multiplications of connected components, as well as a filtering mechanism to extract terminal hypergraphs from derived hypergraphs in a certain way. The application of a context-sensitive fusion rule consumes two complementarily labeled hyperedges and identifies corresponding attachment vertices provided that the context condition holds. In this paper, we show that the Post correspondence problem can be formulated very intuitively by such a grammar. Furthermore, we prove that these grammars can generate all recursively enumerable string languages (up to representation of strings as graphs) and are universal in this respect.


title: The Automatic Baire Property and an Effective Property of [Formula: see text]-Rational Functions

text: We prove that [Formula: see text]-regular languages accepted by Büchi or Muller automata satisfy an effective automata-theoretic version of the Baire property. Then we use this result to obtain a new effective property of rational functions over infinite words which are realized by finite state Büchi transducers: for each such function [Formula: see text], one can construct a deterministic Büchi automaton [Formula: see text] accepting a dense [Formula: see text]-subset of [Formula: see text] such that the restriction of F to [Formula: see text] is continuous.


title: Deciding Classes of Regular Languages: The Covering Approach

text: We investigate the membership problem that one may associate to every class of languages [Formula: see text]. The problem takes a regular language as input and asks whether it belongs to [Formula: see text]. In practice, finding an algorithm provides a deep insight on the class [Formula: see text]. While this problem has a long history, many famous open questions in automata theory are tied to membership. Recently, a breakthrough was made on several of these open questions. This was achieved by considering a more general decision problem than membership: covering. In the paper, we investigate how the new ideas and techniques brought about by the introduction of this problem can be applied to get new insight on earlier results. In particular, we use them to give new proofs for two of the most famous membership results: Schützenberger’s theorem and Simon’s theorem.


title: Geometrically Closed Positive Varieties of Star-Free Languages

text: A recently introduced operation of geometrical closure on formal languages is investigated. It is proved that the geometrical closure of a language from the positive variety [Formula: see text], the level 3/2 of the Straubing-Thérien hierarchy of star-free languages, always falls into the variety [Formula: see text], which is a new variety consisting of specific R-trivial languages. As a consequence, each class of regular languages lying between [Formula: see text] and [Formula: see text] is geometrically closed.


title: [Formula: see text] Is Decidable in [Formula: see text]

text: We show that it is decidable whether or not a relation on the reals definable in the structure [Formula: see text] can be defined in the structure [Formula: see text]. This result is achieved by obtaining a topological characterization of [Formula: see text]-definable relations in the family of [Formula: see text]-definable relations and then by following Muchnik’s approach of showing that this characterization can be expressed in the logic of [Formula: see text].


title: Expressiveness and Conciseness of Timed Automata for the Verification of Stochastic Models

text: Timed Automata are a well-known formalism for specifying timed behaviours. In this paper we are concerned with Timed Automata for the specification of timed behaviour of Continuous Time Markov Chains (CTMC), as used in the stochastic temporal logic CSL[Formula: see text]. A timed path formula of CSL[Formula: see text] is specified by a Deterministic Timed Automaton (DTA) that features two kinds of transitions: synchronizing transitions (triggered by CTMC transitions) and autonomous transitions (triggered when a clock reaches a given threshold). Other definitions of CSL[Formula: see text] are based on DTAs that do not include autonomous transitions. This raises the natural question: do autonomous transitions enhance expressiveness and/or conciseness of DTAs? We prove that this is the case and we provide a syntactical characterization of DTAs for which autonomous transitions do not add expressive power, but allow one to define exponentially more concise DTAs.


docid: zgrabaiw

title: On Collapsing Prefix Normal Words

text: Prefix normal words are binary words in which each prefix has at least the same number of [Formula: see text]s as any factor of the same length. Firstly introduced in 2011, the problem of determining the index (amount of equivalence classes for a given word length) of the prefix normal equivalence relation is still open. In this paper, we investigate two aspects of the problem, namely prefix normal palindromes and so-called collapsing words (extending the notion of critical words). We prove characterizations for both the palindromes and the collapsing words and show their connection. Based on this, we show that still open problems regarding prefix normal words can be split into certain subproblems.


title: Windable Heads and Recognizing NL with Constant Randomness

text: Every language in NL has a k-head two-way nondeterministic finite automaton (2nfa([Formula: see text])) recognizing it. It is known how to build a constant-space verifier algorithm from a 2nfa([Formula: see text]) for the same language with constant-randomness, but with error probability [Image: see text] that can not be reduced further by repetition. We have defined the unpleasant characteristic of the heads that causes the high error as the property of being “windable”. With a tweak on the previous verification algorithm, the error is improved to [Image: see text], where [Formula: see text] is the number of windable heads. Using this new algorithm, a subset of languages in NL that have a 2nfa([Formula: see text]) recognizer with [Formula: see text] can be verified with arbitrarily reducible error using constant space and randomness.


title: Input Strictly Local Tree Transducers

text: We generalize the class of input strictly local string functions (Chandlee et al. 2014) to tree functions. We show they are characterized by a subclass of frontier-to-root, deterministic, linear tree transducers. We motivate this class from the study of natural language as it provides a way to distinguish local syntactic processes from non-local ones. We give examples illustrating this kind of analysis.


docid: bdruuzbq

title: Pebble-Intervals Automata and FO[Formula: see text] with Two Orders

text: We introduce a novel automata model, which we call pebble-intervals automata (PIA), and study its power and closure properties. PIAs are tailored for a decidable fragment of FO that is important for reasoning about structures that use data values from infinite domains: the two-variable fragment with one total preorder and its induced successor relation, one linear order, and an arbitrary number of unary relations. We prove that the string projection of every language of data words definable in the logic is accepted by a pebble-intervals automaton [Image: see text], and obtain as a corollary an automata-theoretic proof of the [Formula: see text] upper bound for finite satisfiability due to Schwentick and Zeume.


title: The Power of Programs over Monoids in [Image: see text]

text: The model of programs over (finite) monoids, introduced by Barrington and Thérien, gives an interesting way to characterise the circuit complexity class [Image: see text] and its subclasses and showcases deep connections with algebraic automata theory. In this article, we investigate the computational power of programs over monoids in [Image: see text], a small variety of finite aperiodic monoids. First, we give a fine hierarchy within the class of languages recognised by programs over monoids from [Image: see text], based on the length of programs but also some parametrisation of [Image: see text]. Second, and most importantly, we make progress in understanding what regular languages can be recognised by programs over monoids in [Image: see text]. We show that those programs actually can recognise all languages from a class of restricted dot-depth one languages, using a non-trivial trick, and conjecture that this class suffices to characterise the regular languages recognised by programs over monoids in [Image: see text].


title: Things You Can Do to an Author When He’s Dead: Literary Prosthetics and the Example of Heinrich von Kleist

text: This chapter explores the adaptations allowed—if not demanded—by the death of the author in terms of what this author dubs a “literary prosthetics”, in which the corpus is imagined as being aesthetically supplemented and potentially also enhanced by new and artificial devices. Taking the example of Heinrich von Kleist (1777–1811), the author examines the space for adaptation left by his premature death and the various lacunae in his biography and literary corpus, and asks if the ultimate act of Kleist reception lies in adaptations which forge new authentic works by the long dead author. This begs the question: what kind of critical reception might this prosthetic Kleist literature engender.


Threats from the coronavirus, lessons from the plague


2020 Year of the Nurse and the Midwife


title: Engineered three-dimensional scaffolds for enhanced bone regeneration in osteonecrosis

text: Osteonecrosis, which is typically induced by trauma, glucocorticoid abuse, or alcoholism, is one of the most severe diseases in clinical orthopedics. Osteonecrosis often leads to joint destruction, and arthroplasty is eventually required. Enhancement of bone regeneration is a critical management strategy employed in osteonecrosis therapy. Bone tissue engineering based on engineered three-dimensional (3D) scaffolds with appropriate architecture and osteoconductive activity, alone or functionalized with bioactive factors, have been developed to enhance bone regeneration in osteonecrosis. In this review, we elaborate on the ideal properties of 3D scaffolds for enhanced bone regeneration in osteonecrosis, including biocompatibility, degradability, porosity, and mechanical performance. In addition, we summarize the development of 3D scaffolds alone or functionalized with bioactive factors for accelerating bone regeneration in osteonecrosis and discuss their prospects for translation to clinical practice.


title: COVID-19: is there a role for immunonutrition, particularly in the over 65s?

text: In late December 2019 severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) first emerged in Wuhan, Hubei, China, resulting in the potentially fatal COVID-19. It went on to be officially recognised as a pandemic by the World Health Organisation on 11 March 2020. While many public health strategies have evolved, there has been little mention of the immune system and how this could be strengthened to help protect against viral infections such as SARS-CoV-2. The present paper evaluates the current evidence base relating to immunonutrition, with a particular focus on respiratory viruses. Within the nutrition sector a promising body of evidence studying inter-relationships between certain nutrients and immune competence already exists. This could potentially be an important player in helping the body to deal with the coronavirus, especially among elders. Evidence for vitamins C, D and zinc and their roles in preventing pneumonia and respiratory infections (vitamins C and D) and reinforcing immunity (zinc) appears to look particularly promising. Ongoing research within this important field is urgently needed.


Reflections on leadership in the time of COVID-19


AANP Forum


Your NP Spirit Continues to Shine


title: Tylophorine: Sources, Properties, Applications and Biotechnological Production

text: Tylophora indica, a medicinal climber, belongs to the family, Asclepiadaceae. Roots and leaves of the plant contain several alkaloids including tylophorine, tylophorinine and tylophrinidine. The major alkaloid, tylophorine found in T. indica possesses several properties, such as immunosuppressive, antitumour, antifeedant, antibacterial, antifungal, antiamoebic, diuretic and hepatoprotective activities. In addition to this, tylophorine provides positive stimulation to adrenal cortex. Biotechnological production of tylophorine was fulfilled by inducing hairy roots mediated by Agrobacterium rhizogenes (A4 strain). It was followed by its growth in liquid suspension culture that could yield maximum biomass and tylophorine production. This type of liquid suspension culture yielded 9.8 ± 0.21 mgL(−1) tylophorine within 4–6 weeks of incubation. Maceration technique employed for the extraction of tylophorine was the most viable and efficient protocol. Although many reports are available regarding the biotechnological production of tylophorine, its competent and economic production still continues as a problematic issue.


title: Phytochemicals as Antiviral Agents: Recent Updates

text: The epidemic of viral diseases is a global concern, mandating an urgent need of most promising antivirals. Some of the viral diseases can be cured by approved antiviral drugs, but for others still do not have any vaccines or drugs available. Most of the approved antiviral drugs are somehow directly or indirectly associated with side effects, which eventually raise the need for the development of antivirals based on natural phytochemicals. Globally, the development of antivirals is shifting towards the plant-derived products as they are less toxic and has less chance to develop resistance. Phytochemicals have been exploited traditionally for the cure of many diseases, and also have been reported to inhibit viral replication/transcription. Most of them inhibit the viruses either during the viral entry inside the host cell or during their replication. Moreover, 50% of the drugs derived from plants are being used in the Western nations. Plants have a variety of phytochemicals like flavonoids, terpenoids, lignins, alkaloids, and coumarins that are having antioxidant activity, and help to inhibit viral genome. Various plant-derived products have been well studied against viruses like herpes virus, human immunodeficiency virus (HIV), influenza, and hepatitis virus. More recently, Coronavirus disease (COVID-19) caused by a newly identified coronavirus has become pandemic, and affected world’s population severely. However, there are still less explored phytochemicals for the inhibition of viruses like dengue virus, chikungunya virus, and other alphaviruses. In this chapter, we will emphasize on the reported phytochemicals and their derivatives, having antiviral properties and their mechanism to treat viral diseases.