Search results for "Algorithm"

showing 10 items of 4887 documents

ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS

2011

The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.

FOS: Computer and information sciencesJ.3average case analysis.Binary numberaverage case analysispermuted stringpermuted stringsComputer Science - Data Structures and AlgorithmsComputer Science (miscellaneous)Parikh vectorData Structures and Algorithms (cs.DS)Pattern matchingTime complexityMathematicsString (computer science)Parikh vectorsstring algorithmDecision problemstring algorithmsSubstringParikh vectors; permuted strings; pattern matching; string algorithms; average case analysisF.2.2; J.3Index (publishing)pattern matchingF.2.2Constant (mathematics)AlgorithmComputer Science::Formal Languages and Automata Theory
researchProduct

Randomized Block Frank–Wolfe for Convergent Large-Scale Learning

2017

Owing to their low-complexity iterations, Frank-Wolfe (FW) solvers are well suited for various large-scale learning tasks. When block-separable constraints are present, randomized block FW (RB-FW) has been shown to further reduce complexity by updating only a fraction of coordinate blocks per iteration. To circumvent the limitations of existing methods, the present work develops step sizes for RB-FW that enable a flexible selection of the number of blocks to update per iteration while ensuring convergence and feasibility of the iterates. To this end, convergence rates of RB-FW are established through computational bounds on a primal sub-optimality measure and on the duality gap. The novel b…

FOS: Computer and information sciencesMathematical optimization0102 computer and information sciences02 engineering and technology01 natural sciencesMeasure (mathematics)Machine Learning (cs.LG)Convergence (routing)FOS: Mathematics0202 electrical engineering electronic engineering information engineeringFraction (mathematics)Electrical and Electronic EngineeringMathematics - Optimization and ControlMathematicsSequenceDuality gapComputer Science - Numerical Analysis020206 networking & telecommunicationsNumerical Analysis (math.NA)Stationary pointSupport vector machineComputer Science - LearningOptimization and Control (math.OC)010201 computation theory & mathematicsIterated functionSignal ProcessingAlgorithmIEEE Transactions on Signal Processing
researchProduct

Adaptive independent sticky MCMC algorithms

2018

In this work, we introduce a novel class of adaptive Monte Carlo methods, called adaptive independent sticky MCMC algorithms, for efficient sampling from a generic target probability density function (pdf). The new class of algorithms employs adaptive non-parametric proposal densities which become closer and closer to the target as the number of iterations increases. The proposal pdf is built using interpolation procedures based on a set of support points which is constructed iteratively based on previously drawn samples. The algorithm's efficiency is ensured by a test that controls the evolution of the set of support points. This extra stage controls the computational cost and the converge…

FOS: Computer and information sciencesMathematical optimizationAdaptive Markov chain Monte Carlo (MCMC)Monte Carlo methodBayesian inferenceHASettore SECS-P/05 - Econometrialcsh:TK7800-8360Machine Learning (stat.ML)02 engineering and technologyBayesian inference01 natural sciencesStatistics - Computationlcsh:Telecommunication010104 statistics & probabilitysymbols.namesakeAdaptive Markov chain Monte Carlo (MCMC); Adaptive rejection Metropolis sampling (ARMS); Bayesian inference; Gibbs sampling; Hit and run algorithm; Metropolis-within-Gibbs; Monte Carlo methods; Signal Processing; Hardware and Architecture; Electrical and Electronic EngineeringGibbs samplingStatistics - Machine Learninglcsh:TK5101-67200202 electrical engineering electronic engineering information engineeringComputational statisticsMetropolis-within-GibbsHit and run algorithm0101 mathematicsElectrical and Electronic EngineeringGaussian processComputation (stat.CO)MathematicsSignal processinglcsh:Electronics020206 networking & telecommunicationsMarkov chain Monte CarloMonte Carlo methodsHardware and ArchitectureSignal ProcessingSettore SECS-S/03 - Statistica EconomicasymbolsSettore SECS-S/01 - StatisticaStatistical signal processingGibbs samplingAdaptive rejection Metropolis sampling (ARMS)EURASIP Journal on Advances in Signal Processing
researchProduct

Bayesian Unification of Gradient and Bandit-based Learning for Accelerated Global Optimisation

