This paper presents an accelerated spherical K-means clustering algorithm for large-scale and high-dimensional sparse document data sets. We design an algorithm working in an architecture-friendly manner (AFM), which is a way of suppressing performance-degradation factors such as the numbers of instructions, branch mispredictions, and cache misses in CPUs of a computer system. For the AFM operation, we leverage universal characteristics (UCs) of the data, which are skewed distributions on data relationships. The UCs indicate that the most part of multiplications for similarity calculations is executed on high-document-frequency terms and the most part of a similarity is obtained by the multiplications regarding a few high mean-feature values. To extract the foregoing specific region on terms and mean-feature values, we construct a mean-inverted index partitioned into three regions by two structural parameters. Our algorithm optimizes the parameters by minimizing the approximate number of the multiplications corresponding to the instructions based on our efficient pruning method, reduces conditional branches by sharing the index structure with all the objects, and keeps in the caches the frequently used data in the foregoing specific region. We experimentally demonstrate that our algorithm efficiently achieves superior speed performance in large-scale documents compared with algorithms using the state-of-the-art techniques.

We propose a new method of constructing a variable bin width histogram that can accommodate the unbalanced distribution of the samples yet retaining, as a whole, the good aspect of both equal width (EW) and equal-area (EA) histograms that are being used popularly for data visualization and analysis. We formulate this as an optimal change point detection problem in which the bin boundaries are determined by minimizing the sum of the absolute error or the squared error in each bin. The former is based on Distance Minimization (DM) and new, and the latter is based on Variance Minimization (VM) and is considered the state-of-the-art. The constructed histograms can effectively be used to detect and visualize hidden outliers/anomalies by applying the interquartile range method in each bin. The final histograms are obtained by adjusting bin boundaries and heights accordingly after removing the detected outliers/anomalies. We further propose a method to annotate the constructed bins if the data for annotation is given for each sample as a set of nominal variables, using z-score with respect to their distribution within each bin. We applied our method to both real vinyl greenhouse datasets and two different sets of three synthetic datasets, and confirmed that both DM and VM methods work as intended, both can represent the sample distribution with a smaller number of bins than those by EW and EA methods, The use of interquartile range method can detect anomalies as well as outliers, and the terms selected for annotation are interpretable and reasonable. EW and EA methods have contrasting properties. DM and VM methods lie in between, but the former is closer to EA method and the latter to EW method. DM method runs substantially faster than VM method and performs slightly better than VM method in outlier detection and annotation tasks.

Counting motifs in an uncertain graph for which each link is associated with a connection probability is computationally expensive when the graph is huge due to the extremely large number of possible worlds. Natural approach is to rely on sampling-based approximation methods, but this still needs many sample graphs for obtaining accurate results. We propose a novel method that analytically computes the expected frequency of motif without relying on expensive sampling. Marginalizing the probability of each possible world on a candidate motif can drastically reduce the number of possible worlds that need be considered when the size of motif is small. Experiments using real-world data confirm that the proposed method is effective and efficient. It is far better than the state-of-the-art sampling-based method. The accuracy is guaranteed and the running time is about 4 order of magnitude faster. It runs at a speed that does not depend on the connection probability.

We challenge the problem of efficiently identifying critical links that substantially degrade network performance if they do not function under a realistic situation where each link is probabilistically disconnected, e.g., unexpected traffic accident in a road network and unexpected server down in a communication network. To solve this problem, we utilize the bridge detection technique in graph theory and efficiently identify critical links in case the node reachability is taken as the performance measure.To be more precise, we define a set of target nodes and a new measure associated with it, Target-oriented latent link Criticalness Centrality (TCC), which is defined as the marginal loss of the expected number of nodes in the network that can reach, or equivalently can be reached from, one of the target nodes, and compute TCC for each link by use of detected bridges. We apply the proposed method to two real-world networks, one from social network and the other from spatial network, and empirically show that the proposed method has a good scalability with respect to the network size and the links our method identified possess unique properties. They are substantially more critical than those obtained by the others, and no known measures can replace the TCC measure.

