SEARCH · PubMed Health

Results for “Algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,153 records · Page 64Linked to original sources

PubMed2004

Linear response algorithms for approximate inference in graphical models.

Belief propagation (BP) on cyclic graphs is an efficient algorithm for computing approximate marginal probability distributions over single nodes and neighboring nodes in the graph. However, it does not prescribe a way to compute joint distributions over pairs of distant nodes in the graph. In this article, we propose two new algorithms for approximating these pairwise probabilities, based on the linear response theorem. The first is a propagation algorithm that is shown to converge if BP converges to a stable fixed point. The second algorithm is based on matrix inversion. Applying these ideas to gaussian random fields, we derive a propagation algorithm for computing the inverse of a matrix.

Algorithms↗

PubMed1999

A unified analysis of value-function-based reinforcement- learning algorithms.

Reinforcement learning is the problem of generating optimal behavior in a sequential decision-making environment given the opportunity of interacting with it. Many algorithms for solving reinforcement-learning problems work by computing improved estimates of the optimal value function. We extend prior analyses of reinforcement-learning algorithms and present a powerful new theorem that can provide a unified analysis of such value-function-based reinforcement-learning algorithms. The usefulness of the theorem lies in how it allows the convergence of a complex asynchronous reinforcement-learning algorithm to be proved by verifying that a simpler synchronous algorithm converges. We illustrate the application of the theorem by analyzing the convergence of Q-learning, model-based reinforcement learning, Q-learning with multistate updates, Q-learning for Markov games, and risk-sensitive reinforcement learning.

Algorithms↗

PubMed1999

Algorithmic stability and sanity-check bounds for leave-one-out cross-validation.

In this article we prove sanity-check bounds for the error of the leave-one-out cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate is not much worse than that of the training error estimate. The name sanity check refers to the fact that although we often expect the leave-one-out estimate to perform considerably better than the training error estimate, we are here only seeking assurance that its performance will not be considerably worse. Perhaps surprisingly, such assurance has been given only for limited cases in the prior literature on cross-validation. Any nontrivial bound on the error of leave-one-out must rely on some notion of algorithmic stability. Previous bounds relied on the rather strong notion of hypothesis stability, whose application was primarily limited to nearest-neighbor and other local algorithms. Here we introduce the new and weaker notion of error stability and apply it to obtain sanity-check bounds for leave-one-out for other classes of learning algorithms, including training error minimization procedures and Bayesian algorithms. We also provide lower bounds demonstrating the necessity of some form of error stability for proving bounds on the error of the leave-one-out estimate, and the fact that for training error minimization algorithms, in the worst case such bounds must still depend on the Vapnik-Chervonenkis dimension of the hypothesis class.

Algorithms↗

PubMed2000

Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning.

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.

Algorithms↗

PubMed2001

Where genetic algorithms excel.

We analyze the performance of a genetic algorithm (GA) we call Culling, and a variety of other algorithms, on a problem we refer to as the Additive Search Problem (ASP). We show that the problem of learning the Ising perceptron is reducible to a noisy version of ASP. Noisy ASP is the first problem we are aware of where a genetic-type algorithm bests all known competitors. We generalize ASP to k-ASP to study whether GAs will achieve "implicit parallelism" in a problem with many more schemata. GAs fail to achieve this implicit parallelism, but we describe an algorithm we call Explicitly Parallel Search that succeeds. We also compute the optimal culling point for selective breeding, which turns out to be independent of the fitness function or the population distribution. We also analyze a mean field theoretic algorithm performing similarly to Culling on many problems. These results provide insight into when and how GAs can beat competing methods.

Algorithms↗

PubMed2001

Design of graph-based evolutionary algorithms: a case study for chemical process networks.

This paper describes the adaptation of evolutionary algorithms (EAs) to the structural optimization of chemical engineering plants, using rigorous process simulation combined with realistic costing procedures to calculate target function values. To represent chemical engineering plants, a network representation with typed vertices and variable structure will be introduced. For this representation, we introduce a technique on how to create problem specific search operators and apply them in stochastic optimization procedures. The applicability of the approach is demonstrated by a reference example. The design of the algorithms will be oriented at the systematic framework of metric-based evolutionary algorithms (MBEAs). MBEAs are a special class of evolutionary algorithms, fulfilling certain guidelines for the design of search operators, whose benefits have been proven in theory and practice. MBEAs rely upon a suitable definition of a metric on the search space. The definition of a metric for the graph representation will be one of the main issues discussed in this paper. Although this article deals with the problem domain of chemical plant optimization, the algorithmic design can be easily transferred to similar network optimization problems. A useful distance measure for variable dimensionality search spaces is suggested.