2017

Bandit based optimisation has a remarkable advantage over gradient based approaches due to their global perspective, which eliminates the danger of getting stuck at local optima. However, for continuous optimisation problems or problems with a large number of actions, bandit based approaches can be hindered by slow learning. Gradient based approaches, on the other hand, navigate quickly in high-dimensional continuous spaces through local optimisation, following the gradient in fine grained steps. Yet, apart from being susceptible to local optima, these schemes are less suited for online learning due to their reliance on extensive trial-and-error before the optimum can be identified. In this…

FOS: Computer and information sciencesMathematical optimizationComputer scienceComputer Science - Artificial IntelligenceBayesian probability02 engineering and technologyMachine learningcomputer.software_genreMachine Learning (cs.LG)symbols.namesakeLocal optimumMargin (machine learning)0202 electrical engineering electronic engineering information engineeringGaussian processFlexibility (engineering)business.industry020206 networking & telecommunicationsFunction (mathematics)Computer Science - LearningArtificial Intelligence (cs.AI)symbols020201 artificial intelligence & image processingAlgorithm designLinear approximationArtificial intelligencebusinesscomputer
researchProduct

Online shortest paths with confidence intervals for routing in a time varying random network

2018

International audience; The increase in the world's population and rising standards of living is leading to an ever-increasing number of vehicles on the roads, and with it ever-increasing difficulties in traffic management. This traffic management in transport networks can be clearly optimized by using information and communication technologies referred as Intelligent Transport Systems (ITS). This management problem is usually reformulated as finding the shortest path in a time varying random graph. In this article, an online shortest path computation using stochastic gradient descent is proposed. This routing algorithm for ITS traffic management is based on the online Frank-Wolfe approach.…