We address the problem of opening and closing shops in group competitive environment, i.e., shops in the same group work cooperatively and those in different groups competitively, and analyze how the market share and location changes over time. We formulate a stochastic utility of each shop as a function of shop distance and attractiveness from which a market share is computed by weighting consumers buying power. We further place a constraint on the traveling time, which is crucial to reduce the computation time, and use a marginal gain of the market share as a measure to rank the candidate location. Using the real dataset of three convenience stores in four cities in Japan, we confirm that, despite the simplification we made in the model, rankings of the existing shops are shown to be high which implies that our model is reasonable. Further, comparison with the baseline gravity model shows that our model gives much more realistic results. Analyses of the dynamics of opening and closing shops indicate that the reasonable time-bound for walking is about 10 min., the market share of each group, thus total share, eventually increases although small, and the difference of the share within each group gradually becomes smaller, revealing that the spatial distribution of the shops in each group becomes more uniform.

Ranking nodes in uncertain graph is computationally expensive when the graph is huge due to the extremely large number of possible worlds. Some approximation is needed in general. We focus on PageRank centrality measure to rank and propose a method that does not use any approximation for uncertain graph in which all the links can be uncertain. We first compute the expected transition matrix over all the possible graphs accurately and then run PageRank algorithm only once to rank the nodes (p-avg approach). This is not the same as computing the scores for each individual graph first and then rank the nodes by taking their average (s-avg approach). Exact computation of the latter is not possible because of the heavy computational load and only the approximate scores are obtained by limiting the number of graphs by sampling. We have tested the performance from various angles using three real world networks. We show that the proposed method (p-avg approach) gives very high precision to the s-avg approach for highly ranked nodes and can be a good alternative to it. Pactically, the p-avg approach runs orders of magnitude, i.e., sample size, faster than the s-avg approach.

At its heart the act of reviewing is very subjective, but in reality many factors would influence user’s decision. This can be called social influence bias. We pick two factors, “Who” and “When” and discuss which factor is more influential when a user posts his/her own rate in an online review syst em. We consider two kinds of users: real and virtual. In the former each user has its own metric, but in the latter the metric is assigned to the order of review posting actions (rating). We propose a weighted multinomial generative model that can learn the factor metric quite efficiently from a vast amount of data already available in many online review systems. If the model can explain the data well enough, this implies that such a social bias does exist. We evaluate the proposed method and confirm its effectiveness by five review datasets, and empirically clarify that there is no universal solution, but the social bias does exist. In reality the influential factor depends on each dataset, the majority of users is normal (average), and there are two small groups of users, each with high metric value and low metric value.

Group centrality is an extension of the conventional node centrality in which the importance of a group of nodes together is the target for performance evaluation. We used this notion and formulated a link creation problem to a spatial network. The kind of problem we want to solve is to find the best places to construct k new roads to maximize the evacuation performance. The problem is formulated as an optimization problem to maximize the gain of the group closeness centrality by creating a set of new roads (k links) with the constraints on the road range distance (link length limit Δ). The problem is NP-hard. We show that this problem is reduced to a node selection problem and the objective function is submodular when there is no constraint on the link length limit. We devised an efficient greedy algorithm to search for the best k new roads under the constraint of Δ that comprises three steps: centrality calculation, parents selection and nodes selection. We applied this algorithm to three real road networks of different cities and evaluated its performance with respect to k and Δ. The algorithm is quite efficient and obtains the efficiency gain of 10^3 to 10^6 compared with a naive method in which every single node is blindly tested as a candidate from which to create a new road.

We address a problem of classifying and characterizing spatial networks in terms of local connection patterns of node degrees, by especially focusing on the property that the maximum node degrees of these networks are restricted to relatively small numbers. To this end, we propose two methods to analyze a set of such networks by 1) enumerating and counting the combinations of node degrees with respect to connected pair or triple nodes, 2) calculating feature vectors of these networks, which express distributions of mixing patterns' Z scores, and 3) constructing a dendrogram of these networks based on a cosine similarity between these feature vectors. In our experiments using spatial networks constructed from urban streets of seventeen cities, we confirm that our method can produce intuitively interpretable results which reflect regional characteristics of these cities. Moreover, we show that these characteristics can be reasonably described in terms of a relatively small number of selected mixing patterns, as main building blocks of given spatial networks.

We address a problem of extracting functionally similar regions in urban streets regarded as spatial networks. Such characteristics of regions will play important roles for developing and planning city promotion, travel tours and so on, as well as understanding and improving the usage of urban streets. In order to analyze such functionally similar regions, we propose an acceleration method of the FCE (functional cluster extraction) algorithm equipped with the lazy evaluation and pivot pruning techniques, which enables to efficiently deal with several large-scale networks. In our experiments using urban streets of six cities, we show that our proposed method achieved a reasonably high acceleration performance. Then, we show that functional cluster produced by our method are useful for understanding the properties of areas in a series of visualization results.

