We did lots of work in this space for certain kinds of business problems, following some new developments. This kind of problem could in the future be addressed by Quantum Computing. Technical:
Prof Patrick H. Madden SUNY Binghamton CSD pmadden@acm.org, explanatory slides from talk last year:
https://drive.google.com/open?id=1hKxS3R4t4B7DXlhhJwSWJutbmutWZ78-
and an introductory article that is unconnected with the above:
Dynamic Programming vs Divide-and-Conquer Or Divide-and-Conquer on Steroids
In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples: binary search and minimum edit distance (Levenshtein distance).
The Problem
When I started to learn algorithms it was hard for me to understand the main idea of dynamic programming (DP) and how it is different from divide-and-conquer (DC) approach. When it gets to comparing those two paradigms usually Fibonacci function comes to the rescue as great example. But when we’re trying to solve the same problem using both DP and DC approaches to explain each of them, it feels for me like we may lose valuable detail that might help to catch the difference faster. And these detail tells us that each technique serves best for different types of problems.
I’m still in the process of understanding DP and DC difference and I can’t say that I’ve fully grasped the concepts so far. But I hope this article will shed some extra light and help you to do another step of learning such valuable algorithm paradigms as dynamic programming and divide-and-conquer. ...
Showing posts with label Dynamic Programming. Show all posts
Showing posts with label Dynamic Programming. Show all posts
Monday, November 12, 2018
Monday, October 08, 2018
Dynamic Programming Methods
Below was given earlier this week, Patrick Madden is developing an APP to analyze problems so you can determine what methods will work well. Below the fold are some technical details about the App and its projected availability. Combinatoric and dynamic programming a longtime interest of mine. I plan to test this as it becomes available. Technical.
Dynamic Programming for the Masses
Original Presentation at UC: Slides.
Prof Patrick Madden, SUNY Bighamton. Patrick.Madden@gmail.com
Dynamic Programming for the Masses
Original Presentation at UC: Slides.
Prof Patrick Madden, SUNY Bighamton. Patrick.Madden@gmail.com
Saturday, March 17, 2018
(Updated) Optimization using Genetic Methods
In our earliest days, addressing supply chain and blending type manufacturing problems, we were an optimization shop. Using the math structure of difficult combinatorial problems to find best solutions based on known goals and constraints. But if you couldn't glean enough low level structure, we tested genetic methods, described here. In this era of faster machines and more contextual information even more useful to try today. Also for certain kinds of structure, also consider Dynamic Programming. Happen to be examining that again today.
In KDNuggets By Ahmed Gad, KDnuggets Contributor
This article gives a brief introduction about evolutionary algorithms (EAs) and describes genetic algorithm (GA) which is one of the simplest random-based EAs.
Selection of the optimal parameters values for machine learning tasks is challenging. Some results may be bad not because the data is noisy or the used learning algorithm is weak, but due to the bad selection of the parameters values. This article gives a brief introduction about evolutionary algorithms (EAs) and describes genetic algorithm (GA) which is one of the simplest random-based EAs.
Introduction
Suppose that a data scientist has an image dataset divided into a number of classes and an image classifier is to be created. After the data scientist investigated the dataset, the K-nearest neighbor (KNN) seems to be a good option. To use the KNN algorithm, there is an important parameter to use which is K. Suppose that an initial value of 3 is selected. The scientist starts the learning process of the KNN algorithm with the selected K=3. The trained model generated reached a classification accuracy of 85%. Is that percent acceptable? In another way, can we get a better classification accuracy than what we currently reached? We cannot say that 85% is the best accuracy to reach until conducting different experiments. But to do another experiment, we definitely must change something in the experiment such as changing the K value used in the KNN algorithm. We cannot definitely say 3 is the best value to use in this experiment unless trying to apply different values for K and noticing how the classification accuracy varies. The question is “how to find the best value for K that maximizes the classification performance?” This is what is called optimization.
In optimization, we start with some kind of initial values for the variables used in the experiment. Because these values may not be the best ones to use, we should change them until getting the best ones. In some cases, these values are generated by complex functions that we cannot solve manually easily. But it is very important to do optimization because a classifier may produce a bad classification accuracy not because, for example, the data is noisy or the used learning algorithm is weak but due to the bad selection of the learning parameters initial values. As a result, there are different optimization techniques suggested by operation research (OR) researchers to do such work of optimization. According to [1], optimization techniques are categorized into four main categories: .... "
(Update) A comment I got made me add this. 'Optimization' in business practice implies you can get the provably, best possible solution to a problem. But in reality it almost always means you only can get the best solution within some specific context. A context can include structure, constraints and goals. It may also vary over time. It may be wrong because its too hard to completely understand the problem. But its still often useful to get a better solution, even if not provably optimal, if its better than todays practice. Further if you can calculate this 'theoretical' best solution, it can give you better understanding of a problem, and what to strive for. - FAD
In KDNuggets By Ahmed Gad, KDnuggets Contributor
This article gives a brief introduction about evolutionary algorithms (EAs) and describes genetic algorithm (GA) which is one of the simplest random-based EAs.
Selection of the optimal parameters values for machine learning tasks is challenging. Some results may be bad not because the data is noisy or the used learning algorithm is weak, but due to the bad selection of the parameters values. This article gives a brief introduction about evolutionary algorithms (EAs) and describes genetic algorithm (GA) which is one of the simplest random-based EAs.
Introduction
Suppose that a data scientist has an image dataset divided into a number of classes and an image classifier is to be created. After the data scientist investigated the dataset, the K-nearest neighbor (KNN) seems to be a good option. To use the KNN algorithm, there is an important parameter to use which is K. Suppose that an initial value of 3 is selected. The scientist starts the learning process of the KNN algorithm with the selected K=3. The trained model generated reached a classification accuracy of 85%. Is that percent acceptable? In another way, can we get a better classification accuracy than what we currently reached? We cannot say that 85% is the best accuracy to reach until conducting different experiments. But to do another experiment, we definitely must change something in the experiment such as changing the K value used in the KNN algorithm. We cannot definitely say 3 is the best value to use in this experiment unless trying to apply different values for K and noticing how the classification accuracy varies. The question is “how to find the best value for K that maximizes the classification performance?” This is what is called optimization.
In optimization, we start with some kind of initial values for the variables used in the experiment. Because these values may not be the best ones to use, we should change them until getting the best ones. In some cases, these values are generated by complex functions that we cannot solve manually easily. But it is very important to do optimization because a classifier may produce a bad classification accuracy not because, for example, the data is noisy or the used learning algorithm is weak but due to the bad selection of the learning parameters initial values. As a result, there are different optimization techniques suggested by operation research (OR) researchers to do such work of optimization. According to [1], optimization techniques are categorized into four main categories: .... "
(Update) A comment I got made me add this. 'Optimization' in business practice implies you can get the provably, best possible solution to a problem. But in reality it almost always means you only can get the best solution within some specific context. A context can include structure, constraints and goals. It may also vary over time. It may be wrong because its too hard to completely understand the problem. But its still often useful to get a better solution, even if not provably optimal, if its better than todays practice. Further if you can calculate this 'theoretical' best solution, it can give you better understanding of a problem, and what to strive for. - FAD
Saturday, November 18, 2017
Dynamic Programming for the Masses
From ACM Sigsoft a presentation about a favorite topic: Dynamic Programming: entitled 'Dynamic Programming for the Masses'. With links to presentation by Prof Patrick Madden of SUNY Binghamton. I will be testing some of the software mentioned, join in if you like, will report on possibilities here as I progress.
Subscribe to:
Posts (Atom)