To investigate the theoretical foundations of deep learning from the view points of the minimum description length (MDL) principle, we analyse the risk bounds on MDL estimators for simple two-layers neural networks (NNs) with ReLU activation. For that purpose, we construct a two-stage code with small redundancy based on the fact that the eigenvalue distribution of the Fisher information matrix of the NNs is strongly biased, which was recently shown by Takeishi et al. (2023). This means that the MDL estimator induced by the two-stage code enjoys a tight upper bound on its risk, which is a direct consequence of the theory on MDL estimators originated by Barron and Cover (1991). The target NNs consist of$d$nodes in the input layer,$p$nodes in the hidden layer, and one output node. The object of estimation is only the$p$weights from the hidden layer to the output node. In the context of the large-scale neural networks of interest to us, it is assumed that$p\gg d$. Note that the leading term of our risk bound is$O(d^{2}\log n/n)$, independent of$p$.

This research aims at automatic clustering from a large-scale malware specimen set by constructing a phylogenetic tree. In our previous work, we proposed a scalable method for constructing a phylogenetic tree with a clustering algorithm. In this paper, we will introduce the current progress of our work. We are trying to improve our algorithm to achieve higher clustering accuracy and we are using a much larger IoT malware set containing 182,838 malware specimens to evaluate our method.

We argue the Fisher information matrix (FIM) of one hidden layer networks with the ReLU activation function. For a network, let W denote the d×p weight matrix from the d-dimensional input to the hidden layer consisting of p neurons, and v the p-dimensional weight vector from the hidden layer to the scalar output. We focus on the FIM of v, which we denote as I. Under certain conditions, we characterize the first three clusters of eigenvalues and eigenvectors of the FIM. Specifically, we show that the following approximately holds. (1) Since I is non-negative owing to the ReLU, the first eigenvalue is the Perron-Frobenius eigenvalue. (2) For the cluster of the next maximum values, the eigenspace is spanned by the row vectors of W. (3) The direct sum of the eigenspace of the first eigenvalue and that of the third cluster is spanned by the set of all the vectors obtained as the Hadamard product of any pair of the row vectors of W. We confirmed by numerical calculation that the above is approximately correct when the number of hidden nodes is about 10000.

Most IoT malware is variants generated by editing and reusing parts of the functions based on publicly available source codes. In our previous study, we proposed a method to estimate the functions of a specimen using the Function Call Sequence Graph (FCSG), which is a directed graph of execution sequence of function calls. In the FCSG-based method, the subgraph corresponding to a malware functionality is manually created and called a signature-FSCG. The specimens with the signature-FSCG are expected to have the corresponding functionality. However, this method cannot detect the specimens with a slightly different subgraph from the signature-FSCG. This paper found that these specimens were supposed to have the same functionality for a signature-FSCG. These specimens need more flexible signature matching, and we propose a graph embedding technique to realize it.

Fisher information of simple neural networks with the softplus activation function is argued. We show that, under certain conditions, FIMs of simple models have the similar interesting spectral structure as the one shown by Takeishi et al (2021) for networks with ReLU. This work helps us to understand why the FIM has such the structure.

Malware is increasingly diversified and sophisti-cated. It is essential to rapidly and accurately detect malware activities when malware infection spreads. However, accurately distinguishing potential malware activities from countless indis-criminate scanning attacks is a huge challenge. In this study, we introduce Dark-NMF, a darknet analysis engine using Non-negative Matrix Factorization (NMF). Dark-NMF focuses on synchronizing the spatiotemporal features seen when malware infection spreads and detects abnormally synchronous spatial features (source hosts and destination ports) automatically in near real-time. Dark-NMF measures the synchronization of spatial features by decomposing spatiotemporal patterns from darknet traffic using NMF. We tuned the hyperparameters of Dark- Nmfand evaluated the detection performance of malware activities against the performance of existing methods such as GLASSO and ChangeFinder using a human-labeled ground truth. We found that Dark-NMF detects all malware activities that should be detected in the ground truth without a miss. We also showed that Dark- Nmfhas many advantages over existing methods and provided a highly practical operation guideline. Consequently, Dark-NMF is expected to contribute as threat intelligence information for rapid response to malware activity.

