This paper proposes graph linear notations and an extension of them with regular expressions. Graph linear notations are a set of strings to represent labeled general graphs. They are extended with regular expressions to represent sets of graphs by specifying chosen parts for selections and repetitions of certain induced subgraphs. Methods for the conversion between graph linear notations and labeled general graphs are shown. The NP-completeness of the membership problem for graph regular expressions is proved.

Synthesis problems on multiplayer non-zero-sum games (MG) with multiple environment players that behave rationally are the problems to find a good strategy of the system and have been extensively studied. This paper concerns the synthesis problems on stochastic MG (SMG), where a special controller other than players, called nature, which chooses a move in its turn randomly, may exist. Two types of synthesis problems on SMG exist: cooperative rational synthesis problem (CRSP) and non-cooperative rational synthesis problem (NCRSP). The rationality of environment players is modeled by Nash equilibria, and CRSP is the problem to decide whether there exists a Nash equilibrium that gives the system a payoff not less than a given threshold. Ummels et al. studied the complexity of CRSP for various classes of objectives and strategies of players. CRSP fits the situation where the system can make a suggestion of a strategy profile (a tuple of strategies of all players) to the environment players. However, in real applications, the system may rarely have an opportunity to make suggestions to the environment, and thus CRSP is optimistic. NCRSP is the problem to decide whether there exists a strategy σ0 of the system satisfying that for every strategy profile of the environment players that forms a 0-fixed Nash equilibrium (a Nash equilibrium where the system's strategy is fixed to σ0), the system obtains a payoff not less than a given threshold. In this paper, we investigate the complexity of NCRSP for positional (i.e. pure memoryless) strategies. We consider ω-regular objectives as the model of players' objectives, and show the complexity results of the problem for several subclasses of ω-regular objectives. In particular, the problem for terminal reachability (TR) objectives is shown to be Σp2-complete.

Linear codes are widely studied due to their important applications in secret sharing schemes, authentication codes, association schemes and strongly regular graphs, etc. In this paper, firstly, a class of three-weight linear codes is constructed by selecting a new defining set, whose weight distributions are determined by exponential sums. Results show that almost all the constructed codes are minimal and thus can be used to construct secret sharing schemes with sound access structures. Particularly, a class of projective two-weight linear codes is obtained and based on which a strongly regular graph with new parameters is designed.

In this paper, we propose a unified algebraic design of the generalized Moreau enhancement matrix (GME matrix) for the Linearly involved Generalized-Moreau-Enhanced (LiGME) model. The LiGME model has been established as a framework to construct linearly involved nonconvex regularizers for sparsity (or low-rank) aware estimation, where the design of GME matrix is a key to guarantee the overall convexity of the model. The proposed design is applicable to general linear operators involved in the regularizer of the LiGME model, and does not require any eigendecomposition or iterative computation. We also present an application of the LiGME model with the proposed GME matrix to a group sparsity aware least squares estimation problem. Numerical experiments demonstrate the effectiveness of the proposed GME matrix in the LiGME model.

Let us consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE minimal substring search problem is to find all minimal substrings of T matching r. Yamamoto proposed O(mn) time and O(m) space algorithm using a Thompson automaton. In this paper, we improve Yamamoto's algorithm by introducing parallelism. The proposed algorithm runs in O(mn) time in the worst case and in O(mn/p) time in the best case, where p denotes the number of processors. Besides, we show a parameter related to the parallel time of the proposed algorithm. We evaluate the algorithm experimentally.

Many modern regular expression engines employ various extensions to give more expressive support for real-world usages. Among the major extensions employed by many of the modern regular expression engines are backreferences and lookaheads. A question of interest about these extended regular expressions is their expressive power. Previous works have shown that (i) the extension by lookaheads does not enhance the expressive power, i.e., the expressive power of regular expressions with lookaheads is still regular, and that (ii) the extension by backreferences enhances the expressive power, i.e., the expressive power of regular expressions with backreferences (abbreviated as rewb) is no longer regular. This raises the following natural question: Does the extension of regular expressions with backreferences by lookaheads enhance the expressive power of regular expressions with backreferences? This paper answers the question positively by proving that adding either positive lookaheads or negative lookaheads increases the expressive power of rewb (the former abbreviated as rewblp and the latter as rewbln). A consequence of our result is that neither the class of finite state automata nor that of memory automata (MFA) of Schmid[2] (which corresponds to regular expressions with backreferenes but without lookaheads) corresponds to rewblp or rewbln. To fill the void, as a first step toward building such automata, we propose a new class of automata called memory automata with positive lookaheads (PLMFA) that corresponds to rewblp. The key idea of PLMFA is to extend MFA with a new kind of memories, called positive-lookahead memory, that is used to simulate the backtracking behavior of positive lookaheads. Interestingly, our positive-lookahead memories are almost perfectly symmetric to the capturing-group memories of MFA. Therefore, our PLMFA can be seen as a natural extension of MFA that can be obtained independently of its original intended purpose of simulating rewblp.

Constructing accurate similarity graph is an important process in graph-based clustering. However, traditional methods have three drawbacks, such as the inaccuracy of the similarity graph, the vulnerability to noise and outliers, and the need for additional discretization process. In order to eliminate these limitations, an entropy regularized unsupervised clustering based on maximum correntropy criterion and adaptive neighbors (ERMCC) is proposed. 1) Combining information entropy and adaptive neighbors to solve the trivial similarity distributions. And we introduce l0-norm and spectral embedding to construct similarity graph with sparsity and strong segmentation ability. 2) Reducing the negative impact of non-Gaussian noise by reconstructing the error using correntropy. 3) The prediction label vector is directly obtained by calculating the sparse strongly connected components of the similarity graph Z, which avoids additional discretization process. Experiments are conducted on six typical datasets and the results showed the effectiveness of the method.

