Search

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connect- ing those elements increases and when the “length” of paths decreases. It turns out that the square root of the average commute time is a Eu- clidean distance and that the pseudoinverse of the Laplacian matrix is a kernel (its elements are inner products closely related to commute times). A procedure for computing the subspace projection of the node vectors of the graph that preserves as much variance as possible in terms of the commute-time distance – a principal component analysis (PCA) of the graph – is also introduced. This graph PCA provides a nice interpreta- tion to the “Fiedler vector”, widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where sug- gestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities (the pseudoinverse of the Laplacian matrix and the “random-forest matrix”) perform well in comparison with other methods. The model, which nicely fits into the so-called “statistical relational learning” framework, could also be usedto compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a database.

This work presents a systematic comparison between seven kernels (or similarity matrices) on a graph, on a collaborative recommendation task involving a database. The database is viewed as a graph where elements are represented as nodes and relations as links between nodes. From this graph, seven kernels are computed, leading to a set of meaningful proximity measures between nodes, allowing to answer questions about the structure of the graph under investigation; in particular, recommend items to users. Cross-validation results indicate that a simple nearest-neighbours rule based on the similarity measure provided by the regularized Laplacian, the Markov diffusion and the commute time kernels performs best. We therefore recommend the use of the commute time kernel for computing similarities between elements of a database, for two reasons: (1) it has a nice appealing interpretation in terms of random walks and (2) no parameter needs to be adjusted.

In this short paper, we show that Kleinberg's hubs and authorities model (HITS) is simply Principal Components Analysis (PCA ­ maybe the most widely used multivariate statistical analysis method), albeit without centering, applied to the adjacency matrix of the graph of web pages. In addition to providing a new interpretation for HITS, this result suggests to rely on existing work, already published in the multivariate statistical analysis litterature (extensions of PCA), in order to design new web pages ranking procedures.

This work presents some general procedures for computing dissimilarities between nodes of a weighted, undirected, graph. It is based on a Markov-chain model of random walk through the graph. This method is applied on the architecture of a Multi Agent System (MAS), in which each agent can be considered as a node and each interaction between two agents as a link. The model assigns transition probabilities to the links between agents, so that a random walker can jump from agent to agent. A quantity, called the average first-passage time, computes the average number of steps needed by a random walker for reaching agent k for the first time, when starting from agent i. A closely related quantity, called the average commute time, provides a distance measure between any pair of agents. Yet another quantity of interest, closely related to the average commute time, is the pseudoinverse of the Laplacian matrix of the graph, which represents a similarity measure between the nodes of the graph. These quantities, representing dissimilarities (similarities) between any two agents, have the nice property of decreasing (increasing) when the number of paths connecting two agents increases and when the "length" of any path decreases. The model is applied on a collaborative filtering task where suggestions are made about which movies people should watch based upon what they watched in the past. For the experiments, we build a MAS architecture and we instantiated the agents belief-set from a real movie database. Experimental results show that the Laplacian-pseudoinverse based similarity outperforms all the other methods.

In this work, we show that Kleinberg's hubs and authorities model (HITS) is simply principal components analysis (PCA; maybe the most widely used multivariate statistical analysis method), albeit without centering, applied to the adjacency matrix of the graph of Web pages. We further show that a variant of HITS, SALSA, is closely related to correspondence analysis, another standard multivariate statistical analysis method. In addition, to provide a clear statistical interpretation for HITS, this result suggests to rely on existing work already published in the multivariate statistical analysis literature (extensions of PCA or correspondence analysis) in order to analyse or design new Web pages scoring procedures.

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted, undirected, graph. It is based on a Markov-chain model of random walk through the database. The suggested quantities, representing dissimilarities (or similarities) between any two elements, have the nice property of decreasing (increasing) when the number of paths connecting those elements increases and when the "length" of any path decreases. The model is evaluated on a collaborative recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. The model, which nicely fits into the so-called "statistical relational learning" framework as well as the "link analysis " paradigm, could also be used to compute document or word similarities, and, more generally, could be applied to other database or web mining tasks.