Algorithms↗

PubMed2002

Evolutionary algorithms for the satisfiability problem.

Several evolutionary algorithms have been proposed for the satisfiability problem. We review the solution representations suggested in literature and choose the most promising one - the bit string representation - for further evaluation. An empirical comparison on commonly used benchmarks is presented for the most successful evolutionary algorithms and for WSAT, a prominent local search algorithm for the satisfiability problem. The key features of successful evolutionary algorithms are identified, thereby providing useful methodological guidelines for designing new heuristics. Our results indicate that evolutionary algorithms are competitive to WSAT.

Algorithms↗

PubMed2004

Real-coded memetic algorithms with crossover hill-climbing.

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.

Algorithms↗

PubMed1998

On the futility of blind search: an algorithmic view of "no free lunch".

The paper is in three parts. First, we use simple adversary arguments to redevelop and explore some of the no-free-lunch (NFL) theorems and perhaps extend them a little. Second, we clarify the relationship of NFL theorems to algorithm theory and complexity classes such as NP. We claim that NFL is weaker in the sense that the constraints implied by the conjectures of traditional algorithm theory on what an evolutionary algorithm may be expected to accomplish are far more severe than those implied by NFL. Third, we take a brief look at how natural evolution relates to computation and optimization. We suggest that the evolution of complex systems exhibiting high degrees of orderliness is not equivalent in difficulty to optimizing hard (in the complexity sense) problems, and that the optimism in genetic algorithms (GAs) as universal optimizers is not justified by natural evolution. This is an informal tutorial paper--most of the information presented is not formally proven, and is either "common knowledge" or formally proven elsewhere. Some of the claims are intuitions based on experience with algorithms, and in a more formal setting should be classified as conjectures.

Algorithms↗

PubMed1999

Scalability problems of simple genetic algorithms.

Scalable evolutionary computation has become an intensively studied research topic in recent years. The issue of scalability is predominant in any field of algorithmic design, but it became particularly relevant for the design of competent genetic algorithms once the scalability problems of simple genetic algorithms were understood. Here we present some of the work that has aided in getting a clear insight in the scalability problems of simple genetic algorithms. Particularly, we discuss the important issue of building block mixing. We show how the need for mixing places a boundary in the GA parameter space that, together with the boundary from the schema theorem, delimits the region where the GA converges reliably to the optimum in problems of bounded difficulty. This region shrinks rapidly with increasing problem size unless the building blocks are tightly linked in the problem coding structure. In addition, we look at how straightforward extensions of the simple genetic algorithm-namely elitism, niching, and restricted mating are not significantly improving the scalability problems.

Algorithms↗

PubMed2006

An extended EM algorithm for joint feature extraction and classification in brain-computer interfaces.

For many electroencephalogram (EEG)-based brain-computer interfaces (BCIs), a tedious and time-consuming training process is needed to set parameters. In BCI Competition 2005, reducing the training process was explicitly proposed as a task. Furthermore, an effective BCI system needs to be adaptive to dynamic variations of brain signals; that is, its parameters need to be adjusted online. In this article, we introduce an extended expectation maximization (EM) algorithm, where the extraction and classification of common spatial pattern (CSP) features are performed jointly and iteratively. In each iteration, the training data set is updated using all or part of the test data and the labels predicted in the previous iteration. Based on the updated training data set, the CSP features are reextracted and classified using a standard EM algorithm. Since the training data set is updated frequently, the initial training data set can be small (semi-supervised case) or null (unsupervised case). During the above iterations, the parameters of the Bayes classifier and the CSP transformation matrix are also updated concurrently. In online situations, we can still run the training process to adjust the system parameters using unlabeled data while a subject is using the BCI system. The effectiveness of the algorithm depends on the robustness of CSP feature to noise and iteration convergence, which are discussed in this article. Our proposed approach has been applied to data set IVa of BCI Competition 2005. The data analysis results show that we can obtain satisfying prediction accuracy using our algorithm in the semisupervised and unsupervised cases. The convergence of the algorithm and robustness of CSP feature are also demonstrated in our data analysis.