This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-d INDEPENDENT SET problem (MaxDdIS for short). For an integer d≥2, a distance-d independent set of an unweighted graph G=(V, E) is a subset S⊆V of vertices such that for any pair of vertices u, v∈S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r≥3) and planar graphs, as follows: (1) For every fixed integers d≥3 and r≥3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-2/d)-approximation algorithms when restricted to d=r=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

Register pushdown system (RPDS) is an extension of pushdown system (PDS) that has registers for dealing with data values. An LTL model checking method for RPDS with regular valuations has been proposed in previous work; however, the method requires the register automata (RA) used for defining a regular valuation to be backward-deterministic. This paper proposes another approach to the same problem, in which the model checking problem for RPDS is reduced to that problem for PDS by constructing a PDS bisimulation equivalent to a given RPDS. This construction is simpler than the previous model checking method and does not require RAs deterministic or backward-deterministic, and the bisimulation equivalence clearly guarantees the correctness of the reduction. On the other hand, the proposed method requires every RPDS (and RA) to have the freshness property, in which whenever the RPDS updates a register with a data value not stored in any register or the stack top, the value should be fresh. This paper also shows that the model checking problem with regular valuations defined by general RA is undecidable, and thus the freshness constraint is essential in the proposed method.

Loan default prediction has been a significant problem in the financial domain because overdue loans may incur significant losses. Machine learning methods have been introduced to solve this problem, but there are still many challenges including feature multicollinearity, imbalanced labels, and small data sample problems. To replicate the success of deep learning in many areas, an effective regularization technique named muddling label regularization is introduced in this letter, and an ensemble of feed-forward neural networks is proposed, which outperforms machine learning and deep learning baselines in a real-world dataset.

Recently, the performances of discriminative correlation filter (CF) trackers are getting better and better in visual tracking. In this paper, we propose spatial-temporal regularization with precise state estimation based on discriminative correlation filter (STPSE) in order to achieve more significant tracking performance. First, we consider the continuous change of the object state, using the information from the previous two filters for training the correlation filter model. Here, we train the correlation filter model with the hand-crafted features. Second, we introduce update control in which average peak-to-correlation energy (APCE) and the distance between the object locations obtained by HOG features and hand-crafted features are utilized to detect abnormality of the state around the object. APCE and the distance indicate the reliability of the filter response, thus if abnormality is detected, the proposed method does not update the scale and the object location estimated by the filter response. In the experiment, our tracker (STPSE) achieves significant and real-time performance with only CPU for the challenging benchmark sequence (OTB2013, OTB2015, and TC128).

