scott1328 wrote:

SpeedOfSound wrote:heuristic

Code: Select all

package heur

object session {
   def abs(x:Double) = if(x>=0) x else -x    //> abs: (x: Double)Double
   def count = 0                             //> count: => Int
   
  def sqrtIter(guess: Double, x: Double): Double =
     if( isGoodEnough(guess, x) ) guess
     else sqrtIter( improve( guess, x), x)     //> sqrtIter: (guess: Double, x: Double)Double
     
   def isGoodEnough(guess:Double, x: Double) =
      abs(guess * guess - x)/x < 0.000001
                                                  //> isGoodEnough: (guess: Double, x: Double)Boolean
   
   def improve(guess: Double, x:Double): Double =
      (guess + x / guess) / 2           //> improve: (guess: Double, x: Double)Double
      
      
   def sqrt(x: Double) = sqrtIter(1.0, x)    //> sqrt: (x: Double)Double
   
   sqrt(2)                                   //> res0: Double = 1.4142135623746899
   sqrt(4)                                   //> res1: Double = 2.0000000929222947
   
   }

Could be adapted to order from a menu.

I would not call that a heuristic, it is an algorithm that applies Newton's method to calculate a square root. In this particular case it doesn't matter what the I initial estimate for the square root is, it will converge very rapidly and could be carried on to arbitrary precision.

I would say Newton's method is itself a heuristic.

As for picking items from a menu. it would serve very poorly for that purpose,

SpeedOfSound wrote:

scott1328 wrote:

SpeedOfSound wrote:heuristic

Code: Select all

package heur

object session {
   def abs(x:Double) = if(x>=0) x else -x    //> abs: (x: Double)Double
   def count = 0                             //> count: => Int
   
  def sqrtIter(guess: Double, x: Double): Double =
     if( isGoodEnough(guess, x) ) guess
     else sqrtIter( improve( guess, x), x)     //> sqrtIter: (guess: Double, x: Double)Double
     
   def isGoodEnough(guess:Double, x: Double) =
      abs(guess * guess - x)/x < 0.000001
                                                  //> isGoodEnough: (guess: Double, x: Double)Boolean
   
   def improve(guess: Double, x:Double): Double =
      (guess + x / guess) / 2           //> improve: (guess: Double, x: Double)Double
      
      
   def sqrt(x: Double) = sqrtIter(1.0, x)    //> sqrt: (x: Double)Double
   
   sqrt(2)                                   //> res0: Double = 1.4142135623746899
   sqrt(4)                                   //> res1: Double = 2.0000000929222947
   
   }

Could be adapted to order from a menu.

I would not call that a heuristic, it is an algorithm that applies Newton's method to calculate a square root. In this particular case it doesn't matter what the I initial estimate for the square root is, it will converge very rapidly and could be carried on to arbitrary precision.

I would say Newton's method is itself a heuristic.

As for picking items from a menu. it would serve very poorly for that purpose,

I think it qualifies. The algorithm takes it upon itself to 'go see'. It can be made to go see for any arbitrarily long period of time. It isn't calculating the answer it is applying a rule that gets arbitrarily closer to the answer. Much like I would walk further toward the object to figure it.

Now I did say could be adapted to pick from a menu. good_enough() would be some measure of my emotional reaction to the current selection. A random pick in the menu would start the process. I may back up to a former pick and reconsider by measuring against picks that followed it's original reading. I actually do this when I order at a restaurant. It's an algorithm I am familiar with. I usually end up with prime rib. And then I hate myself.