Algorithms↗

PubMed1999

Prospective evaluation of an algorithm for the functional assessment of lung resection candidates.

Patients with impaired pulmonary function are at increased risk for the development of postoperative complications. Recently exercise testing and predicted postoperative (ppo) function have gained increasing importance in the evaluation of lung resection candidates. We prospectively evaluated an algorithm for the preoperative functional evaluation that was developed at our institution. This algorithm incorporated the cardiac history including an electrocardiogram (ECG), and the three parameters FEV1, diffusing capacity of the lungs for carbon monoxide (DLCO), and maximal oxygen uptake (VO2max), as well as their respective ppo values (FEV1-ppo, DLCO-ppo, and VO2max-ppo) calculated based on radionuclide perfusion scans. A consecutive group of 137 patients (mean age 62 yr; range 23 to 81; 102 males, 35 females) with clinically resectable lesions underwent assessment according to our algorithm. Five patients were deemed functionally inoperable, 132 passed the algorithm and underwent pulmonary resections with standard thoracotomy: 9 segmental or wedge resections, 85 lobectomies (inclusive 3 bilobectomies), and 38 pneumonectomies. All patients were extubated within 24 h. The mean stay in the ICU was 1.4 (+/- 1.8) d, and the mean hospital stay was 14.6 (+/- 5) d. Postoperative complications (within 30 d) occurred in 15 patients (11%), of whom two died (overall mortality rate 1.5%). In comparison to our previous series this meant a 50% reduction in complications whereas the percentage of inoperable patients remained unchanged (4% now, 5% before). We conclude that adherence to our algorithm resulted in a very low complication rate (morbidity and mortality), and excluded more rigorous patient selection as a bias for the improved results.

Aged↗

PubMed1989

A medical algorithm for detecting physical disease in psychiatric patients.

An algorithm for screening psychiatric patients for physical disease was empirically derived from a comprehensive assessment of 509 patients in California's mental health system. The first 343 patients were used to develop the algorithm, and the remaining 166 were used as a test group. Calculations were made for several versions of the algorithm, and the data were compared with the diagnoses listed in the patients' admission mental health record. The algorithmic procedure was more accurate and more cost-effective than the medical evaluation procedures used by the state mental health system. When applied to the test group, the algorithm detected up to 90 percent of patients who had an active, important physical disease at a cost of $156 per patient. The mental health system had detected 58 percent of test-group patients with a disease at a cost of $230 per patient.

Algorithms↗

PubMed1994

Fast scan conversion algorithms for displaying ultrasound sector images.

Two fast algorithms for interpolation of ultrasonic sector-scans were developed. Both algorithms are based on line-drawing algorithms and are free from multiplications in the innermost loops. The algorithms were compared to the following conventional interpolators: 2-D windowed sinc, bicubic spline, 4 x 4 point bicubic spline, bilinear, and nearest neighbor. The most accurate of the two new algorithms is about eight times faster than nearest neighbor interpolation. The quantitative errors are of the same order as the errors of the nearest neighbor interpolator. The subjective image quality is between nearest neighbor and bilinear interpolation.

Algorithms↗

PubMed2002

Guidelines and algorithms for the use of methylphenidate in children with Attention-Deficit/ Hyperactivity Disorder.

OBJECTIVE: To review published algorithms for guiding the use of methylphenidate (MPH) in the treatment of Attention-Deficit/Hyperactivity Disorder (ADHD) in children and adolescents. METHODS: A consensus roundtable of 12 experts was convened to review the evidence for the safety and efficacy of MPH in the treatment of ADHD, as well as the published algorithms and practice guidelines for using MPH. The experts reviewed the algorithms for practicality and acceptability by clinicians. RESULTS: Algorithms that included MPH commonly selected it as the initial medication to be employed in the treatment of children with ADHD. Factors involved included its high efficacy, good safety record, and the ubiquitous nature of its appearance in the ADHD treatment literature. CONCLUSIONS: MPH should be considered as the first medication to be used in a treatment algorithm for children and adolescents with ADHD.

Adolescent↗

PubMed1997