In this paper,we present amaximumentropy (maxent) approach to the fusion of experts opinions, or classifiers outputs, problem. Themaxent approach is quite versatile and allows us to express in a clear, rigorous,way the a priori knowledge that is available on the problem. For instance, our knowledge about the reliability of the experts and the correlations between these experts can be easily integrated: Each piece of knowledge is expressed in the form of a linear constraint. An iterative scaling algorithm is used in order to compute the maxent solution of the problem. The maximum entropy method seeks the joint probability density of a set of random variables that has maximum entropy while satisfying the constraints. It is therefore the “most honest” characterization of our knowledge given the available facts (constraints). In the case of conflicting constraints, we propose to minimise the “lack of constraints satisfaction” or to relax some constraints and recompute the maximum entropy solution. The maxent fusion rule is illustrated by some simulations.

In this paper, we present a maximum entropy (maxent) approach to the fusion of experts opinions, or classifiers outputs, problem. The maxent approach is quite versatile and allows us to express in a clear, rigorous, way the a priori knowledge that is available on the problem. Each piece of knowledge is expressed in the form of a linear constraint. An iterative scaling algorithm is used in order to compute the maxent solution of the problem. The maximum entropy method seeks the joint probability density of a set of random variables that has maximum entropy while satisfying the constraints. It is therefore the "most honest" characterization of our knowledge given the available facts (constraints). In the case of conflicting constraints, we propose to minimize the "lack of constraints satisfaction" or to relax some constraints and recompute the maximum entropy solution. The maxent fusion rule is illustrated by some simulations.

This work presents some general procedures for computing dissimilarities between elements of a database or, more generally, nodes of a weighted, undirected, graph. It is based on a Markov-chain model of random walk through the database. The model assigns transition probabilities to the links between elements, so that a random walker can jump from element to element. A quantity, called the average first-passage time, computes the average number of steps needed by a random walker for reaching element k for the first time, when starting from element i. A closely related quantity, called the average commute time, provides a distance measure between any pair of elements. These quantities, representing dissimilarities between any two elements, have the nice property of decreasing when the number of paths connecting two elements increases and when the "length" of any path decreases. The model is applied on a collaborative filtering task.

In this work, we show that Kleinberg's hubs and authorities model is closely related to both correspondence analysis, a well-known multivariate statistical technique, and a particular Markov chain model of navigation through the web. The only difference between correspondence analysis and Kleinberg's method is the use of the average value of the hubs (authorities) scores for computing the authorities (hubs) scores, instead of the sum for Kleinberg's method. We also show that correspondence analysis and our Markov model are related to SALSA, a variant of Kleinberg's model. We finally suggest that the Markov model could easily be extended to the analysis of more general structures, such as relational databases.

This work presents a novel procedure for computing (1) distances between nodes of a weighted, undirected, graph, called the Euclidean commute time distance (ECTD), and (2) a subspace projection of the nodes of the graph that preserves as much variance as possible, in terms of the ECTD - a principal components analysis of the graph. It is based on a Markov-chain model of random walk through the graph. The model assigns transition probabilities to the links between nodes, so that a random walker can jump from node to node. A quantity, called the average commute time, computes the average time taken by a random walker for reaching node j for the first time when starting from node i, and coming back to node i. The square root of this quantity, the ECTD, is a distance measure between any two nodes, and has the nice property of decreasing when the number of paths connecting two nodes increases and when the "length" of any path decreases. The ECTD can be computed from the pseudoinverse of the Laplacian matrix of the graph, which is a kernel. We finally define the principal components analysis (PCA) of a graph as the subspace projection that preserves as much variance as possible, in terms of the ECTD. This graph PCA has some interesting links with spectral graph theory, in particular spectral clustering., Anglais

This thesis focuses particularly on the application of chemometrics in the field of analytical chemistry. Chemometrics (or multivariate analysis) consists in finding a relationship between two groups of variables, often called dependent and independent variables. In infrared spectroscopy for instance, chemometrics consists in the prediction of a quantitative variable (the obtention of which is delicate, requiring a chemical analysis and a qualified operator), such as the concentration of a component present in the studied product from spectral data measured on various wavelengths or wavenumbers (several hundreds, even several thousands). In this research we propose a methodology in the field of chemometrics to handle the chemical data (spectrophotometric data) which are often in high dimension. To handle these data, we first propose a new incremental method (step-by-step) for the selection of spectral data using linear and non-linear regression based on the combination of three principles: linear or non-linear regression, incremental procedure for the variable selection, and use of a validation set. This procedure allows on one hand to benefit from the advantages of non-linear methods to predict chemical data (there is often a non-linear relationship between dependent and independent variables), and on the other hand to avoid the overfitting phenomenon, one of the most crucial problems encountered with non-linear models. Secondly, we propose to improve the previous method by a judicious choice of the first selected variable, which has a very important influence on the final performances of the prediction. The idea is to use a measure of the mutual information between the independent and dependent variables to select the first one; then the previous incremental method (step-by-step) is used to select the next variables. The variable selected by mutual information can have a good interpretation from the spectrochemical point of view, and does not depend on the data di, (FSA 3)--UCL, 2003

