algorithmkdb+accumulateaccumulatorhill-climbing

KDB/q How to accumulate based on output accuracy


I'm trying to create a simple hill climbing function, where I have a list of numbers of length n and a target number x. I'm trying to adjust this list and calculate the accuracy of the sum of the numbers in the list to the target x.

My plan is to do 1,000 iterations, and to avoid any local maximum/minimum, I have a 5% threshold (via random number generation). I already have the function to calculate the Accuracy metric, and the function to change one value of the list, my only question is how I can create the accumulation function that can 1) compare the current and new lists, 2) make the adjustment to the list based on accuracy and if 5% threshold is crossed, and 3) accumulate to see the progress.

For example, if I have the initial table below:

Iteration List Accuracy
1 listx 10

If the 2nd iteration is not better than the current list (iteration #1), then the output will be:

Iteration List Accuracy
1 listx 10
2 listx 10

If the 3rd iteration is better than the current list (iteration #2) and crossed the 5% threshold, the output will be:

Iteration List Accuracy
1 listx 10
2 listx 10
3 listy 15

My pseudocode is:

    moveOneStep:{[List]
        adjustedList: changeOneNumber[List]
        if calculateAccuracy[adjustedList] > calculateAccuracy[List]:
            if randomNumberGeneration > 0.05:
                adjustedList
            else if randomNumberGeneration <= 0.05:
                List
        else if calculateAccuracy[adjustedList] < calculateAccuracy[List]:
            List

I've used python extensively in the past but I'm new to q, and I'm not sure how I can translate what I'm thinking of above. Any and all help is greatly appreciative!


Solution

  • Taking in to account your comment, this should work. It will give you a keyed table response with the iteration value, list used and accuracy.

    / Input will be list and the iteration value 
    moveOneStep:{[list;n]
        adjustedList:changeOneNumber[list];
    
        / Calculate accuracy and save variable for each
        $[(adjListAcc:calculateAccuracy[adjustedList]) > origListAcc:calculateAccuracy[list];
    
        $[randomNumberGeneration[] > 0.05;
    
            / If randNumber is greater than 0.05 return iteration, adjusted list and adjusted list accuracy            
            :(n;adjustedList;adjListAcc);
    
            / If not greater than 0..5 return iteration, original list and original list accuracy 
            :(n;list;origListAcc)];
    
        / If calculateAccuracy < return iteration, original list and original list accuracy
        :(n;list;origListAcc)]
    }
    
    / Input list and number of iterations needed
    completeCalc:{[l;i]
    
        / Initiate table for results
        tab:([Iteration:()]List:();Accuracy:());
    
        / Initiate count for iterations
        x:1; 
    
        / Do loop to complete designated iterations
        do[i;
    
            / Complete calculation and save table
            tab:tab upsert res:moveOneStep[l;x];
    
            / Get most recent list to use for next iteration
            l:res[1];
    
            / Add one to count
            x+:1];
    
    / Return completed table 
    :tab}
    

    For initial list of (1 2 3 4) and to iterate 100 times, it should be

    completeCalc[1 2 3 4; 100]