Virtual Adversarial Training (VAT) has shown impressive results among recently developed regularization methods called consistency regularization. VAT utilizes adversarial samples, generated by injecting perturbation in the input space, for training and thereby enhances the generalization ability of a classifier. However, such adversarial samples can be generated only within a very small area around the input data point, which limits the adversarial effectiveness of such samples. To address this problem we propose LVAT (Latent space VAT), which injects perturbation in the latent space instead of the input space. LVAT can generate adversarial samples flexibly, resulting in more adverse effect and thus more effective regularization. The latent space is built by a generative model, and in this paper we examine two different type of models: variational auto-encoder and normalizing flow, specifically Glow. We evaluated the performance of our method in both supervised and semi-supervised learning scenarios for an image classification task using SVHN and CIFAR-10 datasets. In our evaluation, we found that our method outperforms VAT and other state-of-the-art methods.

In channel decoding, a decoder with suboptimal metrics may be used because of the uncertainty of the channel statistics or the limitations of the decoder. In this case, the decoding metric is different from the actual channel metric, and thus it is called mismatched decoding. In this paper, applying the technique of the DS2 bound, we derive an upper bound on the error probability of mismatched decoding over a regular channel for the ensemble of linear block codes, which was defined by Hof, Sason and Shamai. Assuming the ensemble of random linear block codes defined by Gallager, we show that the obtained bound is not looser than the conventional bound. We also give a numerical example for the ensemble of LDPC codes also introduced by Gallager, which shows that our proposed bound is tighter than the conventional bound. Furthermore, we obtain a single letter error exponent for linear block codes.

In the recent years, deep learning has achieved significant results in various areas of machine learning. Deep learning requires a huge amount of data to train a model, and data collection techniques such as web crawling have been developed. However, there is a risk that these data collection techniques may generate incorrect labels. If a deep learning model for image classification is trained on a dataset with noisy labels, the generalization performance significantly decreases. This problem is called Learning with Noisy Labels (LNL). One of the recent researches on LNL, called DivideMix [1], has successfully divided the dataset into samples with clean labels and ones with noisy labels by modeling loss distribution of all training samples with a two-component Mixture Gaussian model (GMM). Then it treats the divided dataset as labeled and unlabeled samples and trains the classification model in a semi-supervised manner. Since the selected samples have lower loss values and are easy to classify, training models are in a risk of overfitting to the simple pattern during training. To train the classification model without overfitting to the simple patterns, we propose to introduce consistency regularization on the selected samples by GMM. The consistency regularization perturbs input images and encourages model to outputs the same value to the perturbed images and the original images. The classification model simultaneously receives the samples selected as clean and their perturbed ones, and it achieves higher generalization performance with less overfitting to the selected samples. We evaluated our method with synthetically generated noisy labels on CIFAR-10 and CIFAR-100 and obtained results that are comparable or better than the state-of-the-art method.

A pushdown system (PDS) is known as an abstract model of recursive programs. For PDS, model checking methods have been studied and applied to various software verification such as interprocedural data flow analysis and malware detection. However, PDS cannot manipulate data values from an infinite domain. A register PDS (RPDS) is an extension of PDS by adding registers to deal with data values in a restricted way. This paper proposes algorithms for LTL model checking problems for RPDS with simple and regular valuations, which are labelings of atomic propositions to configurations with reasonable restriction. First, we introduce RPDS and related models, and then define the LTL model checking problems for RPDS. Second, we give algorithms for solving these problems and also show that the problems are EXPTIME-complete. As practical examples, we show solutions of a malware detection and an XML schema checking in the proposed framework.

It is well-known that pushdown systems (PDS) effectively preserve regularity. This property implies the decidability of the reachability problem for PDS and has been applied to automatic program verification. The backward regularity preservation property was also shown for an extension of PDS by adding registers. This paper aims to show the forward regularity preservation property. First, we provide a concise definition of the register model called register pushdown systems (RPDS). Second, we show the forward regularity preservation property of RPDS by providing a saturation algorithm that constructs a register automaton (RA) recognizing $post^{ast}_calP(L(calA))$ where $calA$ and $calP$ are a given RA and an RPDS, respectively, and $post^{ast}_calP$ is the forward image of the mapping induced by $calP$. We also give an example of applying the proposed algorithm to malware detection.