In this work, we show that Kleinberg's hubs and authorities model is closely related to both correspondence analysis, a well-known multivariate statistical technique, and a particular Markov chain model of navigation through the web. The only difference between correspondence analysis and Kleinberg's method is the use of the average value of the hubs (authorities) scores for computing the authorities (hubs) scores, instead of the sum for Kleinberg's method. We also show that correspondence analysis and our Markov model are related to SALSA, a variant of Kleinberg's model. We finally suggest that the Markov model could easily be extended to the analysis of more general structures, such as relational databases.

In this work, we show that Kleinberg's hubs and authorities model is closely related to both correspondence analysis, a well-known multivariate statistical technique, and a particular Markov chain model of navigation through the web. The only difference between correspondence analysis and Kleinberg's method is the use of the average value of the hubs (authorities) scores for computing the authorities (hubs) scores, instead of the sum for Kleinberg's method. We also show that correspondence analysis and our Markov model are related to SALSA, a variant of Kleinberg'smodel.

It sometimes happens (for instance in case control studies) that a classifier is trained on a data set that does not reflect the true a priori probabilities of the target classes on real-world data. This may have a negative effect on the classification accuracy obtained on the real-world data set, especially when the classifier's decisions are based on the a posteriori probabilities of class membership. Indeed, in this case, the trained classifier provides estimates of the a posteriori probabilities that are not valid for this real-world data set (they rely on the a priori probabilities of the training set). Applying the classifier as is (without correcting its outputs with respect to these new conditions) on this new data set may thus be suboptimal. In this note, we present a simple iterative procedure for adjusting the outputs of the trained classifier with respect to these new a priori probabilities without having to refit the model, even when these probabilities are not known in advance. As a by-product, estimates of the new a priori probabilities are also obtained. This iterative algorithm is a straightforward instance of the expectation-maximization (EM) algorithm and is shown to maximize the likelihood of the new data. Thereafter, we discuss a statistical test that can be applied to decide if the a priori class probabilities have changed from the training set to the real-world data. The procedure is illustrated on different classification problems involving a multilayer neural network, and comparisons with a standard procedure for a priori probability estimation are provided. Our original method, based on the EM algorithm, is shown to be superior to the standard one for a priori probability estimation. Experimental results also indicate that the classifier with adjusted outputs always performs better than the original one in terms of classification accuracy, when the a priori probability conditions differ from the training set to the real-world data. The gain

It sometimes happens (for instance in case control studies) that a classifier is trained on a data set that does not reflect the true a priori probabilities of the target classes on real-world data. This may have a negative effect on the classification accuracy obtained on the real-world data set, especially when the classifier's decisions are based on the a posteriori probabilities of class membership. Indeed, in this case, the trained classifier provides estimates of the a posteriori probabilities that are not valid for this real-world data set (they rely on the a priori probabilities of the training set). Applying the classifier as is (without correcting its outputs with respect to these new conditions) on this new data set may thus be suboptimal. In this note, we present a simple iterative procedure for adjusting the outputs of the trained classifier with respect to these new a priori probabilities without having to refit the model, even when these probabilities are not known in advance. As a by-product, estimates of the new a priori probabilities are also obtained. This iterative algorithm is a straightforward instance of the expectation-maximization (EM) algorithm and is shown to maximize the likelihood of the new data. Thereafter, we discuss a statistical test that can be applied to decide if the a priori class probabilities have changed from the training set to the real-world data. The procedure is illustrated on different classification problems involving a multilayer neural network, and comparisons with a standard procedure for a priori probability estimation are provided. Our original method, based on the EM algorithm, is shown to be superior to the standard one for a priori probability estimation. Experimental results also indicate that the classifier with adjusted outputs always performs better than the original one in terms of classification accuracy, when the a priori probability conditions differ from the training set to the real-world data. The gain, Journal Article, Research Support, Non-U.S. Gov't, info:eu-repo/semantics/published