newolder wrote:The square root of X can be written as X1/2 (as long as X > 0) and has 'plus' and 'minus' solutions.
Let Z = X1/2
Then ln (Z) = 1/2 ln (X) and therefore Z = (plus or minus) exp(0.5 * ln(X)) is a suitable algorithm (its not a heuristic tho') and requires a math library with functions for exponentiation and taking logarithms.

A branch of artificial intelligence, which uses heuristics -- common-sense rules drawn from experience -- to solve problems. This is in contrast to algorithmic programming, which is based on mathematically provable procedures. Heuristic programming is characterized by programs that are self-learning; they get better with experience. Heuristic programs do not always reach the very best result but usually produce a good result. Many expert systems use heuristic programming.

SpeedOfSound wrote:So much for abstraction.

Give me a concrete design for a heuristic algorithm that finds square roots.

scott1328 wrote:

SpeedOfSound wrote:So much for abstraction.

Give me a concrete design for a heuristic algorithm that finds square roots.

for very large integers X

Arrange arrange X blocks into a square array. When finished count the number of blocks on edge, then on the other edge. Take the average of the two edge counts. That is an approximation of the square root of X

newolder wrote:A quick search on - heuristic program -, brought this:

A branch of artificial intelligence, which uses heuristics -- common-sense rules drawn from experience -- to solve problems. This is in contrast to algorithmic programming, which is based on mathematically provable procedures. Heuristic programming is characterized by programs that are self-learning; they get better with experience. Heuristic programs do not always reach the very best result but usually produce a good result. Many expert systems use heuristic programming.

SpeedOfSound wrote:

scott1328 wrote:

SpeedOfSound wrote:So much for abstraction.

Give me a concrete design for a heuristic algorithm that finds square roots.

for very large integers X

Arrange arrange X blocks into a square array. When finished count the number of blocks on edge, then on the other edge. Take the average of the two edge counts. That is an approximation of the square root of X

How do you get a computer to arrange the blocks?

SpeedOfSound wrote:

newolder wrote:A quick search on - heuristic program -, brought this:

A branch of artificial intelligence, which uses heuristics -- common-sense rules drawn from experience -- to solve problems. This is in contrast to algorithmic programming, which is based on mathematically provable procedures. Heuristic programming is characterized by programs that are self-learning; they get better with experience. Heuristic programs do not always reach the very best result but usually produce a good result. Many expert systems use heuristic programming.

So we have data drawn from our experience and fed into a computer algorithm to give some answer. In the scala code above the 'guess' can be construed as such data. The improve function is a convergent algorithm.

If we had pure heuristics we would have a table of the right answers. Input from somewhere else. I just don't see a foundational difference between heuristics and algorithm. Other than that we have removed the solution and error quantification from the computer and assigned them to some nebulous procedures outside the program. We can always imagine a nebulous outside. Much like we imagine that our minds do some magical and nebulous thing outside of our detailed understanding to pick an item from a menu.

So what I am getting at is that when these discussions of the human vs machine intelligence come up the group that insists it isn't possible are just deferring to god of the gap arguments. If I pick an item from a menu my limbic system is the goodenough function, the menus item placement and colors are the guess, and my reading skills are the improve function. I see no difference of substance here.

An algorithm is the description of an automated solution to a problem. What the algorithm does is precisely defined. The solution could or could not be the best possible one but you know from the start what kind of result you will get. You implement the algorithm using some programming language to get (a part of) a program.

Now, some problems are hard and you may not be able to get an acceptable solution in an acceptable time. In such cases you often can get a not too bad solution much faster, by applying some arbitrary choices (educated guesses): that's a heuristic.

A heuristic is still a kind of an algorithm, but one that will not explore all possible states of the problem, or will begin by exploring the most likely ones.

Typical examples are from games. When writing a chess game program you could imagine trying every possible move at some depth level and applying some evaluation function to the board. A heuristic would exclude full branches that begin with obviously bad moves.

In some cases you're not searching for the best solution, but for any solution fitting some constraint. A good heuristic would help to find a solution in a short time, but may also fail to find any if the only solutions are in the states it chose not to try.

SpeedOfSound wrote:But! As usual we can clear it all up by coming up with a CONCRETE example of heuristic code to contrast with the code I provided. Naming programs is not a concrete example. The square block method is a one-iter that would require relaxing good enough considerably.

GrahamH wrote:

SpeedOfSound wrote:But! As usual we can clear it all up by coming up with a CONCRETE example of heuristic code to contrast with the code I provided. Naming programs is not a concrete example. The square block method is a one-iter that would require relaxing good enough considerably.

You can't have a 'concrete example of a heuristic code'. That's why it's call heuristic, the code you can write does not define the solutions it might produce.

...