Parallel Monte Carlo algorithms for information retrieval

In any data mining applications, automated text and text and image retrieval of information is needed. This becomes essential with the growth of the Internet and digital libraries. Our approach is based on the latent semantic indexing (LSI) and the corresponding term-by-document matrix suggested by Berry and his co-authors. Instead of using deterministic methods to find the required number of first "k" singular triplets, we propose a stochastic approach. First, we use Monte Carlo method to sample and to build much smaller size term-by-document matrix (e.g. we build k x k matrix) from where we then find the first "k" triplets using standard deterministic methods. Second, we investigate how we can reduce the problem to finding the "k"-largest eigenvalues using parallel Monte Carlo methods. We apply these methods to the initial matrix and also to the reduced one. The algorithms are running on a cluster of workstations under MPI and results of the experiments arising in textual retrieval of Web documents as well as comparison of the stochastic methods proposed are presented. (C) 2003 IMACS. Published by Elsevier Science B.V. All rights reserved.

What Monte Carlo models can do and cannot do efficiently?

The question "what Monte Carlo models can do and cannot do efficiently" is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Holder type conditions, as well as Korobov-like spaces. Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms - deterministic and randomized for both problems - numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented. (c) 2007 Elsevier Inc. All rights reserved.

Complexity of Monte Carlo algorithms for a class of integral equations

In this work we study the computational complexity of a class of grid Monte Carlo algorithms for integral equations. The idea of the algorithms consists in an approximation of the integral equation by a system of algebraic equations. Then the Markov chain iterative Monte Carlo is used to solve the system. The assumption here is that the corresponding Neumann series for the iterative matrix does not necessarily converge or converges slowly. We use a special technique to accelerate the convergence. An estimate of the computational complexity of Monte Carlo algorithm using the considered approach is obtained. The estimate of the complexity is compared with the corresponding quantity for the complexity of the grid-free Monte Carlo algorithm. The conditions under which the class of grid Monte Carlo algorithms is more efficient are given.

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices. Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both - systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed. A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix. (c) 2007 Elsevier Inc. All rights reserved.

Experimental design and model construction algorithms for radial basis function networks

New construction algorithms for radial basis function (RBF) network modelling are introduced based on the A-optimality and D-optimality experimental design criteria respectively. We utilize new cost functions, based on experimental design criteria, for model selection that simultaneously optimizes model approximation, parameter variance (A-optimality) or model robustness (D-optimality). The proposed approaches are based on the forward orthogonal least-squares (OLS) algorithm, such that the new A-optimality- and D-optimality-based cost functions are constructed on the basis of an orthogonalization process that gains computational advantages and hence maintains the inherent computational efficiency associated with the conventional forward OLS approach. The proposed approach enhances the very popular forward OLS-algorithm-based RBF model construction method since the resultant RBF models are constructed in a manner that the system dynamics approximation capability, model adequacy and robustness are optimized simultaneously. The numerical examples provided show significant improvement based on the D-optimality design criterion, demonstrating that there is significant room for improvement in modelling via the popular RBF neural network.

Effects of dietary fat modification on insulin sensitivity and on other risk factors of the metabolic syndrome—LIPGENE: a European randomized dietary intervention study

Background:Excessive energy intake and obesity lead to the metabolic syndrome (MetS). Dietary saturated fatty acids (SFAs) may be particularly detrimental on insulin sensitivity (SI) and on other components of the MetS. Objective:This study determined the relative efficacy of reducing dietary SFA, by isoenergetic alteration of the quality and quantity of dietary fat, on risk factors associated with MetS. Design:A free-living, single-blinded dietary intervention study. Subjects and Methods:MetS subjects (n=417) from eight European countries completed the randomized dietary intervention study with four isoenergetic diets distinct in fat quantity and quality: high-SFA; high-monounsaturated fatty acids and two low-fat, high-complex carbohydrate (LFHCC) diets, supplemented with long chain n-3 polyunsaturated fatty acids (LC n-3 PUFAs) (1.2 g per day) or placebo for 12 weeks. SI estimated from an intravenous glucose tolerance test (IVGTT) was the primary outcome measure. Lipid and inflammatory markers associated with MetS were also determined. Results:In weight-stable subjects, reducing dietary SFA intake had no effect on SI, total and low-density lipoprotein cholesterol concentration, inflammation or blood pressure in the entire cohort. The LFHCC n-3 PUFA diet reduced plasma triacylglycerol (TAG) and non-esterified fatty acid concentrations (P<0.01), particularly in men. Conclusion:There was no effect of reducing SFA on SI in weight-stable obese MetS subjects. LC n-3 PUFA supplementation, in association with a low-fat diet, improved TAG-related MetS risk profiles.

Effects of a novel galactooligosaccharide on the faecal microbiota of healthy and inflammatory bowel disease cats during a randomized, double-blind, cross-over feeding study

Inflammatory bowel disease (IBD) is a common gastrointestinal disorder of cats with no known aetiological agent. Previous work has suggested that the faecal microbiota of IBD cats is significantly different from that of healthy cats, including significantly lower bifidobacteria, bacteroides and total counts in IBD cats and significantly lower levels of sulfate-reducing bacteria in healthy cats. Prebiotics, including galactooligosaccharides (GOS), have been shown to elicit a bifidogenic effect in humans and other animals. The purpose of the current study was to examine the impact of a novel GOS supplementation on the faecal microbiota of healthy and IBD cats during a randomized, double-blind, cross-over feeding study. Eight oligonucleotide probes targeting specific bacterial populations and DAPI stain (total bacteria) were used to monitor the feline faecal microbiota. Overall, inter-animal variation was high; while a trend of increased bifidobacterial levels was seen with GOS supplementation it was not statistically significant in either healthy or IBD cats. No significant differences were observed in the faecal microbiota of IBD cats and healthy cats fed the same diet. Members of the family Coriobacteriaceae (Atopobium cluster) were found to be the most abundant bacteria in the feline microbiota.