This paper presents an accelerated k-means clustering algorithm suitable for a large-scale and numerous-class data set. The proposed iterative algorithm avoids unnecessary exact distance calculations, especially in the early and the last stage in its convergence process, and retains the same result as the standard algorithm. This is efficiently performed by two distinct components. One uses the lower bounds on exact distances between objects and centroids for the acceleration in the early stage. The lower bound is calculated by the triangle inequality with newly introduced fixed points called pivots. The other component for the last stage skips the distance calculation between an invariant centroid and an object satisfying the following condition. The cluster to which the object is assigned remains unchanged, i.e., its centroid is also invariant. For much further speed-up, we can incorporate an existing algorithm into the proposed algorithm as an extension, which often performs a complementary role in the middle stage. The experimental results we obtained on large-scale and high-dimensional image data sets demonstrate that given a large k value, the proposed algorithm outperforms existing algorithms in terms of both the reduction rate of distance calculations and elapsed time.

Acquiring a network of trust relations among users in social media sites, e.g., item-review sites, is important for analyzing users' behavior and efficiently finding reliable information on the Web. We address the problem of predicting trustlinks among users for an item-review site. Non-negative matrix factorization (NMF) methods have recently been shown useful for trust-link prediction in such a site where both link and activity information is available. Here, a user activity in an item-review site means posting a review and giving a rating for an item. In this paper, for better trust-link prediction, we propose a new NMF method that incorporates people's evaluation of users' activities as well as trust-links and users' activities themselves. We further apply it to an analysis of users' behavior. Using two real world item-review sites, we experimentally demonstrate the effectiveness of the proposed method.

The structures of some real-world networks are dynamic in nature as time goes by. These changes consist of the addition or deletion of nodes or links and the rewiring of links. Even if link rewiring occurs, the influence degree tends to differ depending on the location in which it occurs, the nature of the nodes, and so forth. In this paper, by quantifying the influence degree of each node, we attempt to extract the influential structural changes wherein each node in a large population changes its function. Concretely, we define the node function as the PageRank convergence curve of the node and the influence degree affecting the node as distance based on a correlation coefficient of convergence curves before and after change occurs. We then propose the Structural Change Influence Measure (SCIM), which is the average value of the influence degree of all nodes. Based on experimental evaluation using several synthetic and real networks, we found five promising properties of our proposed measure. Our method indicates a higher value for changes in: 1) number of link rewirings; 2) concentrated link deleting; 3) link addition between distant nodes; 4) link addition between important and unimportant nodes; and 5) link deletion between communities.

Node influence is yet another useful concept to quantify how important each node is over a network and can share the same role that other centrality measures have. It can provide new insight into the information diffusion phenomena such as existence of epidemic threshold which the other topology-based centralities cannot do. We focus on information diffusion process based on the SIR model, and address the problem of efficiently estimating the influence degree for all the nodes in the network. The proposed approach is a further improvement over the existing work of the bond percolation process [1], [2] which was demonstrated to be very effective, i.e., three orders of magnitude faster than direct Monte Carlo simulation, in approximately solving the influence maximization problem under a greedy search strategy. We introduce two pruning techniques which improve computational efficiency by an order of magnitude. This is a generic approach for the SIR model setting and can be instantiated to any specific diffusion model. It does not require any approximations or assumptions to the model, e.g., small diffusion probability, shortest path, maximum influence path, etc., that were needed in the existing approaches. We demonstrate its effectiveness by extensive experiments on two large real social networks. Main finding includes that different network structures have different epidemic thresholds and the node influence can identify influential nodes that the other centrality measures cannot.

We address a problem of efficiently estimating the influence of a node in information diffusion over a social network. Since the information diffusion is a stochastic process, the influence degree of a node is quantified by the expectation, which is usually obtained by very time consuming many runs of simulation. Our contribution is that we proposed a framework for predictive simulation based on the leave-N-out cross validation technique that well approximates the error from the unknown ground truth for two target problems: one to estimate the influence degree of each node, and the other to identify top-K influential nodes. The method we proposed for the first problem estimates the approximation error of the influence degree of each node, and the method for the second problem estimates the precision of the derived top-K nodes, both without knowing the true influence degree. We experimentally evaluate the proposed methods using the three real world networks, and show that they can serve as a good measure to solve the target problems with far fewer runs of simulation ensuring the accuracy if N is appropriately chosen, and that estimating the top-K nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree.