The minimum description length (MDL) principle is extended to supervised learning. The MDL principle is a philosophy that the shortest description of given data leads to the best hypothesis about the data source. One of the key theories for the MDL principle is Barron and Cover's theory (BC theory), which mathematically justifies the MDL principle based on two-stage codes in density estimation (unsupervised learning). Though the codelength of two-stage codes looks similar to the target function of penalized likelihood methods, parameter optimization of penalized likelihood methods is done without quantization of parameter space. Recently, Chatterjee and Barron have provided theoretical tools to extend BC theory to penalized likelihood methods by overcoming this difference. Indeed, applying their tools, they showed that the famous penalized likelihood method `lasso' can be interpreted as an MDL estimator and enjoys performance guarantee by BC theory. An important fact is that their results assume a fixed design setting, which is essentially the same as unsupervised learning. The fixed design is natural if we use lasso for compressed sensing. If we use lasso for supervised learning, however, the fixed design is considerably unsatisfactory. Only random design is acceptable. However, it is inherently difficult to extend BC theory to the random design regardless of whether the parameter space is quantized or not. In this paper, a novel theoretical tool for extending BC theory to supervised learning (the random design setting and no quantization of parameter space) is provided. Applying this tool, when the covariates are subject to a Gaussian distribution, it is proved that lasso in the random design setting can also be interpreted as an MDL estimator, and that lasso enjoys the risk bound of BC theory. The risk/regret bounds obtained have several advantages inherited from BC theory. First, the bounds require remarkably few assumptions. Second, the bounds hold for any finite sample size $n$ and any finite feature number $p$ even if $n\ll p$ . Behavior of the regret bound is investigated by numerical simulations. We believe that this is the first extensions of BC theory to supervised learning (random design).

The MDL estimators for density estimation, which are defined by two-part codes for universal coding, are analyzed. We give a two-part code for mixture families whose regret is close to the minimax regret, where regret of a code with respect to a target family ℳ is the difference between the codelength of the code and the ideal codelength achieved by an element in ℳ. Our code is constructed using a probability density in an enlarged family of ℳ (a bundle of local exponential families of ℳ) for data description. This result gives a tight upper bound on the risk of the MDL estimator defined by the two-part code, based on the theory introduced by Barron and Cover in 1991.

For linear system models, the approximate massage passing (AMP) is one of the effective iterative sparse recovery algorithms. However, depending on a measurement matrix ensemble, AMP may face convergence issues. Some algorithms are proposed so far to avoid the convergence issues, e.g., the orthogonal AMP (OAMP) and the mean removal. One of the simplest ways to avoid the convergence issues is to introduce a damping effect into AMP. In this paper, we derive a simple recursive equations that characterizes the damped OAMP, which is an OAMP in which the damping effect is introduced, and show that the result can be applied to the damped version of the original AMP.

Cardinality of typical sets and the smallest high probability set for discrete memoryless sources and stationary Markov sources are considered. Usually, its width is fixed in the definition of both sets, but sometimes it is assumed that the width converges to zero as the length of sequence n goes to infinity. In such setting, some condition for the width is necessary to make the cardinality near 2nH, where H denotes the entropy rate of the information source. In this article, we give sufficient conditions for the above propositions. We also show sufficient conditions for that they don’t hold for DMS and Markov sources under a certain restriction.

