Cross-entropy method (original) (raw)
The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective. The method approximates the optimal importance sampling estimator by repeating two phases: 1. * Draw a sample from a probability distribution. 2. * Minimize the cross-entropy between this distribution and a target distribution to produce a better sample in the next iteration.
| Property | Value |
|---|---|
| dbo:abstract | The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective. The method approximates the optimal importance sampling estimator by repeating two phases: 1. * Draw a sample from a probability distribution. 2. * Minimize the cross-entropy between this distribution and a target distribution to produce a better sample in the next iteration. Reuven Rubinstein developed the method in the context of rare event simulation, where tiny probabilities must be estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems. The method has also been applied to the traveling salesman, quadratic assignment, DNA sequence alignment, max-cut and buffer allocation problems. (en) La méthode de l'entropie-croisée (CE) attribuée à Reuven Rubinstein est une méthode générale d'optimisation de type , combinatoire ou , et d'échantillonnage préférentiel. La méthode a été conçue à l'origine pour la simulation d'événements rares, où des densités de probabilité très faibles doivent être estimées correctement, par exemple dans l'analyse de la sécurité des réseaux, les modèles de file d'attente, ou l'analyse des performances des systèmes de télécommunication.La méthode CE peut être appliquée à tout problème d'optimisation combinatoire où les observations sont bruitées comme le problème du voyageur de commerce, l'optimisation quadratique, le problème d'alignement de séquences d'ADN, le et les problèmes d'allocation de mémoire, tout comme des problèmes d'optimisation continue avec de nombreux extrema locaux. La méthode CE se décompose en deux phases : 1. * Créer aléatoirement un échantillon de données (trajectoires, vecteurs, etc.) selon un mécanisme spécifique. 2. * Mettre à jour les paramètres du mécanisme de création aléatoire à partir de l'échantillon de données pour produire un meilleur échantillon à l'itération suivante. Cette étape implique de minimiser l'entropie croisée ou la divergence de Kullback-Leibler. (fr) Метод перехресної ентропії — розроблений у 1997 році Р. Рубінштейном загальний підхід до комбінаторної та неперервної мульти-екстремальної оптимізації та вибірки за значущістю. Метод з'явився з моделювання рідких подій, де потрібно точно оцінити дуже малі ймовірності, наприклад аналіз ефективності телекомунікаційних систем. Метод перехресної ентропії може бути застосований до статистичних задач комбінаторної оптимізації, таких як задача комівояжера, квадратична задача про призначення, задача максимального перерізу, а також неперервна глобальна оптимізація з множинними екстремумами тощо. Метод перехресної ентропії визначний тим, що він визначає точну математичну основу для отримання швидких, і в деякому сенсі «оптимальних» правил оновлення / навчання. Метод перехресної ентропії складається з двох етапів: 1. * Генерація випадкової вибірки даних (траєкторії, вектора тощо) відповідно до визначеного механізму. 2. * Оновлення параметрів випадкового механізму базуючись на даних щоб отримати «кращу» вибірку на наступній ітерації. Цей крок включає мінімізацію перехресної ентропії або дивергенції Кульбака — Лейблера. (uk) |
| dbo:wikiPageExternalLink | http://www.maths.uq.edu.au/~kroese/ps/aortut.pdf https://cran.r-project.org/web/packages/CEoptim/index.html https://www.nuget.org/packages/Novacta.Analytics |
| dbo:wikiPageID | 5767980 (xsd:integer) |
| dbo:wikiPageLength | 7200 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1079343769 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Monte_Carlo_methods dbr:Sequence_alignment dbr:Cross_entropy dbr:Estimation_of_distribution_algorithm dbr:Optimization_(mathematics) dbr:Monte_Carlo_method dbr:Continuous_optimization dbr:Simulated_annealing dbr:Combinatorial_optimization dbr:Tabu_search dbc:Machine_learning dbc:Heuristics dbc:Optimization_algorithms_and_methods dbr:Exponential_family dbr:Probability_density_function dbr:Parametric_family dbr:Gaussian_distribution dbr:Harmony_search dbr:Quadratic_assignment_problem dbr:Support_(mathematics) dbr:Discrete_space dbr:Maxcut dbr:Kullback–Leibler_divergence dbr:Randomized_algorithm dbr:Genetic_algorithms dbr:Maximum_likelihood dbr:Importance_sampling dbr:Natural_Evolution_Strategy dbr:Reuven_Rubinstein dbr:Traveling_salesman_problem |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dct:subject | dbc:Monte_Carlo_methods dbc:Machine_learning dbc:Heuristics dbc:Optimization_algorithms_and_methods |
| rdf:type | yago:WikicatMonteCarloMethods yago:WikicatOptimizationAlgorithmsAndMethods yago:Ability105616246 yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Cognition100023271 yago:Event100029378 yago:Heuristic105847956 yago:Know-how105616786 yago:Method105660268 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatHeuristics yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective. The method approximates the optimal importance sampling estimator by repeating two phases: 1. * Draw a sample from a probability distribution. 2. * Minimize the cross-entropy between this distribution and a target distribution to produce a better sample in the next iteration. (en) La méthode de l'entropie-croisée (CE) attribuée à Reuven Rubinstein est une méthode générale d'optimisation de type , combinatoire ou , et d'échantillonnage préférentiel. La méthode a été conçue à l'origine pour la simulation d'événements rares, où des densités de probabilité très faibles doivent être estimées correctement, par exemple dans l'analyse de la sécurité des réseaux, les modèles de file d'attente, ou l'analyse des performances des systèmes de télécommunication.La méthode CE peut être appliquée à tout problème d'optimisation combinatoire où les observations sont bruitées comme le problème du voyageur de commerce, l'optimisation quadratique, le problème d'alignement de séquences d'ADN, le et les problèmes d'allocation de mémoire, tout comme des problèmes d'optimisation continue a (fr) Метод перехресної ентропії — розроблений у 1997 році Р. Рубінштейном загальний підхід до комбінаторної та неперервної мульти-екстремальної оптимізації та вибірки за значущістю. Метод з'явився з моделювання рідких подій, де потрібно точно оцінити дуже малі ймовірності, наприклад аналіз ефективності телекомунікаційних систем. Метод перехресної ентропії може бути застосований до статистичних задач комбінаторної оптимізації, таких як задача комівояжера, квадратична задача про призначення, задача максимального перерізу, а також неперервна глобальна оптимізація з множинними екстремумами тощо. Метод перехресної ентропії визначний тим, що він визначає точну математичну основу для отримання швидких, і в деякому сенсі «оптимальних» правил оновлення / навчання. (uk) |
| rdfs:label | Cross-entropy method (en) Méthode de l'entropie croisée (fr) Метод перехресної ентропії (uk) |
| owl:sameAs | freebase:Cross-entropy method yago-res:Cross-entropy method wikidata:Cross-entropy method dbpedia-fr:Cross-entropy method dbpedia-th:Cross-entropy method dbpedia-uk:Cross-entropy method https://global.dbpedia.org/id/34SPH |
| prov:wasDerivedFrom | wikipedia-en:Cross-entropy_method?oldid=1079343769&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Cross-entropy_method |
| is dbo:wikiPageRedirects of | dbr:Cross-Entropy_Method dbr:Cross_entropy_method dbr:Xe_method |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Deep_reinforcement_learning dbr:List_of_numerical_analysis_topics dbr:Cross_entropy dbr:Estimation_of_distribution_algorithm dbr:Genetic_algorithm dbr:Ant_colony_optimization_algorithms dbr:Simulated_annealing dbr:Cross-Entropy_Method dbr:Kabsch_algorithm dbr:Reinforcement_learning dbr:Dirk_Kroese dbr:List_of_statistics_articles dbr:Reuven_Rubinstein dbr:Stochastic_optimization dbr:Outline_of_machine_learning dbr:Cross_entropy_method dbr:Xe_method |
| is foaf:primaryTopic of | wikipedia-en:Cross-entropy_method |