mike + algorithms   26

The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm – Math ∩ Programming
What mystical algorithm has such broad applications? Now that computer scientists have studied it in generality, it’s known as the Multiplicative Weights Update Algorithm (MWUA). Procedurally, the algorithm is simple. I can even describe the core idea in six lines of pseudocode. You start with a collection of objects, and each object has a weight.

Set all the object weights to be 1.
For some large number of rounds:
Pick an object at random proportionally to the weights
Some event happens
Increase the weight of the chosen object if it does well in the event
Otherwise decrease the weight
algorithms  math  linearprogramming  gradientdescent  gametheory 
march 2018 by mike
Inside Wade | Kabir Shah
Wade is a 1kb Javascript search library. It allows you to search for a query through a set of documents. This query is processed, split into keywords, and then searched within an index structure.
algorithms  js 
november 2017 by mike
Are Index Funds Communist? - Bloomberg
Again: I know this is silly. But as a wild extrapolation of the far future of financial capitalism, I submit to you that it is less silly than the  "Silent Road to Serfdom" thesis. That thesis is that, in the long run, financial markets will tend toward mindlessness, a sort of central planning -- by an index fund -- that is worse than 1950s communism because it's not even trying to make the right decisions.

The alternative view is that, in the long run, financial markets will tend toward perfect knowledge, a sort of central planning -- by the Best Capital Allocating Robot -- that is better than Marxism because it is perfectly informed and ideally rational. And once you have that, you can shut down the market: The game is over, and the Best Capital Allocating Robot won. The Fraser-Jenkins thesis is that algorithmic investing runs the risk of destroying capitalism by abandoning the pursuit of knowledge. But the really fun alternative is that it runs the risk of destroying capitalism by perfecting that pursuit: Once you have solved the socialist calculation problem, what do you need markets for?
economics  algorithms  finance 
november 2017 by mike
Dasgupta's algorithms homeworks
algorithms  cs 
december 2016 by mike
CS 383: Algorithms (Spring 2011)
Selected solutions to Dasgupta exercises
algorithms  cs 
december 2016 by mike
algorithms - Prove Upper Bound (Big O) for Fibonacci's Sequence? - Mathematics Stack Exchange
In general, given any linear recurrence relation, the same trick works: guess that the general nnth term is of the form cxncxn, write down an equation for xx (which will be a polynomial), and if αα is the largest root of that polynomial equation, then you'll have T(n)=O(αn)T(n)=O(αn).
math  cs  algorithms 
december 2016 by mike
Researchers Sue the Government Over Computer Hacking Law | WIRED
Web sites often use algorithms to analyze user profile information, web surfing habits—determined through tracking cookies that sites place on the computers of visitors—and other information collected by data brokers from public records, social media sites, and store loyalty programs. The algorithms, which are proprietary and therefore not transparent in how they work, can determine not only the ads a site serves to visitors but can also determine things like the job and housing listings a visitor sees on them. This can lead to discrimination that is illegal under the Fair Housing Act and Title VII of the Civil Rights Act.

The concern is that by threatening researchers who violate service terms with criminal prosecution, web sites could effectively chill research that helps determine if the web sites themselves are breaking laws. And because it’s the web sites that draft the terms of service, “the recipe for avoiding Fair Housing Act and Title VII liability for algorithmic discrimination is straightforward,” the plaintiffs write. “[M]erely employ terms of service that preclude subsequent speech about such discrimination, and it can continue unchecked.”
bias  algorithms  law 
july 2016 by mike
The one great thing about unfair algorithms | mathbabe
So, algorithms are not by their nature fair. But sometimes their specific brand of unfairness might still be an improvement, because it’s at least measurable.

Algorithms represent decision processes that are vulnerable to inspection more than most human-led processes are. And although we are not taking advantage of this yet, we could and should do so soon. We need to start auditing our algorithms, at least the ones that are widespread and high impact.
algorithms  fairness  ethics  datascience 
february 2016 by mike

Copy this bookmark: