Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

[Politics] The world's most-surveilled cities; [Bike] Hope Freehub; [Restaurant] Mama Chau's (Chinese, Providencia); [Politics] Brexit Podcast; [Diary] Pneumonia; [Politics] Britain's Reichstag Fire moment; GPS Vehicle Tracking for Cat Soft LLC; install cairo; Credit Card Processing for Cat Soft LLC; [Programming] GCC Sanitizer Flags; VOIP quote for Cat Soft LLC; Copier Quotes for Cat Soft LLC; Costs; [GPU, Programming] Per-Thread Program Counters; Now Is Cat Soft LLC's Chance To Save Up To 32% On Mail; My Bike Accident - Looking Back One Year; [Python] Geographic heights are incredibly easy!; [Cooking] Cookie Recipe; Efficient, Simple, Directed Maximisation of Noisy Function; And for argparse; Bash Completion in Python; [Computing] Configuring Github Jekyll Locally; [Maths, Link] The Napkin Project; You can Masquerade in Firewalld; [Bike] Servicing Budget (Spring) Forks; [Crypto] CIA Internet Comms Failure; [Python] Cute Rate Limiting API; [Causality] Judea Pearl Lecture; [Security, Computing] Chinese Hardware Hack Of Supermicro Boards; SQLAlchemy Joined Table Inheritance and Delete Cascade; [Translation] The Club; [Computing] Super Potato Bruh; [Computing] Extending Jupyter; Further HRM Details; [Computing, Bike] Activities in ch2; [Books, Link] Modern Japanese Lit; What ended up there; [Link, Book] Logic Book; Update - Garmin Express / Connect; Garmin Forerunner 35 v 230; [Link, Politics, Internet] Government Trolls; [Link, Politics] Why identity politics benefits the right more than the left; SSH Forwarding; A Specification For Repeating Events; A Fight for the Soul of Science; [Science, Book, Link] Lost In Math; OpenSuse Leap 15 Network Fixes; Update; [Book] Galileo's Middle Finger; [Bike] Chinese Carbon Rims; [Bike] Servicing Shimano XT Front Hub HB-M8010; [Bike] Aliexpress Cycling Tops; [Computing] Change to ssh handling of multiple identities?; [Bike] Endura Hummvee Lite II; [Computing] Marble Based Logic; [Link, Politics] Sanity Check For Nuclear Launch; [Link, Science] Entropy and Life; [Link, Bike] Cheap Cycling Jerseys; [Link, Music] Music To Steal 2017; [Link, Future] Simulated Brain Drives Robot; [Link, Computing] Learned Index Structures; Solo Air Equalization; Update: Higher Pressures; Psychology; [Bike] Exercise And Fuel; Continental Race King 2.2; Removing Lowers; Mnesiacs; [Maths, Link] Dividing By Zero; [Book, Review] Ray Monk - Ludwig Wittgenstein: The Duty Of Genius; [Link, Bike, Computing] Evolving Lacing Patterns; [Jam] Strawberry and Orange Jam; [Chile, Privacy] Biometric Check During Mail Delivery; [Link, Chile, Spanish] Article on the Chilean Drought; [Bike] Extended Gear Ratios, Shimano XT M8000 (24/36 Chainring); [Link, Politics, USA] The Future Of American Democracy; Mass Hysteria; [Review, Books, Links] Kazuo Ishiguro - Never Let Me Go; [Link, Books] David Mitchell's Favourite Japanese Fiction; [Link, Bike] Rear Suspension Geometry; [Link, Cycling, Art] Strava Artwork; [Link, Computing] Useful gcc flags; [Link] Voynich Manuscript Decoded; [Bike] Notes on Servicing Suspension Forks; [Links, Computing] Snap, Flatpack, Appimage; [Link, Computing] Oracle is leaving Java (to die); [Link, Politics] Cubans + Ultrasonics; [Book, Link] Laurent Binet; VirtualBox; [Book, Link] No One's Ways; [Link] The Biggest Problem For Cyclists Is Bad Driving; [Computing] Doxygen, Sphinx, Breathe; [Admin] Brokw Recent Permalinks; [Bike, Chile] Buying Bearings in Santiago; [Computing, Opensuse] Upgrading to 42.3; [Link, Physics] First Support for a Physics Theory of Life; [Link, Bike] Peruvian Frame Maker; [Link] Awesome Game Theory Tit-For-Tat Thing; [Food, Review] La Fabbrica - Good Italian Food In Santiago; [Link, Programming] MySQL UTF8 Broken; [Link, Books] Latin American Authors

© 2006-2017 Andrew Cooke (site) / post authors (content).

Efficient, Simple, Directed Maximisation of Noisy Function

From: andrew cooke <andrew@...>

Date: Fri, 14 Dec 2018 18:04:10 -0300

Maybe this is already known - I guess it must be - but I just dreamt
it up myself.  I need to find the max (could be min, obvs) of a noise
function in 1D.

Since it's noisy I can't assume it's smooth, hope it has a global
minimum, and bisect.  I need something more robust.

At the same time, I don't want to be doing repeated evaluations of the
function where they're not needed, so any iterative deepening of a
search should re-use old values when possible.

So here's the solution:

  * Evaluate the function at 5 equally spaced points across the range
    (including the two extremes).

  * Throw away two end points.

  * Expand the remaining 3 points back to 5 by inserting new points at
    the mid-points of the existing points.

  * Repeat until you're happy.

The trick is to know which end points to discard.  It could be one
either end, or two from one end.

What I do is calculate the average of the x values at the points,
weighted by the function values there.  Then I compare this to the
unweighted average.  If it's higher, then the max is towards the high
end, so discard a low point.  Or vice-versa.  And repeat for a second
point.

Here's an example.  The lines are (x, f(x)) pairs:

[(0.0, 0), (0.25, 5), (0.5, 10), (0.75, 1), (1.0, 1)]
[(0.25, 5), (0.375, 12), (0.5, 10), (0.625, 2), (0.75, 1)]
[(0.25, 5), (0.3125, 11), (0.375, 12), (0.4375, 10), (0.5, 10)]
[(0.3125, 11), (0.34375, 12), (0.375, 12), (0.40625, 10), (0.4375, 10)]
[(0.3125, 11), (0.328125, 11), (0.34375, 12), (0.359375, 13), (0.375, 12)]

On the first step, both ends were discarded.  On the second, two from
the "high" side, etc.  The maximum is 13 at 0.359375, roughly.

And here's the code:

def expand_max(lo, hi, n, f):
    data = [(x, f(x)) for x in (lo + i * (hi - lo) / 4 for i in range(5))]
    for _ in range(n):
        print(data)
        while len(data) > 3:
            w = sum(x*fx for (i, (x, fx)) in enumerate(data)) / sum(fx for (x, fx) in data)
            m = sum(x for (x, fx) in data) / len(data)
            if w > m:
                del data[0]
            else:
                del data[-1]
        x = (data[0][0] + data[1][0]) / 2
        data.insert(1, (x, f(x)))
        x = (data[-2][0] + data[-1][0]) / 2
        data.insert(-1, (x, f(x)))
    x_max, fx_max = None, None
    for (x, fx) in data:
        if x_max is None or fx > fx_max:
            x_max, fx_max = x, fx
    return x_max, fx_max

Andrew

Comment on this post