We prove that a tree model is an exponential family (e-family) of Markov kernels, if and only if it is an FSMX model. The notion of e-family of Markov kernels was first introduced by Nakagawa and Kanaya ('93) in the one-dimensional case. Then, Nagaoka ('05) gave its established form, and Hayashi & Watanabe ('16) discussed it. A tree model is the Markov model defined by a context tree. It is noted by Weinberger et al., ('95) that tree models are classified into two classes; FSMX models and non-FSMX models, depending on the shape of their context trees. The FSMX model is a tree model and a finite state machine. We further show that, for Markov models, the e-family of Markov kernels is equivalent to the asymptotic e-family, which was introduced by Takeuchi & Barron ('98). Note that Takeuchi & Kawabata ('07) proved that non-FSMX tree models are not asymptotic e-families for the binary alphabet case. This paper enhances their result and reveals the information geometrical properties of tree models.

We study Barron and Cover’s theory (BC theory) in supervised learning. The original BC theory can be applied to supervised learning only approximately and limitedly. Though Barron (2008) and Chatterjee and Barron (2014) succeeded in removing the approximation, their idea cannot be essentially applied to supervised learning in general. By solving this issue, we propose an extension of BC theory to supervised learning. The extended theory has several advantages inherited from the original BC theory. First, it holds for finite sample number n. Second, it requires remarkably few assumptions. Third, it gives a justification of the MDL principle in supervised learning. We also derive new risk and regret bounds of lasso with random design as its application. The derived risk bound hold for any finite n without boundedness of features in contrast to past work. Behavior of the regret bound is investigated by numerical simulations. We believe that this is the first extension of BC theory to general supervised learning without approximation.

For the additive white Gaussian noise channel with average power constraint, it is shown that sparse superposition codes, proposed by Barron and Joseph in 2010, achieve the capacity. We study the upper bounds on its block error probability with least squares decoding when a dictionary with which we make codewords is drawn from an unbiased Bernoulli distribution. We improve the upper bounds shown by Takeishi et.al. in 2014 with fairly simplified form.

We study the problems of data compression, gambling and prediction of a string xn= x1x2...xnfrom an alphabet X, in terms of regret with respect to models with hidden variables including general mixture families. When the target class is a non-exponential family, a modification of Jeffreys prior which has measure outside the given family of densities was introduced to achieve the minimax regret [8], under certain regularity conditions. In this paper, we show that the models with hidden variables satisfy those regularity conditions, when the hidden variables' model is an exponential family. In paticular, we do not have to restrict the class of data strings so that the MLE is in the interior of the parameter space for the case of the general mixture family.

We study the problem of data compression, gambling and prediction of strings xn= x1x2...xnin terms of coding regret, where the tree model is assumed as a target class. We apply the minimax Bayes strategy for curved exponential families to this problem and show that it achieves the minimax regret without restriction on the data strings. This is an extension of the minimax result by (Takeuchi et al. 2013) for models of kth order Markov chains and determines the constant term of the Stochastic Complexity for the tree model.

For the additive white Gaussian noise channel with average power constraint, sparse superposition codes with least squares decoding are proposed by Barron and Joseph in 2010. The codewords are designed by using a dictionary each entry of which is drawn from a Gaussian distribution. The error probability is shown to be exponentially small for all rates up to the capacity. This paper proves that when each entry of the dictionary is drawn from a Bernoulli distribution, the error probability is also exponentially small for all rates up to the capacity. The proof is via a central limit theorem-type inequality, which we show for this analysis.

For the additive white Gaussian noise channel with average power constraint, sparse superposition codes with least squares decoding were proposed by Barron and Joseph in 2010. The codewords are designed by using a dictionary which is drawn from a Gaussian distribution. The error probability is shown to be exponentially small in code length for all rates up to the capacity. This paper proves that when the dictionary is drawn from a Bernoulli distribution, the error probability is also exponentially small for all rates up to the capacity.