Uses of the EM algorithm in the analysis of data on HIV/AIDS and other infectious diseases.

The analysis of data on infectious diseases is a natural setting for applications of the EM algorithm, because the infection process is only partially observable. Difficulties in determining the expectation at the E step have been side-stepped by adopting pragmatic models which reflect only part of the mechanism that generates the data. In the HIV/AIDS context the EM algorithm has helped in the reconstruction of the unobserved HIV infection curve, the so-called backprojection problem, as well as in the estimation of the distribution for the incubation period until AIDS, in estimating the infectivity of HIV in partnerships and in estimating parameters describing the decline in the immune system. There is a need for smooth estimates of functions in these applications, suggesting the use of the EMS algorithm or use of the EM algorithm to maximize a penalized likelihood. For data on other infectious diseases the application of the EM algorithm has so far been restricted to analyses of data on the size of outbreaks in a sample of households.

Acquired Immunodeficiency Syndrome↗

PubMed2004

Challenges and recent developments in hearing aids. Part I. Speech understanding in noise, microphone technologies and noise reduction algorithms.

This review discusses the challenges in hearing aid design and fitting and the recent developments in advanced signal processing technologies to meet these challenges. The first part of the review discusses the basic concepts and the building blocks of digital signal processing algorithms, namely, the signal detection and analysis unit, the decision rules, and the time constants involved in the execution of the decision. In addition, mechanisms and the differences in the implementation of various strategies used to reduce the negative effects of noise are discussed. These technologies include the microphone technologies that take advantage of the spatial differences between speech and noise and the noise reduction algorithms that take advantage of the spectral difference and temporal separation between speech and noise. The specific technologies discussed in this paper include first-order directional microphones, adaptive directional microphones, second-order directional microphones, microphone matching algorithms, array microphones, multichannel adaptive noise reduction algorithms, and synchrony detection noise reduction algorithms. Verification data for these technologies, if available, are also summarized.

Algorithms↗

PubMed2006

Development of an algorithm for using PINP to monitor treatment of patients with teriparatide.

INTRODUCTION: Teriparatide effects are mediated via the preferential stimulation of osteoblastic activity over osteoclastic activity. Amino-terminal propeptide of type I procollagen (PINP) is an indicator of osteoblastic activity. OBJECTIVE: Develop an algorithm using PINP as an aid in the management of patients with postmenopausal osteoporosis treated with teriparatide. RESEARCH DESIGN AND METHODS: For inclusion in this post-hoc analysis, trials had to be investigations of teriparatide 20 microg/day in postmenopausal women with osteoporosis having measurements of PINP at 3 months and bone mineral density (BMD) at 12 months. Signal-to-noise ratio was calculated for a series of markers of bone turnover in the Fracture Prevention Trial. An algorithm was developed to monitor patients treated with teriparatide using PINP. RESULTS: Three trials met inclusion criteria and included the Fracture Prevention, Forteo-Alendronate Comparator and Anabolic After Antiresorptive trials. PINP had the highest signal-to-noise ratio of all bone-turnover markers. Positive PINP responses defined as increases > 10 microg/L were observed in 77-79% of teriparatide- and in 6% of placebo-treated patients after 3 months of study drug. Mean lumbar spine BMD increases after 12 months of teriparatide in patients having PINP changes > 10 microg/L ranged from 8.3% to 9.5% and in patients with PINP changes < or = 10 microg/L ranged from 5.9% to 7.6%. In the algorithm, PINP is measured at baseline and after 1-3 months of therapy. Patients with PINP increases > 10 microg/L are given a positive message. Patients with PINP increases < or = 10 microg/L are assessed for adherence, teriparatide administration and storage techniques, and for the presence of medical conditions that might limit their therapeutic response, and these issues are addressed as appropriate. Patients without these issues and with PINP increases < or = 10 microg/L should be given a neutral message because BMD may significantly increase with continued therapy. CONCLUSIONS: The PINP algorithm provides information regarding the anabolic response to teriparatide therapy and has the potential to identify patients requiring help with issues of adherence, injection technique, teriparatide storage, and medical problems limiting therapeutic responsiveness to teriparatide treatment. Data assessing the relationship of changes in PINP to fracture risk reduction are not available. We recommend physicians audit the use of the algorithm in practice so that improvements can be made.

Adult↗