We address a problem of detecting changes in information posted to social media taking both content and posting time distributions into account. To this end, we introduce a generative model consisting of two components, one for a content distribution and the other for a timing distribution, approximating the shape of the parameter change by a series of step functions. We then propose an efficient algorithm to detect change points by maximizing the likelihood of generating the observed sequence data, which has time complexity almost proportional to the length of observed sequence (possible change points). We experimentally evaluate the method on synthetic data streams and demonstrate the importance of considering both distributions to improve the accuracy. We, further, apply our method to real scoring stream data extracted from a Japanese word-of-mouth communication site for cosmetics and show that it can detect change points and the detected parameter change patterns are interpretable through an in-depth investigation of actual reviews.

We addressed the problem of detecting the change in behavior of information diffusion over a social network which is caused by an unknown external situation change using a small amount of observation data in a retrospective setting. The unknown change is assumed effectively reflected in changes in the parameter values in the probabilistic information diffusion model, and the problem is reduced to detecting where in time and how long this change persisted and how big this change is. We solved this problem by searching the change pattern that maximizes the likelihood of generating the observed information diffusion sequences, and in doing so we devised a very efficient general iterative search algorithm using the derivative of the likelihood which avoids parameter value optimization during each search step. This is in contrast to the naive learning algorithm in that it has to iteratively update the patten boundaries, each requiring the parameter value optimization and thus is very inefficient. We tested this algorithm for two instances of the probabilistic information diffusion model which has different characteristics. One is of information push style and the other is of information pull style. We chose Asynchronous Independent Cascade (AsIC) model as the former and Value-weighted Voter (VwV) model as the latter. The AsIC is the model for general information diffusion with binary states and the parameter to detect its change is diffusion probability and the VwV is the model for opinion formation with multiple states and the parameter to detect its change is opinion value. The results tested on these two models using four real-world network structures confirm that the algorithm is robust enough and can efficiently identify the correct change pattern of the parameter values. Comparison with the naive method that finds the best combination of change boundaries by an exhaustive search through a set of randomly selected boundary candidates shows that the proposed algorithm far outperforms the native method both in terms of accuracy and computation time.

This paper presents a fast approximate similarity search method for finding the most similar object to a given query object from an object set with a dissimilarity with a success probability exceeding a given value. As a search index, the proposed method utilizes a degree-reduced k-nearest neighbor (k-DR) graph constructed from the object set with the dissimilarity, and explores the k-DR graph along its edges using a greedy search (GS) algorithm starting from multiple initial vertices with parallel processing. In the graph-construction stage, the structural parameter k of the k-DR graph is determined so that the probability with which at least one search trial of those with multiple initial vertices succeeds is more than the given success probability. To estimate the greedy-search success probability, we introduce the concept of a basin in the k-DR graph. The experimental results on a real data set verify the approximation scheme and high search performance of the proposed method and demonstrate that it is superior to E2LSH in terms of the expected search cost.

We address the problem of estimating the parameters, from observed data in a complex social network, for an information diffusion model that takes time-delay into account, based on the popular independent cascade (IC) model. For this purpose we formu

We address the problem of predicting the expected opinion share over a social network at a target time from the opinion diffusion data under the value-weighted voter model with multiple opinions. The value update algorithm ensures that it converges to a correct solution and the share prediction results outperform a simple linear extrapolation approximation when the available data is limited. We further show in an extreme case of complete network that the opinion with the highest value eventually takes over, and the expected share prediction problem with uniform opinion value is not well-defined and any opinion can win.

This paper presents a novel graph-based approach for solving a problem of fast finding a speech model acoustically similar to a query model from a large set of speech models. Each speech model in the set is represented by a Gaussian mixture model and dissimilarity from a GMM to another is measured with a Kullback-Leibler divergence (KLD). Conventional pruning techniques based on the triangle inequality for fast similarity search are not available because the model space with a KLD is not a metric space. We propose a search method that is characterized by an index of a degree-reduced nearest neighbor (DRNN) graph. The search method can efficiently find the most similar (closest) GMM to a query, exploring the DRNN graph with a best-first manner. Experimental evaluations on utterance GMM search tasks reveal a significantly low computational cost of the proposed method.