We study the problems of data compression, gambling and prediction of a sequence xn= x1x2...xnfrom an alphabet X, in terms of regret with respect to various families of probability distributions. It is known that the regret of the Bayes mixture with respect to a general exponential families asymptotically achieves the minimax value when variants of Jeffreys prior are used, under the condition that the maximum likelihood estimate is in the interior of the parameter space. We discuss a modification of Jeffreys prior which has measure outside the given family of densities, to achieve minimax regret with respect to non-exponential type families, e.g. curved exponential families and mixture families. These results also provide characterization of Rissanen's stochastic complexity for those classes.

We discuss the properties of Jeffreys mixture for a Markov model. First, we show that a modified Jeffreys mixture asymptotically achieves the minimax coding regret for universal data compression, where we do not put any restriction on data sequences. Moreover, we give an approximation formula for the prediction probability of Jeffreys mixture for a Markov model. By this formula, it is revealed that the prediction probability by Jeffreys mixture for the Markov model with alphabet$\{0,1\}$is not of the form$(n_{x \vert s}+\alpha)/(n_{s}+\beta)$, where$n_{x \vert s}$is the number of occurrences of the symbol$x$following the context$s \in \{0,1\}$and$n_{s}=n_{0 \vert s}+n_{1 \vert s}$. Moreover, we propose a method to compute our minimax strategy, which is a combination of a Monte Carlo method and the approximation formula, where the former is used for earlier stages in the data, while the latter is used for later stages.

We analyze properties of Constant Markov Portfolio (CMP), which we proposed as a generalized notion of Constantly Rebalanced Portfolio (CRP) in 2011, and present its generalization. In particular, we show the algorithm for exact computation of the Bayesian strategy for CMP by extending the algorithm for CRP given by Cover & Ordentlich in 1996. Further, we propose a generalization of CMP in order to design a strategy which employs the option of cash as side information. We show an efficient approximation algorithm to compute the universal strategy for the model based on EM algorithm.

We provide a new look at Cover's universal portfolio, where we define probability density functions (p.d.f.) representing wealth functions of portfolios. In this view, log wealth ratio of a portfolio sequence is equal to coding regret of its p.d.f. for the target class which consists of the p.d.f. representing constantly rebalanced portfolios (CRP). It is revealed that the p.d.f. of a CRP is a hidden Markov model (HMM) with the restriction that the latent variable's distribution is Bernoulli. Further we consider the portfolio with the generalized target class defined by extending the latent variable's distribution to a parametric model of stochastic processes. Then, we discuss the minimax log wealth ratio of the class analyzing Fisher information of the p.d.f. for portfolios, which is strictly smaller than that of the latent variable's model. Finally we propose a portfolio strategy using the Jeffreys prior of the class of p.d.f. and an efficient method to calculate causal portfolios using the Baum-Welch algorithm.

This paper proposes a modification of model selection criterion Direct Eigenvalue Estimator (DEE) for small sample regression proposed by Chapelle et al. (2002). The derivation of DEE requires neither an asymptotic assumption nor an assumption that the variance of noise is known in advance. Chapelle et al. (2002) reported that their model selection procedure performed well even when the data number was small but a little worse than ADJ (Schuurmans, 1997) on experiments. We point out, however, the derivation of DEE includes two mistakes. We further propose a slight modification to correct those mistakes. Our experiments verify that the modified DEE gives more stable model selection than the original DEE.

We study Fisher information of stationary Markov models with a finite alphabet. In particular, we derive the Fisher information determinant of expectation parameter eta, which is defined as expectation of Markov type. The Fisher information determinant with respect to Markov kernel parameter (conditional probabilities) is easy to find, while it is not so with respect to the expectation parameter eta nor the natural parameter thetas. Note that thetas and eta are of special importance for exponential families including Markov models.

We prove that the non FSMX tree model is not an exponential family. It is noted in [Weinberger et al., 95] that the tree source is classified into two classes; a FSMX source or not, depending on shape of the context tree. The FSMX source is a tree source and a finite state machine. It is known that the FSMX model is an exponential family. In this situation our concern is whether the non FSMX tree model is an exponential family or not. This paper's contribution is to show that the non FSMX tree model is not an exponential family. Hence, for the tree model, to be an FSMX model is a necessary and sufficient condition for to be an exponential family.