A double-blind, placebo-controlled, randomized human study assessing the capacity of a novel galacto-oligosaccharide mixture in reducing travellers' diarrhoea.

Background/Objectives: Prebiotics have attracted interest for their ability to positively affect the colonic microbiota composition, thus increasing resistance to infection and diarrhoeal disease. This study assessed the effectiveness of a prebiotic galacto-oligosaccharide mixture (B-GOS) on the severity and/or incidence of travellers' diarrhoea (TD) in healthy subjects. Subjects/Methods: The study was a placebo-controlled, randomized, double blind of parallel design in 159 healthy volunteers, who travelled for minimum of 2 weeks to a country of low or high risk for TD. The investigational product was the B-GOS and the placebo was maltodextrin. Volunteers were randomized into groups with an equal probability of receiving either the prebiotic or placebo. The protocol comprised of a 1 week pre-holiday period recording bowel habit, while receiving intervention and the holiday period. Bowel habit included the number of bowel movements and average consistency of the stools as well as occurrence of abdominal discomfort, flatulence, bloating or vomiting. A clinical report was completed in the case of diarrhoeal incidence. A post-study questionnaire was also completed by all subjects on their return. Results: Results showed significant differences between the B-GOS and the placebo group in the incidence (P<0.05) and duration (P<0.05) of TD. Similar findings occurred on abdominal pain (P<0.05) and the overall quality of life assessment (P<0.05). Conclusions: Consumption of the tested galacto-oligosaccharide mixture showed significant potential in preventing the incidence and symptoms of TD.

New algorithms for synthesized design of optical filters

Chebyshev optical-filter algorithms for low-cost microcomputers have been improved. An offset ripple is now used for better transmission/matching in low-pass stacks. A prototype for narrowband filters is now more general and nearer practicability.

Application of the entropy technique and genetic algorithms to construction site layout planning of medium-size projects

Genetic algorithms (GAs) have been introduced into site layout planning as reported in a number of studies. In these studies, the objective functions were defined so as to employ the GAs in searching for the optimal site layout. However, few studies have been carried out to investigate the actual closeness of relationships between site facilities; it is these relationships that ultimately govern the site layout. This study has determined that the underlying factors of site layout planning for medium-size projects include work flow, personnel flow, safety and environment, and personal preferences. By finding the weightings on these factors and the corresponding closeness indices between each facility, a closeness relationship has been deduced. Two contemporary mathematical approaches - fuzzy logic theory and an entropy measure - were adopted in finding these results in order to minimize the uncertainty and vagueness of the collected data and improve the quality of the information. GAs were then applied to searching for the optimal site layout in a medium-size government project using the GeneHunter software. The objective function involved minimizing the total travel distance. An optimal layout was obtained within a short time. This reveals that the application of GA to site layout planning is highly promising and efficient.

Evaluation of peak-picking algorithms for protein mass spectrometry

Peak picking is an early key step in MS data analysis. We compare three commonly used approaches to peak picking and discuss their merits by means of statistical analysis. Methods investigated encompass signal-to-noise ratio, continuous wavelet transform, and a correlation-based approach using a Gaussian template. Functionality of the three methods is illustrated and discussed in a practical context using a mass spectral data set created with MALDI-TOF technology. Sensitivity and specificity are investigated using a manually defined reference set of peaks. As an additional criterion, the robustness of the three methods is assessed by a perturbation analysis and illustrated using ROC curves.

Distributed acceleration of mobile radio network optimisation algorithms

The past decade has witnessed explosive growth of mobile subscribers and services. With the purpose of providing better-swifter-cheaper services, radio network optimisation plays a crucial role but faces enormous challenges. The concept of Dynamic Network Optimisation (DNO), therefore, has been introduced to optimally and continuously adjust network configurations, in response to changes in network conditions and traffic. However, the realization of DNO has been seriously hindered by the bottleneck of optimisation speed performance. An advanced distributed parallel solution is presented in this paper, as to bridge the gap by accelerating the sophisticated proprietary network optimisation algorithm, while maintaining the optimisation quality and numerical consistency. The ariesoACP product from Arieso Ltd serves as the main platform for acceleration. This solution has been prototyped, implemented and tested. Real-project based results exhibit a high scalability and substantial acceleration at an average speed-up of 2.5, 4.9 and 6.1 on a distributed 5-core, 9-core and 16-core system, respectively. This significantly outperforms other parallel solutions such as multi-threading. Furthermore, augmented optimisation outcome, alongside high correctness and self-consistency, have also been fulfilled. Overall, this is a breakthrough towards the realization of DNO.

Acceleration of radio network optimisation algorithms

The increasing demand for cheaper-faster-better services anytime and anywhere has made radio network optimisation much more complex than ever before. In order to dynamically optimise the serving network, Dynamic Network Optimisation (DNO), is proposed as the ultimate solution and future trend. The realization of DNO, however, has been hindered by a significant bottleneck of the optimisation speed as the network complexity grows. This paper presents a multi-threaded parallel solution to accelerate complicated proprietary network optimisation algorithms, under a rigid condition of numerical consistency. ariesoACP product from Arieso Ltd serves as the platform for parallelisation. This parallel solution has been benchmarked and results exhibit a high scalability and a run-time reduction by 11% to 42% based on the technology, subscriber density and blocking rate of a given network in comparison with the original version. Further, it is highly essential that the parallel version produces equivalent optimisation quality in terms of identical optimisation outputs.