We address the problem of minimizing the propagation of undesirable things, such as computer viruses or malicious rumors, by blocking a limited number of links in a network, which is converse to the influence maximization problem in which the most influential nodes for information diffusion is searched in a social network. This minimization problem is more fundamental than the problem of preventing the spread of contamination by removing nodes in a network. We introduce two definitions for the contamination degree of a network, accordingly define two contamination minimization problems, and propose methods for efficiently finding good approximate solutions to these problems on the basis of a naturally greedy strategy. Using large social networks, we experimentally demonstrate that the proposed methods outperform conventional link-removal methods. We also show that unlike the case of blocking a limited number of nodes, the strategy of removing nodes with high out-degrees is not necessarily effective for these problems.

We consider the problem of finding influential nodes for information diffusion on a social network under the independent cascade model. It is known that the greedy algorithm can give a good approximate solution for the problem. Aiming to obtain efficient methods for finding better approximate solutions, we explore what structual feature of the underlying network is relevant to the greedy solution that is the approximate solution by the greedy algorithm. We focus on the SR-community structure, and analyze the greedy solution in terms of the SR-community structure. Using real large social networks, we experimentally demonstrate that the SR-community structure can be more strongly correlated with the greedy solution than the community structure introduced by Newman and Leicht.

This paper presents a method for designing semi-supervised classifiers trained on labeled and unlabeled samples. We focus on probabilistic semi-supervised classifier design for multi-class and single-labeled classification problems, and propose a hybrid approach that takes advantage of generative and discriminative approaches. In our approach, we first consider a generative model trained by using labeled samples and introduce a bias correction model, where these models belong to the same model family, but have different parameters. Then, we construct a hybrid classifier by combining these models based on the maximum entropy principle. To enable us to apply our hybrid approach to text classification problems, we employed naive Bayes models as the generative and bias correction models. Our experimental results for four text data sets confirmed that the generalization ability of our hybrid classifier was much improved by using a large number of unlabeled samples for training when there were too few labeled samples to obtain good performance. We also confirmed that our hybrid approach significantly outperformed generative and discriminative approaches when the performance of the generative and discriminative approaches was comparable. Moreover, we examined the performance of our hybrid classifier when the labeled and unlabeled data distributions were different.

It is important for online stores to improve customer lifetime value (LTV) if they are to increase their profits. Conventional recommendation methods suggest items that best coincide with user's interests to maximize the purchase probability, and this does not necessarily help improve LTV. We present a novel recommendation method that maximizes the probability of the LTV being improved, which can apply to both measured and subscription services. Our method finds frequent purchase patterns among high-LTV users and recommends items for a new user that simulate the found patterns. Using survival analysis techniques, we efficiently find the patterns from log data. Furthermore, we infer a user's interests from the purchase history based on maximum entropy models and use the interests to improve recommendation. Since a higher LTV is the result of greater user satisfaction, our method benefits users as well as online stores. We evaluate our method using two sets of real log data for measured and subscription services.

A crucial issue inputting solid oxide fuel cells (SOFCs) into practical use is the establishment of a technique for evaluating the deterioration of SOFCs. We attempted to capture fracture dynamics measured by acoustic emission (AE) method, employing the following approaches: (1) detection of AE waves utilizing burst extraction method, (2) clustering of AE waves based on the burst level to identify AE types, and (3) visualization of fracture dynamics using adopted self-organizing map. We empirically validated our approach, and obtained a map that can interpret fracture dynamics as physical phenomenon.

A set covering greedy algorithm is proposed for solving the influence maximization problem in social networks. Two information diffusion models are considered: Independent Cascade Model and Linear Threshold Model. The proposed algorithm is compared with traditional maximization algorithms such as simple greedy and degree centrality using three data sets. In addition, an algorithm for mapping social networks is proposed, which allows visualizing the infection process and how the different algorithms evolve. The proposed approach is useful for mining large social networks.

We propose a model for user purchase behavior in online stores that provide recommendation services. We model the purchase probability given recommendations for each user based on the maximum entropy principle using features that deal with recommendations and user interests. The proposed model enable us to measure the effect of recommendations on user purchase behavior, and the effect can be used to evaluate recommender systems. We show the validity of our model using the log data of an online cartoon distribution service, and measure the recommendation effects for evaluating the recommender system.