We are concerned with the issue of detecting outliers and change points from time series. In the area of data mining, there have been increased interest in these issues since outlier detection is related to fraud detection, rare event discovery, etc., while change-point detection is related to event/trend change detection, activity monitoring, etc. Although, in most previous work, outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them. In this framework, a probabilistic model of time series is incrementally learned using an online discounting learning algorithm, which can track a drifting data source adaptively by forgetting out-of-date statistics gradually. A score for any given data is calculated in terms of its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. By taking an average of the scores over a window of a fixed length and sliding the window, we may obtain a new time series consisting of moving-averaged scores. Change point detection is then reduced to the issue of detecting outliers in that time series. We compare the performance of our framework with those of conventional methods to demonstrate its validity through simulation and experimental applications to incidents detection in network security.

It is known that the Jeffreys prior plays an important role in statistical inference. In this paper, we generalize the Jeffreys prior from the point of view of information geometry and introduce a one-parameter family of prior distributions, which we named the /spl alpha/-parallel priors. The /spl alpha/-parallel prior is defined as the parallel volume element with respect to the /spl alpha/-connection and coincides with the Jeffreys prior when /spl alpha/=0. Further, we analyze asymptotic behavior of the various estimators such as the projected Bayes estimator (the estimator obtained by projecting the Bayes predictive density onto the original class of distributions) and the minimum description length (MDL) estimator, when the /spl alpha/-parallel prior is used. The difference of these estimators from maximum-likelihood estimator (MLE) due to the /spl alpha/-prior is shown to be regulated by an invariant vector field of the statistical model. Although the Jeffreys prior always exists, the existence of /spl alpha/-parallel prior with /spl alpha/ /spl ne/ 0 is not always guaranteed. Hence, we consider conditions for the existence of the /spl alpha/-parallel prior, elucidating the conjugate symmetry in a statistical model.

We are developing a technique to predict travel time of a vehicle for an objective road section, based on real time traffic data collected through a probe-car system. In the area of Intelligent Transport System (ITS), travel time prediction is an important subject. Probe-car system is an upcoming data collection method, in which a number of vehicles are used as moving sensors to detect actual traffic situation. It can collect data concerning much larger area, compared with traditional fixed detectors. Our prediction technique is based on statistical analysis using AR model with seasonal adjustment and MDL (Minimum Description Length) criterion. Seasonal adjustment is used to handle periodicities of 24 hours in traffic data. Alternatively, we employ state space model, which can handle time series with periodicities. It is important to select really effective data for prediction, among the data from widespread area, which are collected via probe-car system. We do this using MDL criterion. That is, we find the explanatory variables that really have influence on the future travel time. In this paper, we experimentally show effectiveness of our method using probe-car data collected in Nagoya Metropolitan Area in 2002.

We consider the situation where a number of agents are distributed and each of them collects a data sequence generated according to an unknown probability distribution. Here each of the distributions is specified by common parameters and individual parameters e.g., a normal distribution with an identical mean and a different variance. Here we introduce a notion of an information consortium, which is a framework where the agents cannot show raw data to one another, but they like to enjoy significant information gain for estimating the respective distributions. Such an information consortium has recently received much interest in a broad range of areas including financial risk management, ubiquitous network mining, etc. In this paper we are concerned with the following three issues: 1) how to design a collaborative strategy for agents to estimate the respective distributions in the information consortium, 2) characterizing when each agent has a benefit in terms of information gain for estimating its distribution or information loss for predicting future data, and 3) charracterizing how much benefit each agent obtains. In this paper we yield a statistical formulation of information consortia and solve all of the above three problems for a general form of probability distributions. Specifically we propose a basic strategy for cooperative estimation and derive a necessary and sufficient condition for each agent to have a significant benefit.