Background. Presently, the only sonographic parameters used to follow puberty in girls are size and morphology of the uterus and ovaries. Doppler of the uterine artery appears a useful complementary parameter to follow puberty. Objective. To determine the potential contribution of Doppler evaluation of the uterine artery in girls around puberty. Materials and methods. We investigated 61 healthy female volunteers aged 2-15 years (mean 10.3 years). In each girl we performed a standard pelvic transabdominal US examination, including measurement of the uterus and ovaries. Uterine arteries were visualized by colour Doppler and a pulsed signal was obtained in each patient. The blood flow velocity waveform was analysed and the pulsatility index (PI) was calculated. Growth of the uterus and ovaries was plotted against age, and the PI was compared to each of the other studied variables (age, size of uterus, volume of ovaries). Results. We observed a strong negative correlation between the PI of the uterine artery and the usually studied variables. We also observed a progressive modification of the Doppler signal pattern of the uterine artery during the establishment of puberty: the narrow systolic flow waves found in prepubertal girls were progressively replaced by a systolic-diastolic flow wave. Conclusions. The demonstration of diastolic flow can confirm the onset of puberty., SCOPUS: ar.j, info:eu-repo/semantics/published

SCOPUS: ar.j, info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

When using the hidden Markov models for speech recognition, it is usually assumed that the probability for a particular acoustic vector is emitted at a given time only depends on the current state and the current acoustic vector observed. This paper introduces another idea, i.e. in a given state, the acoustic vectors are generated by a linear stochastic differential equation. This extends a previous study in which it was assumed that the acoustic vectors are generated by a continuous Markov process. This is motivated by the fact that the time evolution of the acoustic vector is inherently dynamic and continuous, so that modeling could be performed in the continuous-time domain instead of the discrete-time domain., SCOPUS: cp.p, info:eu-repo/semantics/published

SCOPUS: ar.j, info:eu-repo/semantics/published

SCOPUS: ar.j, info:eu-repo/semantics/published

In this paper, we prove the stability of a certain class of nonlinear discrete MIMO (Multi-Input Multi-Output) systems controlled by a multilayer neural net with a simple weight adaptation strategy. The proof is based on the Lyapunov formalism. The stability statement is, however, only valid if the initial weight values are not too far from their optimal values that allow perfect model matching. We therefore propose to initialize the weights with values that solve the linear problem. This extends our previous work (Renders, 1993; Saerens, Renders & Bersini. 1993), where single-input single-output (SISO) systems were considered., SCOPUS: cp.p, info:eu-repo/semantics/published

When using hidden Markov models for speech recognition, it is usually assumed that the probability that a particular acoustic vector is emitted at a given time only depends on the current state and the current acoustic vector observed. In this paper, we introduce another idea, i.e. we assume that, in a given state, the acoustic vectors are generated by a continuous Markov process. Indeed, the time evolution of the acoustic vector is inherently dynamic and continuous, and sampling only occurs for the purpose of computation. This allows us to assign a probability density to the time trajectory of the acoustic vector inside the state, reflecting the probability that this particular path has been generated by the continuous Markov process associated with this state. Roughly speaking, it measures the "adequacy" of the observed trajectory with respect to an ideal trajectory, which is modelled by a vectorial linear differential equation. This model is introduced in order to describe the dynamic behaviour of the acoustic vector inside a state. Once the segmentation is fixed, reestimation formulae for the parameters of the continuous Markov process are derived for the Viterbi algorithm. As usual, the segmentation can be obtained by sampling the continuous process, and by applying dynamic programming to find the best path over all the possible sequences of states and all the possible durations. Finally, we sketch a possible generalization to path mixtures, for which different trajectories are available in each state. However, we have to stress that no experimental results are available at present. Indeed, we did not have the opportunity to test the algorithm on real speech. We are aware of the fact that the assumptions we did may not be appropriate for the modelling of speech. © 1993., SCOPUS: ar.j, info:eu-repo/semantics/published

The present study examines the time course of lexical access in written-word recognition by comparing words with early and late uniqueness points (UPs). Three experiments, which used a normal (simultaneous) presentation of the letters under 3 different tasks (gender classification, naming, and semantic classification) provided no evidence for sequential processing. Rather, a small advantage in favor of words with late UP was found, which may be interpreted in terms of the lower n-gram frequencies of early-UP words. Experiment 4 supported this interpretation and discussed an alternative interpretation in terms of parafoveal preview of the initial letters. A last experiment, which used an incremental presentation of the word letters, gave rise to a UP effect comparable in size to that obtained in an auditory study, suggesting that a temporal distribution of the signal is a sufficient condition for directional processing., SCOPUS: ar.j, info:eu-repo/semantics/published