We propose a new method, parametric embedding (PE), that embeds objects with the class structure into a low-dimensional visualization space. PE takes as input a set of class conditional probabilities for given data points and tries to preserve the structure in an embedding space by minimizing a sum of Kullback-Leibler divergences, under the assumption that samples are generated by a gaussian mixture with equal covariances in the embedding space. PE has many potential uses depending on the source of the input data, providing insight into the classifier's behavior in supervised, semisupervised, and unsupervised settings. The PE algorithm has a computational advantage over conventional embedding methods based on pairwise object relations since its complexity scales with the product of the number of objects and the number of classes. We demonstrate PE by visualizing supervised categorization of Web pages, semisupervised categorization of digits, and the relations of words and latent topics found by an unsupervised algorithm, latent Dirichlet allocation.

Online stores providing subscription services need to extend user subscription periods as long as possible to increase their profits. Conventional recommendation methods recommend items that best coincide with user's interests to maximize the purchase probability, which does not necessarily contribute to extend subscription periods. We present a novel recommendation method for subscription services that maximizes the probability of the subscription period being extended. Our method finds frequent purchase patterns in the long subscription period users, and recommends items for a new user to simulate the found patterns. Using survival analysis techniques, we efficiently extract information from the log data for finding the patterns. Furthermore, we infer user's interests from purchase histories based on maximum entropy models, and use the interests to improve the recommendations. Since a longer subscription period is the result of greater user satisfaction, our method benefits users as well as online stores. We evaluate our method using the real log data of an online cartoon distribution service for cell-phone in Japan.

A new approach to mapping high dimensional data into a low dimensional space embedding is presented. The aim of this approach is to project simultaneously the input data and the codebook vectors into a low dimensional output space, preserving the local neighborhood. The neural gas algorithm is used to obtain codebook vectors. A cost function based on the cross entropy (CE) between input and output probabilities is minimized by using a Newton-Raphson method. The new approach is compared with multidimensional scaling (MDS) using a benchmark data set and three high dimensional real world data sets. In comparison with MDS, our method delivers a clear visualization of both data points and codebooks, and better CE and topology preservation measurements.

We propose a new unsupervised learning method called multinomial PCA (MuPCA) for efficiently extracting the major latent topics from a document stream based on the "bag-of-words" (BOW) representation of a document. Unlike PCA, MuPCA follows a suitable probabilistic generative model for the document stream represented as time-series of word-frequency vectors. Using real data of document streams on the Web, we experimentally demonstrate the effectiveness of the proposed method.

In this paper, we study weight sharing on the naive Bayes document model. Firstly we consider splitting words into a relatively small number of groups such that words in each group have the same parameter value. This problem can be regarded as a probabilistic parameter sharing task. In this task, we formalize the problem in terms of maximum likelihood estimation, and then propose an algorithm for this purpose. Secondly we focus on an adaptive hyperparameter estimation problem based on prior distributions constructed by using such word groups. This problem can be regarded as a hyperparameter sharing task. In this task, we describe a framework and algorithm, which enables to derive the unique optimal solution in the context of leave-one-out cross validation. In our experiments using a benchmark document set called webkb, we show a series of simulation results using the proposed algorithms.

We present a method to find a succinct neural network having shared weights. We focus on weight sharing. Weight sharing constrains the freedom of weight values and weights are allowed to have one of common weights. A near-zero common weight can be eliminated, called weight pruning. Recently, a weight sharing method called BCW has been proposed. The BCW employs merge and split operations based on 2nd-order optimal criteria, and can escape local optima through bidirectional clustering. However, the BCW assumes a vital network parameter J, the number of hidden units, is given. This paper modifies the BCW to make the procedure faster so that the selection of J based on cross-validation can be done in reasonable CPU time. Our experiments showed that the proposed method can restore the original model for an artificial data set, and finds a small number of common weights and an interesting tendency for a real data set.

In this paper, we consider models for estimating categories of documents and extracting characteristic words of such categories. To this end, we focus on three models, i.e., naive Bayes and two types of neural networks formalized as statistical models. Here, suitable categories of documents are estimated based on posterior probabilities, and characteristic words are extracted based on the magnitude of resulting parameter values. In our experiments using a set of real Web pages, we compare these models in the aspect of categorization performances and extraction capabilities of characteristic words.