We are concerned with the issues of outlier detection and change point detection from a data stream. In the area of data mining, there have been increased interest in these issues since the former is related to fraud detection, rare event discovery, etc., while the latter is related to event/trend by change detection, activity monitoring, etc. Specifically, it is important to consider the situation where the data source is non-stationary, since the nature of data source may change over time in real applications. Although in most previous work outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them on the basis of the theory of on-line learning of non-stationary time series. In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm, which can track the changing data source adaptively by forgetting the effect of past data gradually. Then the score for any given data is calculated to measure its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model. Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data, and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.

This paper is concerned with the problem of detecting outliers from unlabeled data. In prior work we have developed SmartSifter, which is an on-line outlier detection algorithm based on unsupervised learning from data. On the basis of SmartSifter this paper yields a new framework for outlier filtering using both supervised and unsupervised learning techniques iteratively in order to make the detection process more effective and more understandable. The outline of the framework is as follows: In the first round, for an initial dataset, we run SmartSifter to give each data a score, with a high score indicating a high possibility of being an outlier. Next, giving positive labels to a number of higher scored data and negative labels to a number of lower scored data, we create labeled examples. Then we construct an outlier filtering rule by supervised learning from them. Here the rule is generated based on the principle of minimizing extended stochastic complexity. In the second round, for a new dataset, we filter the data using the constructed rule, then among the filtered data, we run SmartSifter again to evaluate the data in order to update the filtering rule. Applying of our framework to the network intrusion detection, we demonstrate that 1) it can significantly improve the accuracy of SmartSifter, and 2) outlier filtering rules can help the user to discover a general pattern of an outlier group.

Outlier detection is a fundamental issue in data mining, speci cally in fraud detection, network intrusion detection, network monitoring, etc. SmartSifter, which we abbreviate as SS, is an outlier detection engine adrressing this problem from the viewpoint of statistical learning theory. This paper provides a theoretical basis for SS and empirically demonstrates its effectiveness. SS detects outliers in an online process through the on-line unsupervised learning of a probabilistic model (using a finite mixture model) of the information source. Each time a datum is input SS employs an on-line discounting learning algorithm to learn the probabilistic model. A score is given to the datum based on the learned model, with a high score indicating a high possibility of being a statistical outlier. The novel features of SS are: 1) it is adaptive to non-stationary sources of data; 2) a score has a clear statistical/information-theoretic meaning; 3) it is computationally inexpensive; and 4) it can handle both categorical and continuous variables. An experimental application to network intrusion detection shows that SS was able to identify data with high scores that corresponded to attacks, with low computational costs. Further experimental application has identified a number of meaningful rare cases in actual health insurance pathology data from Australia's Health Insurance Commission.

We consider an on-line learning model of rational choice, in which the goal of an agent is to choose its actions so as to maximize the number of successes, while learning about its reacting environment through th$e very sctions.In particular, we consider a model of tennis play, in which the only actions that the player can take are a 'pass' and a 'lob,' and the opponent is modeled by two linear (probabilistic) functions ~'(r) = alr + bl and jp(r) = a2r + ~, specifying the probabllit y that a 10b (and a pass, respectively) will win a point when the proportion of lobs in the put trials is r.We measure the performance of a player in this model by its expected regret, namely how many less points it expects to win as compared to the ideal player (one that knows the two probabilistic functions) ss a function oft, the total number of trials.which is unknown to the player a priori.A&urning that the probabilistic functions satisfy the matching shoulder condition, i.e. f~(0) = ~P (l), we obtain a variety of upper bounds for sssmuptions and restrictions of varying degrees, ranging from o(logt),'o(t*), O(t+), O(t:), O(tf) to O(t$) as well as a matching lower bound of order $l(log t) for the most restrictive case.When the total number of trials t is given to the player in advance, the upper bo~nds can be improved sigrdkantly.