This paper presents a new method to translate a regular expression into a nondeterministic finite automaton (an NFA for short). Let r be a regular expression and let M be a Thompson automaton for r. We first introduce a labeled Thompson automaton defined by assigning two types of expressions which denote prefixes and suffixes of words in L(r) to each state of M. Then we give new ϵ-free NFAs constructed from a labeled Thompson automaton. These NFAs are called a prefix equation automaton and a suffix equation automaton. We show that a suffix equation automaton is isomorphic to an equation automaton defined by Antimirov. Furthermore we give an NFA called a unified equation automaton by joining two NFAs. Thus the number of states of a unified equation automaton can be smaller than that of an equation automaton.

The task of image annotation is becoming enormously important for efficient image retrieval from the web and other large databases. However, huge semantic information and complex dependency of labels on an image make the task challenging. Hence determining the semantic similarity between multiple labels on an image is useful to understand any incomplete label assignment for image retrieval. This work proposes a novel method to solve the problem of multi-label image annotation by unifying two different types of Laplacian regularization terms in deep convolutional neural network (CNN) for robust annotation performance. The unified Laplacian regularization model is implemented to address the missing labels efficiently by generating the contextual similarity between labels both internally and externally through their semantic similarities, which is the main contribution of this study. Specifically, we generate similarity matrices between labels internally by using Hayashi's quantification method-type III and externally by using the word2vec method. The generated similarity matrices from the two different methods are then combined as a Laplacian regularization term, which is used as the new objective function of the deep CNN. The Regularization term implemented in this study is able to address the multi-label annotation problem, enabling a more effectively trained neural network. Experimental results on public benchmark datasets reveal that the proposed unified regularization model with deep CNN produces significantly better results than the baseline CNN without regularization and other state-of-the-art methods for predicting missing labels.

A limited number of types of sound event occur in an acoustic scene and some sound events tend to co-occur in the scene; for example, the sound events “dishes” and “glass jingling” are likely to co-occur in the acoustic scene “cooking.” In this paper, we propose a method of sound event detection using graph Laplacian regularization with sound event co-occurrence taken into account. In the proposed method, the occurrences of sound events are expressed as a graph whose nodes indicate the frequencies of event occurrence and whose edges indicate the sound event co-occurrences. This graph representation is then utilized for the model training of sound event detection, which is optimized under an objective function with a regularization term considering the graph structure of sound event occurrence and co-occurrence. Evaluation experiments using the TUT Sound Events 2016 and 2017 detasets, and the TUT Acoustic Scenes 2016 dataset show that the proposed method improves the performance of sound event detection by 7.9 percentage points compared with the conventional CNN-BiGRU-based detection method in terms of the segment-based F1 score. In particular, the experimental results indicate that the proposed method enables the detection of co-occurring sound events more accurately than the conventional method.

As smartphones and IoT devices become widespread, probabilistic event streams, which are continuous analysis results of sensing data, have received a lot of attention. One of the applications of probabilistic event streams is monitoring of time series events based on regular expressions. That is, we describe a monitoring query such as “Has the tracked object moved from RoomA to RoomB in the past 30 minutes?” by using a regular expression, and then check whether corresponding events occur in a probabilistic event stream with a sliding window. Although we proposed the fundamental monitoring method of time series events in our previous work, three problems remain: 1) it is based on an unusual assumption about slide size of a sliding window, 2) the grammar of pattern queries did not include “negation”, and 3) it was not optimized for multiple monitoring queries. In this paper, we propose several techniques to solve the above problems. First, we remove the assumption about slide size, and propose adaptive slicing of sliding windows for efficient probability calculation. Second, we calculate the occurrence probability of a negation pattern by using an inverted DFA. Finally, we propose the merge of multiple DFAs based on disjunction to process multiple queries efficiently. Experimental results using real and synthetic datasets demonstrate effectiveness of our approach.