FOS: Computer and information sciencesMathematical optimizationComputer sciencePopulation02 engineering and technology[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE][INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing[SPI]Engineering Sciences [physics][INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]0502 economics and business11. SustainabilityComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringFOS: MathematicsData Structures and Algorithms (cs.DS)educationIntelligent transportation systemMathematics - Optimization and ControlRandom graph050210 logistics & transportationeducation.field_of_studyStochastic process[SPI.PLASMA]Engineering Sciences [physics]/Plasmas05 social sciencesApproximation algorithm[INFO.INFO-MO]Computer Science [cs]/Modeling and SimulationStochastic gradient descentOptimization and Control (math.OC)[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA]Shortest path problem020201 artificial intelligence & image processing[INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET]Routing (electronic design automation)[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]
researchProduct

Scalability of using Restricted Boltzmann Machines for Combinatorial Optimization

2014

Abstract Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Restricted Boltzmann Machines (RBMs) are generative neural networks with these desired properties. We integrate an RBM into an EDA and evaluate the performance of this system in solving combinatorial optimization problems with a single objective. We assess how the number of fitness evaluations and the CPU time scale with problem size and complexity. The results are compared to the Bayesian Optimization Algorithm (BOA), a state-of-the-art multivariate EDA, and the Dependency Tree Algorithm (DTA), which uses a simpler probability model requiring less computati…

FOS: Computer and information sciencesMathematical optimizationInformation Systems and ManagementOptimization problemGeneral Computer SciencePopulationComputer Science::Neural and Evolutionary Computation0211 other engineering and technologiesBoltzmann machine02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringEvolutionary computation0202 electrical engineering electronic engineering information engineeringNeural and Evolutionary Computing (cs.NE)educationMathematicseducation.field_of_study021103 operations researchArtificial neural networkI.2.6I.2.8Computer Science - Neural and Evolutionary ComputingEstimation of distribution algorithmModeling and SimulationScalabilityCombinatorial optimization020201 artificial intelligence & image processingI.2.6; I.2.8Algorithm
researchProduct

An LP-based hyperparameter optimization model for language modeling

2018

In order to find hyperparameters for a machine learning model, algorithms such as grid search or random search are used over the space of possible values of the models hyperparameters. These search algorithms opt the solution that minimizes a specific cost function. In language models, perplexity is one of the most popular cost functions. In this study, we propose a fractional nonlinear programming model that finds the optimal perplexity value. The special structure of the model allows us to approximate it by a linear programming model that can be solved using the well-known simplex algorithm. To the best of our knowledge, this is the first attempt to use optimization techniques to find per…

FOS: Computer and information sciencesMathematical optimizationPerplexityLinear programmingComputer scienceMachine Learning (stat.ML)02 engineering and technology010501 environmental sciences01 natural sciencesTheoretical Computer ScienceNonlinear programmingMachine Learning (cs.LG)Random searchSimplex algorithmSearch algorithmStatistics - Machine Learning0202 electrical engineering electronic engineering information engineeringFOS: MathematicsMathematics - Optimization and Control0105 earth and related environmental sciencesHyperparameterComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science - LearningHardware and ArchitectureOptimization and Control (math.OC)Hyperparameter optimization020201 artificial intelligence & image processingLanguage modelSoftwareInformation Systems
researchProduct

Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

2010

We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified stop at different times. Our second algorithm uses the first algorithm to improve the running time of Harrow et al. algorithm for solving systems of linear equations from O(kappa^2 log N) to O(kappa log^3 kappa log N) where \kappa is the condition number of the system of equations.

FOS: Computer and information sciencesMathematics::LogicQuantum PhysicsComputer Science - Computational ComplexityComputer Science - Data Structures and AlgorithmsFOS: Physical sciencesData Structures and Algorithms (cs.DS)Computational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct

Heretical Mutiple Importance Sampling

2016

Multiple Importance Sampling (MIS) methods approximate moments of complicated distributions by drawing samples from a set of proposal distributions. Several ways to compute the importance weights assigned to each sample have been recently proposed, with the so-called deterministic mixture (DM) weights providing the best performance in terms of variance, at the expense of an increase in the computational cost. A recent work has shown that it is possible to achieve a trade-off between variance reduction and computational effort by performing an a priori random clustering of the proposals (partial DM algorithm). In this paper, we propose a novel "heretical" MIS framework, where the clustering …

FOS: Computer and information sciencesMean squared errorComputer scienceApplied MathematicsEstimator020206 networking & telecommunications02 engineering and technologyVariance (accounting)Statistics - Computation01 natural sciencesReduction (complexity)010104 statistics & probability[INFO.INFO-TS]Computer Science [cs]/Signal and Image ProcessingSignal Processing0202 electrical engineering electronic engineering information engineeringA priori and a posterioriVariance reduction0101 mathematicsElectrical and Electronic EngineeringCluster analysisAlgorithm[SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processingImportance samplingComputation (stat.CO)ComputingMilieux_MISCELLANEOUS
researchProduct

The Recycling Gibbs sampler for efficient learning

2018

Monte Carlo methods are essential tools for Bayesian inference. Gibbs sampling is a well-known Markov chain Monte Carlo (MCMC) algorithm, extensively used in signal processing, machine learning, and statistics, employed to draw samples from complicated high-dimensional posterior distributions. The key point for the successful application of the Gibbs sampler is the ability to draw efficiently samples from the full-conditional probability density functions. Since in the general case this is not possible, in order to speed up the convergence of the chain, it is required to generate auxiliary samples whose information is eventually disregarded. In this work, we show that these auxiliary sample…

FOS: Computer and information sciencesMonte Carlo methodSlice samplingInferenceMachine Learning (stat.ML)02 engineering and technologyBayesian inferenceStatistics - Computation01 natural sciencesMachine Learning (cs.LG)010104 statistics & probabilitysymbols.namesake[INFO.INFO-TS]Computer Science [cs]/Signal and Image ProcessingStatistics - Machine LearningArtificial IntelligenceStatistics0202 electrical engineering electronic engineering information engineering0101 mathematicsElectrical and Electronic EngineeringGaussian processComputation (stat.CO)ComputingMilieux_MISCELLANEOUSMathematicsChain rule (probability)Applied Mathematics020206 networking & telecommunicationsMarkov chain Monte CarloStatistics::ComputationComputer Science - LearningComputational Theory and MathematicsSignal ProcessingsymbolsComputer Vision and Pattern RecognitionStatistics Probability and UncertaintyAlgorithm[SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processingGibbs samplingDigital Signal Processing
researchProduct