In this paper, we propose a new method, Parametric Embedding (PE), for visualizing the posteriors estimated over a mixture model. PE simultane- ously embeds both objects and their classes in a low-dimensional space. PE takes as input a set of class posterior vectors for given data points, and tries to preserve the posterior structure in an embedding space by minimizing a sum of Kullback-Leibler divergences, under the assump- tion that samples are generated by a Gaussian mixture with equal covari- ances in the embedding space. PE has many potential uses depending on the source of the input data, providing insight into the classifier’s be- havior in supervised, semi-supervised and unsupervised settings. The PE algorithm has a computational advantage over conventional embedding methods based on pairwise object relations since its complexity scales with the product of the number of objects and the number of classes. We demonstrate PE by visualizing supervised categorization of web pages, semi-supervised categorization of digits, and the relations of words and latent topics found by an unsupervised algorithm, Latent Dirichlet Allo- cation.

In this paper, we address the problem of detecting multiple topics or categories of text where each text is not assumed to belong to one of a number of mutually exclusive categories. Conventionally, the binary classification approach has been employed, in which whether or not text belongs to a category is judged by the binary classifier for every category. In this paper, we propose a more sophisticated approach to simultaneously detect multiple categories of text using parametric mixture models (PMMs), newly presented in this paper. PMMs are probabilistic generative models for text that has multiple categories. Our PMMs are essentially different from the conventional mixture of multinomial distributions in the sense that in the former several basis multinomial parameters are mixed in the parameter space, while in the latter several multinomial components are mixed. We derive efficient learning algorithms for PMMs within the framework of the maximum a posteriori estimate. We also empirically show that our method can outperform the conventional binary approach when applied to multitopic detection of World Wide Web pages, focusing on those from the "yahoo.com" domain.

We propose probabilistic generative models, called parametric mix- ture models (PMMs), for multiclass, multi-labeled text categoriza- tion problem. Conventionally, the binary classi(cid:12)cation approach has been employed, in which whether or not text belongs to a cat- egory is judged by the binary classi(cid:12)er for every category. In con- trast, our approach can simultaneously detect multiple categories of text using PMMs. We derive e(cid:14)cient learning and prediction algo- rithms for PMMs. We also empirically show that our method could signi(cid:12)cantly outperform the conventional binary methods when ap- plied to multi-labeled text categorization using real World Wide Web pages.

We describe an experimental study for discovering underlying laws of market capitalization using BS (Balance Sheet) items. For this purpose, we apply law discovery methods based on neural networks: RF5 (Rule Finder) discovers a single numeric law from data containing only numeric values, RF6 discovers a set of nominally conditioned polynomials from data containing both nominal and numeric values, and MCV regularizer is used to improve both the generalization performance and the readability. Our preliminary experimental results show that these methods are promising for discovering underlying laws from financial data.

This article compares three penalty terms with respect to the efficiency of supervised learning, by using first- and second-order off-line learning algorithms and a first-order on-line algorithm. Our experiments showed that for a reasonably adequate penalty factor, the combination of the squared penalty term and the second-order learning algorithm drastically improves the convergence performance in comparison to the other combinations, at the same time bringing about excellent generalization performance. Moreover, in order to understand how differently each penalty term works, a function surface evaluation is described. Finally, we show how cross validation can be applied to find an optimal penalty factor.

Second-order learning algorithms based on quasi-Newton methods have two problems. First, standard quasi-Newton methods are impractical for large-scale problems because they require N2 storage space to maintain an approximation to an inverse Hessian matrix (N is the number of weights). Second, a line search to calculate a reasonably accurate step length is indispensable for these algorithms. In order to provide desirable performance, an efficient and reasonably accurate line search is needed. To overcome these problems, we propose a new second-order learning algorithm. Descent direction is calculated on the basis of a partial Broydon-Fletcher-Goldfarb-Shanno (BFGS) update with 2Ns memory space (s < < N), and a reasonably accurate step length is efficiently calculated as the minimal point of a second-order approximation to the objective function with respect to the step length. Our experiments, which use a parity problem and a speech synthesis problem, have shown that the proposed algorithm outperformed major learning algorithms. Moreover, it turned out that an efficient and accurate step-length calculation plays an important role for the convergence of quasi-Newton algorithms, and a partial BFGS update greatly saves storage space without losing the convergence performance.