Tag Archives: multiobjective-optimization

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • [1006.5366] “Not only defended but also applied”: The per­ceived absur­dity of Bayesian inference

    “The mis­sion­ary zeal of many Bayesians of old has been matched, in the other direc­tion, by a view among some the­o­reti­cians that Bayesian meth­ods are absurd-​​not merely mis­guided but obvi­ously wrong in prin­ci­ple. We con­sider sev­eral exam­ples, begin­ning with Feller’s clas­sic text on prob­a­bil­ity the­ory and con­tin­u­ing with more recent cases such as the per­ceived Bayesian nature of the so-​​called dooms­day argu­ment. We ana­lyze in this note the intel­lec­tual back­ground behind var­i­ous mis­con­cep­tions about Bayesian sta­tis­tics, with­out aim­ing at a com­plete his­tor­i­cal cov­er­age of the rea­sons for this dismissal.”

    social-​​dynamics sta­tis­tics martial-​​arts-​​schools

  • [1206.3268] Fea­ture Selec­tion via Block-​​Regularized Regression

    “In this paper, we con­sid­ered the prob­lem of find­ing a sub­set of covari­ates in a high-​​dimensional space that affect the out­put vari­able when there is a block struc– ture in the covari­ates. In the con­text of asso­ci­a­tion map­ping, we pro­posed a regression-​​based model with a Markov chain prior that encodes the infor­ma­tion in the cor­re­la­tion struc­ture such as dis­tance and re– com­bi­na­tion rate between adja­cent SNP mark­ers. We demon­strated on the sim­u­lated and mouse data that our pro­posed algo­rithm can be used to iden­tify groups of SNP mark­ers as a rel­e­vant block of causal SNPs. The idea of rep­re­sent­ing the cor­re­la­tion struc­ture as a Markov chain in a vari­able selec­tion method to learn grouped rel­e­vant vari­ables can be gen­er­al­ized to use a graph­i­cal model as a prior in a vari­able selec­tion prob– lem to rep­re­sent an arbi­trary cor­re­la­tion struc­ture in vari­ables in a high-​​dimensional space. Another inter– est­ing exten­sion of the model is to model a struc­ture in out­put vari­ables as well when mea­sure­ments of mul– tiple out­put vari­ables are available.”

    sta­tis­tics bioin­for­mat­ics algo­rithms data-​​mining feature-​​extraction

  • Fil­ipe Kiss : A bet­ter git log

    “So, are you tired of this old and bored git log screen?”

    yes software-​​development git tricks-​​n-​​tips bash

  • Neu­roskep­tic: Brains are Dif­fer­ent on Macs

    “The paper goes into lots more detail, but the les­son for researchers is extremely sim­ple: don’t cross the streams of data-​​analysis. Set up your analy­sis stream and then use it on all of your data. Same hard­ware, same soft­ware, same set­tings. Imag­ine you’re doing a study com­par­ing brain struc­ture in two groups. Halfway through ana­lyz­ing your data, you upgrade your MacOS. All of the brains you ana­lyze after that will be, say, 5% “big­ger”. That’ll cer­tainly make your data much nois­ier, and if you hap­pen to ana­lyze most of Group A before Group B, it’ll give you a false pos­i­tive find­ing. Some­times you just can’t avoid changes in hard­ware or soft­ware — IT techs have a habit of upgrad­ing things with­out ask­ing — but in these cases, you should run the same data under the old and the new regime to see if it’s mak­ing a dif­fer­ence. Finally, it would be wrong to blame FreeSurfer for this. I’d be sur­prised if they were any worse than the other soft­ware pack­ages. Mix­ing and match­ing ver­sions is some­thing that the FreeSurfer devel­op­ers specif­i­cally warn against. This paper shows why.”

    data-​​analysis repro­ducibil­ity technical-​​assumptions anomalies-​​are-​​where-​​you-​​find-​​them

  • Plug: What is infer­en­tial­ism? « Odontomachus’s Blog

    “I’ve been crit­i­cal of objects and the idea of ref­er­ence for a while now. To me sen­tences and propo­si­tions, by virtue of their role as “moves” in social inter­ac­tions, are likely to have pri­or­ity in a prop­erly objec­tive account of mean­ing. Many puta­tive objects (e.g. cor­po­ra­tions or muta­ble dig­i­tal doc­u­ments) bor­der on being fic­tional, gain­ing their object­hood only through what we say about them; and many refer­ring phrases seem to refer to dif­fer­ent things, depend­ing on what is being pred­i­cated. I think this opin­ion would make me what Pere­grin calls a “strong infer­en­tial­ist”. Even­tu­ally I hope that think­ing clearly about seman­tics ought to (among other things) help bring calm to the cur­rent mass hys­te­ria which is the Seman­tic Web and Linked Data, and help steer all of that energy expen­di­ture to improve its consequence.”

    prag­ma­tism indirect-​​links phi­los­o­phy talking-​​about-​​thinking-​​and-​​the-​​reverse

  • [1206.3552] A Clas­si­fi­ca­tion for Com­mu­nity Dis­cov­ery Meth­ods in Com­plex Networks

    “In the last few years many real-​​world net­works have been found to show a so-​​called com­mu­nity struc­ture orga­ni­za­tion. Much effort has been devoted in the lit­er­a­ture to develop meth­ods and algo­rithms that can effi­ciently high­light this hid­den struc­ture of the net­work, tra­di­tion­ally by par­ti­tion­ing the graph. Since net­work rep­re­sen­ta­tion can be very com­plex and can con­tain dif­fer­ent vari­ants in the tra­di­tional graph model, each algo­rithm in the lit­er­a­ture focuses on some of these prop­er­ties and estab­lishes, explic­itly or implic­itly, its own def­i­n­i­tion of com­mu­nity. Accord­ing to this def­i­n­i­tion it then extracts the com­mu­ni­ties that are able to reflect only some of the fea­tures of real com­mu­ni­ties. The aim of this sur­vey is to pro­vide a man­ual for the com­mu­nity dis­cov­ery prob­lem. Given a meta def­i­n­i­tion of what a com­mu­nity in a social net­work is, our aim is to orga­nize the main cat­e­gories of com­mu­nity dis­cov­ery based on their own def­i­n­i­tion of com­mu­nity. Given a desired def­i­n­i­tion of com­mu­nity and the fea­tures of a prob­lem (size of net­work, direc­tion of edges, mul­ti­di­men­sion­al­ity, and so on) this review paper is designed to pro­vide a set of approaches that researchers could focus on.”

    via:cshalizi graph-​​theory com­mu­nity clas­si­fi­ca­tion algo­rithms nudge

  • [1205.0792] Exact Wavelets on the Ball

    “We develop an exact wavelet trans­form on the three-​​dimensional ball (i.e. on the solid sphere), which we name the fla­glet trans­form. For this pur­pose we first con­struct an exact har­monic trans­form on the radial line using damped Laguerre poly­no­mi­als and develop a cor­re­spond­ing quad­ra­ture rule. Com­bined with the spher­i­cal har­monic trans­form, this approach leads to a sam­pling the­o­rem on the ball and a novel three-​​dimensional decom­po­si­tion which we call the Fourier-​​Laguerre trans­form. We relate this new trans­form to the well-​​known Fourier-​​Bessel decom­po­si­tion and show that band-​​limitness in the Fourier-​​Laguerre basis is a suf­fi­cient con­di­tion to com­pute the Fourier-​​Bessel decom­po­si­tion exactly. We then con­struct the fla­glet trans­form on the ball through a har­monic tiling, which is exact thanks to the exact­ness of the Fourier-​​Laguerre trans­form (from which the name fla­glets is coined). The cor­re­spond­ing wavelet ker­nels have com­pact local­i­sa­tion prop­er­ties in real and har­monic space and their angu­lar aper­ture is invari­ant under radial trans­la­tion. We intro­duce a mul­tires­o­lu­tion algo­rithm to per­form the fla­glet trans­form rapidly, while cap­tur­ing all infor­ma­tion at each wavelet scale in the min­i­mal num­ber of sam­ples on the ball. Our imple­men­ta­tion of these new tools achieves float­ing point pre­ci­sion and is made pub­licly avail­able. We per­form numer­i­cal exper­i­ments demon­strat­ing the speed and accu­racy of these libraries and illus­trate their capa­bil­i­ties on a sim­ple denois­ing example.”

    wavelets geom­e­try representation-​​theory signal-​​processing answer-​​languages

  • [1205.3077] Efficiency-​​Revenue Trade-​​offs in Auctions

    “When agents with inde­pen­dent pri­ors bid for a sin­gle item, Myerson’s opti­mal auc­tion max­i­mizes expected rev­enue, whereas Vickrey’s second-​​price auc­tion opti­mizes social wel­fare. We address the nat­ural ques­tion of trade-​​offs between the two cri­te­ria, that is, auc­tions that opti­mize, say, rev­enue under the con­straint that the wel­fare is above a given level. If one allows for ran­dom­ized mech­a­nisms, it is easy to see that there are polynomial-​​time mech­a­nisms that achieve any point in the trade-​​off (the Pareto curve) between rev­enue and wel­fare. We inves­ti­gate whether one can achieve the same guar­an­tees using deter­min­is­tic mech­a­nisms. We pro­vide a neg­a­tive answer to this ques­tion by show­ing that this is a (weakly) NP-​​hard prob­lem. On the pos­i­tive side, we pro­vide polynomial-​​time deter­min­is­tic mech­a­nisms that approx­i­mate with arbi­trary pre­ci­sion any point of the trade-​​off between these two fun­da­men­tal objec­tives for the case of two bid­ders, even when the val­u­a­tions are cor­re­lated arbi­trar­ily. The major prob­lem left open by our work is whether there is such an algo­rithm for three or more bid­ders with inde­pen­dent val­u­a­tion distributions.”

    algo­rithms Pareto-​​front performance-​​measure multiobjective-​​optimization

  • Sym­bol­set

    “Sym­bol­sets are seman­tic sym­bol fonts. They work in mod­ern browsers and any­where Open­Type fea­tures are supported.”

    typog­ra­phy uni­code

  • [1204.6653] Elim­i­na­tion of Glass Arti­facts and Object Segmentation

    “Many images nowa­days are cap­tured from behind the glasses and may have cer­tain stains dis­crep­ancy because of glass and must be processed to make dif­fer­en­ti­a­tion between the glass and objects behind it. This research paper pro­poses an algo­rithm to remove the dam­aged or cor­rupted part of the image and make it con­sis­tent with other part of the image and to seg­ment objects behind the glass. The dam­aged part is removed using total vari­a­tion inpaint­ing method and seg­men­ta­tion is done using kmeans clus­ter­ing, anisotropic dif­fu­sion and water­shed trans­for­ma­tion. The final out­put is obtained by inter­po­la­tion. This algo­rithm can be use­ful to appli­ca­tions in which some part of the images are cor­rupted due to data trans­mis­sion or needs to seg­ment objects from an image for fur­ther processing.”

    image-​​segmentation image-​​processing nudge-​​targets algo­rithms

  • The whole of the law — Things from your life

    “But it’ll be your deci­sion, not iner­tia or fate. The ongo­ing cadence of ask­ing these ques­tions (and, maybe, the con­tent of any answers you come up with) will con­vene an open space for you to live in. A world where what­ever you do is right.”

    this

  • The Pirate Uni­ver­sity | Pirate university

    “The Pirate Uni­ver­sity is an on-​​line bul­letin board on which stu­dents post requests for aca­d­e­mic pub­li­ca­tions. You can com­pare it to an aca­d­e­mic wish list. Oth­ers, who know where to find these pub­li­ca­tions, reply and if pos­si­ble, pro­vide links to the resources searched. The Pirate Uni­ver­sity is not pro­vid­ing, stor­ing or shar­ing copy­righted mate­r­ial. An impor­tant ques­tion is if the upload­ing of arti­cles, pub­li­ca­tions is legal. If you are the copy­right holder of the arti­cle requested, there should be no prob­lem. Also in cer­tain cases, if you or your insti­tute have acquired the rights of the pub­li­ca­tion, or if it is free of rights, there shouldn’t be a prob­lem. It is prob­a­bly best to con­sult with your librar­ian to see which kind of pub­li­ca­tion is okay to share on the Internet.”

    academic-​​culture pub­lish­ing col­lab­o­ra­tion crowd­sourc­ing librar­i­ans open-​​access schol­ar­ship

  • [1206.3793] A dis­trib­uted classification/​estimation algo­rithm for sen­sor networks

    “…We pro­pose a novel coop­er­a­tive iter­a­tive algo­rithm which copes with the com­mu­ni­ca­tion con­straints imposed by the net­work and shows remark­able per­for­mance. Our main result is a rig­or­ous proof of the con­ver­gence of the algo­rithm and a char­ac­ter­i­za­tion of the limit behav­ior. We also show that, in the limit when the num­ber of sen­sors goes to infin­ity, the com­mon unknown para­me­ter is esti­mated with arbi­trary small error, while the clas­si­fi­ca­tion error con­verges to that of the opti­mal cen­tral­ized max­i­mum like­li­hood esti­ma­tor. We also show numer­i­cal results that val­i­date the the­o­ret­i­cal analy­sis and sup­port their pos­si­ble gen­er­al­iza­tion. We com­pare our strat­egy with the Expectation-​​Maximization algo­rithm and we dis­cuss trade-​​offs in terms of robust­ness, speed of con­ver­gence and imple­men­ta­tion simplicity.”

    distributed-​​processing collective-​​behavior sensor-​​networks algo­rithms nudge-​​targets

  • [1204.6391] Extend­ing par­tial rep­re­sen­ta­tions of func­tion graphs and per­mu­ta­tion graphs

    “Func­tion graphs are graphs rep­re­sentable by inter­sec­tions of con­tin­u­ous real-​​valued func­tions on the inter­val [0,1] and are known to be exactly the com­ple­ments of com­pa­ra­bil­ity graphs. As such they are rec­og­niz­able in poly­no­mial time. Func­tion graphs gen­er­al­ize per­mu­ta­tion graphs, which arise when all func­tions con­sid­ered are lin­ear. We focus on the prob­lem of extend­ing par­tial rep­re­sen­ta­tions, which gen­er­al­izes the recog­ni­tion prob­lem. We observe that for per­mu­ta­tion graphs an easy exten­sion of Golumbic’s com­pa­ra­bil­ity graph recog­ni­tion algo­rithm can be exploited. This approach fails for func­tion graphs. Nev­er­the­less, we present a polynomial-​​time algo­rithm for extend­ing a par­tial rep­re­sen­ta­tion of a graph by func­tions defined on the entire inter­val [0,1] pro­vided for some of the ver­tices. On the other hand, we show that if a par­tial rep­re­sen­ta­tion con­sists of func­tions defined on subin­ter­vals of [0,1], then the prob­lem of extend­ing this rep­re­sen­ta­tion to func­tions on the entire inter­val [0,1] becomes NP-​​complete.”

    graph-​​theory math-i-didn’t-know representation-​​theory ontol­ogy inter­est­ing

  • [1206.3294] Flex­i­ble Pri­ors for Exemplar-​​based Clustering

    “Exemplar-​​based clus­ter­ing meth­ods have been shown to pro­duce state-​​of-​​the-​​art results on a num­ber of syn­thetic and real-​​world clus­ter­ing prob­lems. They are appeal­ing because they offer com­pu­ta­tional ben­e­fits over latent-​​mean mod­els and can han­dle arbi­trary pair­wise sim­i­lar­ity mea­sures between data points. How­ever, when try­ing to recover under­ly­ing struc­ture in clus­ter­ing prob­lems, tai­lored sim­i­lar­ity mea­sures are often not enough; we also desire con­trol over the dis­tri­b­u­tion of clus­ter sizes. Pri­ors such as Dirich­let process pri­ors allow the num­ber of clus­ters to be unspec­i­fied while express­ing pri­ors over data par­ti­tions. To our knowl­edge, they have not been applied to exemplar-​​based mod­els. We show how to incor­po­rate pri­ors, includ­ing Dirich­let process pri­ors, into the recently intro­duced affin­ity prop­a­ga­tion algo­rithm. We develop an effi­cient max­prod­uct belief prop­a­ga­tion algo­rithm for our new model and demon­strate exper­i­men­tally how the expanded range of clus­ter­ing pri­ors allows us to bet­ter recover true clus­ter­ings in sit­u­a­tions where we have some infor­ma­tion about the gen­er­at­ing process.”

    clus­ter­ing algo­rithms

  • Mag­a­zine — The Case Against Cre­den­tial­ism — The Atlantic

    ’”ALL OF OUR WORK HAS GIVEN ME A VERY STRONG view,” Richard Boy­atzis told me one after­noon. The con­sult­ing firm Boy­atzis heads, McBer and Com­pany, was founded by David McClel­land in 1963. Its spe­cialty has been ana­lyz­ing what peo­ple actu­ally do in busi­ness jobs—not what their job descrip­tions say, but how they spend their time and which skills seem most impor­tant to their suc­cess. “I’ve come to see that when­ever a group insti­tutes a cre­den­tial­ing process, whether by licens­ing or insist­ing on advanced degrees, the espoused rhetoric is to enforce the stan­dards of pro­fes­sion­al­ism. This is true whether it’s among accoun­tants or plumbers or physi­cians. But the observed con­se­quences always seem to be these two: the exclu­sion of cer­tain groups, whether by inten­tion or not, and the estab­lish­ment of mediocre per­for­mance standards.“‘

    pro­fes­sion­al­iza­tion cre­den­tial­ing Andrew-​​Abbott-​​smiles-​​in-​​Chicago author­ity exper­tise cultural-​​assumptions disintermediation-​​targets

  • [1205.2483] Edge-​​clique graphs of cock­tail par­ties have unbounded rankwidth

    “In an attempt to find a polynomial-​​time algo­rithm for the edge-​​clique cover prob­lem on cographs we tried to prove that the edge-​​clique graphs of cographs have bounded rankwidth. How­ever, this is not the case. In this note we show that the edge-​​clique graphs of cock­tail party graphs have unbounded rank width.”

    open-​​questions nudge-​​targets graph-​​theory algo­rithms

  • [1206.3235] Iden­ti­fy­ing rea­son­ing pat­terns in games

    “We present an algo­rithm that iden­ti­fies the rea­son­ing pat­terns of agents in a game, by iter­a­tively exam­in­ing the graph struc­ture of its Multi-​​Agent Influ­ence Dia­gram (MAID) rep­re­sen­ta­tion. If the deci­sion of an agent par­tic­i­pates in no rea­son­ing pat­terns, then we can effec­tively ignore that deci­sion for the pur­pose of cal­cu­lat­ing a Nash equi­lib­rium for the game. In some cases, this can lead to expo­nen­tial time sav­ings in the process of equi­lib­rium cal­cu­la­tion. More­over, our algo­rithm can be used to enu­mer­ate the rea­son­ing pat­terns in a game, which can be use­ful for con­struct­ing more effec­tive com­put­er­ized agents inter­act­ing with humans.”

    game-​​theory infer­ence strat­egy nudge-​​targets learning-​​by-​​watching

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • A List Apart: Arti­cles: Artis­tic Distance

    “While I’m sure that some­one will dis­agree, these sites have proven that very few “pro­fes­sion­als” have the abil­ity or courage to pro­vide a well-​​constructed analy­sis of some­one else’s work (whether or not the eval­u­a­tion was solicited). My opin­ion has noth­ing at all to do with either web­site, but rather with indus­try pro­fes­sion­als’ inabil­ity to chal­lenge, or fear of chal­leng­ing, the sta­tus quo. Far too often, hon­esty is met with ridicule, shame, or out­right rage from peo­ple hid­ing behind elec­tronic media. As a com­mu­nity, if our goal is to con­tinue rais­ing the bar for design, we need to get to a place where objec­tive dis­cus­sion is wel­comed, not scorned or drowned in obse­quious­ness. I would love to see dis­cus­sion of basic design move past the super­fi­cial trendi­ness of emerg­ing web technologies.”

    cri­tique col­lab­o­ra­tion advice graphic-​​design not-​​just

  • - How We Will Read: Laura Miller and Maud Newton

    “LM: Lit­er­ary peo­ple, when they talk about books, tend to think of fic­tion first. But most peo­ple, when they think about books, are think­ing about non­fic­tion, which lends itself amaz­ingly well to some kind of enhanced e-​​book expe­ri­ence. As a piece of that, I’m skep­ti­cal of enhanc­ing fic­tion e-​​books. The essence of nar­ra­tive is this sense of causal­ity and mean­ing, and when you intro­duce a lot of arbi­trary or ran­dom branch­ing things into it, it actu­ally loses it’s core plea­sure. It’s a tricky issue.”

    pub­lish­ing ebooks read­ing edi­tor

  • Per­sonal Tech for the 17th Cen­tury — Suzanne Fis­cher — Tech­nol­ogy — The Atlantic

    “The university’s John Carter Brown Library has long held the “Roger Williams Mys­tery Book,” a book that pur­port­edly belonged to Roger Williams, the rad­i­cal reli­gious thinker and founder of Rhode Island. The book is miss­ing its title page and thus has lit­tle iden­ti­fy­ing infor­ma­tion (besides a sub­ti­tle, “An Essay Con­cern­ing the Rec­on­cil­ing of Dif­fer­ences among Chris­tians”) — but it’s cov­ered with exten­sive short­hand mar­gin­a­lia sus­pected to have been writ­ten by Williams him­self some­time in the mid 1600s. The stu­dents, who include his­tory and math majors, are using this semes­ter to deci­pher the writ­ing and to deter­mine whether or not the short­hand hand­writ­ing was Williams’s hand.”

    nanohis­tory mar­gin­a­lia early-​​modern puz­zles

  • atomo

    “atomo is a small, sim­ple, insanely flex­i­ble and expres­sive pro­gram­ming lan­guage. its design is inspired by Scheme (small, sim­ple core), Slate (mul­ti­ple dis­patch, key­words), Ruby (very DSL-​​friendly), and Erlang (message-​​passing con­cur­rency). it is writ­ten in and pig­gy­backs on the Haskell run­time, per­mit­ting access to all of its power (and libraries!) through a thin layer.”

    pro­gram­ming lan­guage

  • Jour­nal of Dig­i­tal Humanities

    “The Jour­nal of Dig­i­tal Human­i­ties is a com­pre­hen­sive, peer-​​reviewed, open access jour­nal that fea­tures the best schol­ar­ship, tools, and con­ver­sa­tions pro­duced by the dig­i­tal human­i­ties com­mu­nity in the pre­vi­ous quarter.”

    digital-​​humanities jour­nal open-​​access pub­lish­ing

  • [1203.4881] Com­pu­ta­tional Com­plex­ity Analy­sis of Multi-​​Objective Genetic Programming

    Some days I just want to take genetic pro­gram­ming away from the com­puter sci­en­tists. Then I real­ize I ought to just let them keep the use­less, rit­u­al­ized thing they imag­ine it is.

    facepalm multiobjective-​​optimization software-​​development-​​is-​​not-​​programming

  • - How We Will Read: Clay Shirky

    “That is one of the poten­tial shifts in social read­ing: Can I cre­ate value for other peo­ple by say­ing that I found this pas­sage by Bruno LaTour strik­ing — even if I never look at it again? That’s an amaz­ing act of what I called “frozen shar­ing” in my last book. Being gen­er­ous about things when you are offer­ing it out to the pub­lic, with­out it being either in a spe­cific time frame or for a spe­cific target.”

    pub­lish­ing read­ing social-​​capital project be-​​useful-​​to-​​one-​​another

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • [1203.1644] The B36/​S125 “2×2″ Life-​​Like Cel­lu­lar Automaton

    “The B36/​S125 (or “2x2”) cel­lu­lar automa­ton is one that takes place on a 2D square lat­tice much like Conway’s Game of Life. Although it exhibits high-​​level behav­iour that is sim­i­lar to Life, such as chaotic but even­tu­ally sta­ble evo­lu­tion and the exis­tence of a nat­ural diag­o­nal glider, the indi­vid­ual objects that the rule con­tains gen­er­ally look very dif­fer­ent from their Life coun­ter­parts. In this arti­cle, a his­tory of notable dis­cov­er­ies in the 2×2 rule is pro­vided, and the fun­da­men­tal pat­terns of the automa­ton are described. Some the­o­ret­i­cal results are derived along the way, includ­ing a proof that the speed lim­its for diag­o­nal and orthog­o­nal space­ships in this rule are c/​3 and c/​2, respec­tively. A Mar­go­lus block cel­lu­lar automa­ton that 2×2 emu­lates is inves­ti­gated, and in par­tic­u­lar a fam­ily of oscil­la­tors made up entirely of 2 x 2 blocks are ana­lyzed and used to show that there exist oscil­la­tors with period 2m(2k — 1) for any inte­gers m,k geq 1.”

    cellular-​​automata artificial-​​life discrete-​​mathematics emer­gence mathematical-​​recreations nudge-​​targets

  • [1203.1034] Gen­eral Com­plex Poly­no­mial Root Solver and Its Fur­ther Opti­miza­tion for Binary Microlenses

    “We present a new algo­rithm to solve poly­no­mial equa­tions, and pub­lish its code, which is 1.6−3 times faster than the ZROOTS sub­rou­tine that is com­mer­cially avail­able from Numer­i­cal Recipes, depend­ing on appli­ca­tion. The largest improve­ment, when com­pared to naive solvers, comes from a fail-​​safe pro­ce­dure that per­mits us to skip the major­ity of the cal­cu­la­tions in the great major­ity of cases, with­out risk­ing cat­a­strophic fail­ure in the few cases that these are actu­ally required. Sec­ond, we iden­tify a dis­crim­i­nant that enables a ratio­nal choice between Laguerre’s Method and Newton’s Method (or a new inter­me­di­ate method) on a case-​​by-​​case basis. We briefly review the his­tory of root solv­ing and demon­strate that “Newton’s Method” was dis­cov­ered nei­ther by New­ton (1671) nor by Raph­son (1690), but only by Simp­son (1740). Some of the argu­ments lead­ing to this con­clu­sion were first given by the British his­to­rian of sci­ence Nick Koller­strom in 1992, but these do not appear to have pen­e­trated the astro­nom­i­cal com­mu­nity. Finally, we argue that Numer­i­cal Recipes should vol­un­tar­ily sur­ren­der its copy­right pro­tec­tion for non-​​profit appli­ca­tions, despite the fact that, in this par­tic­u­lar case, such pro­tec­tion was the major stim­u­lant for devel­op­ing our improved algorithm.”

    algo­rithms numerical-​​methods optics nudge-​​targets

  • [1203.1065] Sub­space clus­ter­ing of high-​​dimensional data: a pre­dic­tive approach

    “In sev­eral appli­ca­tion domains, high-​​dimensional obser­va­tions are col­lected and then analysed in search for nat­u­rally occur­ring data clus­ters which might pro­vide fur­ther insights about the nature of the prob­lem. In this paper we describe a new approach for par­ti­tion­ing such high-​​dimensional data. Our assump­tion is that, within each clus­ter, the data can be approx­i­mated well by a lin­ear sub­space esti­mated by means of a prin­ci­pal com­po­nent analy­sis (PCA). The pro­posed algo­rithm, Pre­dic­tive Sub­space Clus­ter­ing (PSC) par­ti­tions the data into clus­ters while simul­ta­ne­ously esti­mat­ing cluster-​​wise PCA para­me­ters. The algo­rithm min­imises an objec­tive func­tion that depends upon a new mea­sure of influ­ence for PCA mod­els. A penalised ver­sion of the algo­rithm is also described for car­ry­ing our simul­ta­ne­ous sub­space clus­ter­ing and vari­able selec­tion. The con­ver­gence of PSC is dis­cussed in detail, and exten­sive sim­u­la­tion results and com­par­isons to com­pet­ing meth­ods are pre­sented. The com­par­a­tive per­for­mance of PSC has been assessed on six real gene expres­sion data sets for which PSC often pro­vides state-​​of-​​art results.”

    ain’t-performance-space sta­tis­tics clus­ter­ing cure-​​for-​​dimensionality algo­rithms

  • [1203.1067] Cor­ti­cal free asso­ci­a­tion dynam­ics: dis­tinct phases of a latch­ing network

    “… The occur­rence and dura­tion of latch­ing dynam­ics is found through sim­u­la­tions to depend crit­i­cally on the strength of local attrac­tor states, expressed in the Potts model by a para­me­ter w. Here we describe with sim­u­la­tions and then ana­lyt­i­cally the bound­aries between dis­tinct phases of no latch­ing, of tran­sient and sus­tained latch­ing, deriv­ing a phase dia­gram in the plane w-​​T, where T param­e­trizes ther­mal noise effects. Impli­ca­tions for real cor­ti­cal dynam­ics are briefly reviewed in the conclusions.”

    neural-​​networks biologically-​​inspired dynamical-​​systems emergent-​​design nudge-​​targets

  • Fright­en­ingly Ambi­tious Startup Ideas

    “One of the more sur­pris­ing things I’ve noticed while work­ing on Y Com­bi­na­tor is how fright­en­ing the most ambi­tious startup ideas are. In this essay I’m going to demon­strate this phe­nom­e­non by describ­ing some. Any one of them could make you a bil­lion­aire. That might sound like an attrac­tive prospect, and yet when I describe these ideas you may notice you find your­self shrink­ing away from them.”

    every-​​idea-​​is-​​born star­tups inno­va­tion

  • [1201.6054] Attain­abil­ity in Repeated Games with Vec­tor Payoffs

    “We intro­duce the con­cept of attain­able sets of pay­offs in two-​​player repeated games with vec­tor pay­offs. A set of pay­off vec­tors is called {em attain­able} if player 1 can ensure that there is a finite hori­zon $T$ such that after time $T$ the dis­tance between the set and the cumu­la­tive pay­off is arbi­trar­ily small, regard­less of what strat­egy player 2 is using. This paper focuses on the case where the attain­able set con­sists of one pay­off vec­tor. In this case the vec­tor is called an attain­able vec­tor. We study prop­er­ties of the set of attain­able vec­tors, and char­ac­ter­ize when a spe­cific vec­tor is attain­able and when every vec­tor is attainable.”

    game-​​theory agent-​​based multiobjective-​​optimization nudge-​​targets

  • [1203.1080] Data Struc­ture Lower Bounds on Ran­dom Access to Grammar-​​Compressed Strings

    “In this paper we inves­ti­gate the prob­lem of build­ing a sta­tic data struc­ture that rep­re­sents a string s using space close to its com­pressed size, and allows fast access to indi­vid­ual char­ac­ters of s. …”

    gram­mars algo­rithms nudge-​​targets

Items of some interest…

Posted on by

These are my recent Pin​board​.in links:

  • [1112.4323] Between the­ory and prac­tice: guide­lines for an opti­miza­tion scheme with genetic algo­rithms — Part I: single-​​objective con­tin­u­ous global optimization

    The rapid advances in the field of opti­miza­tion meth­ods in many pure and applied sci­ence pose the dif­fi­culty of keep­ing track of the devel­op­ments as well as select­ing an appro­pri­ate tech­nique that best suits the prob­lem in-​​hand. From a prac­ti­tioner point of view is right­ful to wan­der “which opti­miza­tion method is the best for my prob­lem?”. Look­ing at the opti­miza­tion process as a “sys­tem” of inter­con– nected parts, in this paper are col­lected some ideas about how to tackle an opti­miza­tion prob­lem using a class of tools from evo­lu­tion­ary com­pu­ta­tions called Genetic Algo­rithms. Despite the num­ber of opti­miza­tion tech­niques avail­able nowa­days the author of this paper thinks that Genetic Algo­rithms still play a cen­tral role for their ver­sa­til­ity, robust­ness, the­o­ret­i­cal frame­work and sim­plic­ity of use. The paper can be con­sid­ered a “col­lec­tion of tips” (from lit­er­a­ture and per­sonal expe­ri­ence) for the non-​​computer-​​scientist that has to deal with opti­miza­tion prob­lems both in the sci­ence and engi­neer­ing prac­tice. No orig­i­nal meth­ods or algo­rithms are proposed.

    meta-​​optimization pragmatism-​​almost genetic-​​algorithm agile-​​almost project-​​management

  • [1112.6075] A semi­def­i­nite pro­gram­ming approach for solv­ing Mul­ti­ob­jec­tive Lin­ear Programming

    Sev­eral algo­rithms are avail­able in the lit­er­a­ture for find­ing the entire set of Pareto-​​optimal solu­tions in Mul­ti­Ob­jec­tive Lin­ear Pro­gram­ming (MOLP). How­ever, it has not been pro­posed so far an inte­rior point algo­rithm that finds all Pareto-​​optimal solu­tions of MOLP. We present an explicit con­struc­tion, based on a trans­for­ma­tion of any MOLP into a finite sequence of Semi­Def­i­nite Pro­grams (SDP), the solu­tions of which give the entire set of Pareto-​​optimal extreme points solu­tions of MOLP. These SDP prob­lems are solved by inte­rior point meth­ods; thus our approach pro­vides a pseudo-​​polynomial inte­rior point method­ol­ogy to find the set of Pareto-​​optimal solu­tions of MOLP.

    linear-​​programming algo­rithms multiobjective-​​optimization nudge-​​targets operations-​​research

  • [1112.0826] Clus­ter­ing under Per­tur­ba­tion Resilience

    Recently, Bilu and Linial for­mal­ized an implicit assump­tion often made when choos­ing a clus­ter­ing objec­tive: that the opti­mum clus­ter­ing to the objec­tive should be pre­served under small mul­ti­plica­tive per­tur­ba­tions to dis­tances between points. They showed that for max-​​cut clus­ter­ing it is pos­si­ble to cir­cum­vent NP-​​hardness and obtain polynomial-​​time algo­rithms for instances resilient to large (fac­tor $O(sqrt{n})$) per­tur­ba­tions, and sub­se­quently Awasthi et al. con­sid­ered center-​​based objec­tives, giv­ing algo­rithms for instances resilient to O(1) fac­tor per­tur­ba­tions. In this paper, we greatly advance this line of work. For center-​​based objec­tives, we present an algo­rithm that can opti­mally clus­ter instances resilient to $(1 + sqrt{2})$-factor per­tur­ba­tions, solv­ing an open prob­lem of Awasthi et al. For a com­monly used center-​​based objec­tive $k$-median, we addi­tion­ally give algo­rithms for a more relaxed assump­tion in which we allow the opti­mal solu­tion to change in a small $epsilon$ frac­tion of the points after per­tur­ba­tion. We give the first bounds known for this more real­is­tic and more gen­eral set­ting. We also pro­vide pos­i­tive results for min-​​sum clus­ter­ing which is a gen­er­ally much harder objec­tive than $k$-median (and also non-​​center-​​based). Our algo­rithms are based on new link­age cri­te­ria that may be of inde­pen­dent inter­est. Addi­tion­ally, we give sublinear-​​time algo­rithms, show­ing algo­rithms that can return an implicit clus­ter­ing from only access to a small ran­dom sample.

    clus­ter­ing sta­tis­tics nonparametric-​​methods robust­ness resilience algo­rithms nudge-​​targets

  • [1104.3516] An adap­tive hier­ar­chi­cal domain decom­po­si­tion method for par­al­lel con­tact dynam­ics sim­u­la­tions of gran­u­lar materials

    A fully par­al­lel ver­sion of the con­tact dynam­ics (CD) method is pre­sented in this paper. For large enough sys­tems, 100% effi­ciency has been demon­strated for up to 256 proces­sors using a hier­ar­chi­cal domain decom­po­si­tion with dynamic load bal­anc­ing. The iter­a­tive scheme to cal­cu­late the con­tact forces is left domain-​​wise sequen­tial, with data exchange after each iter­a­tion step, which ensures its sta­bil­ity. The num­ber of addi­tional iter­a­tions required for con­ver­gence by the par­tially par­al­lel updates at the domain bound­aries becomes neg­li­gi­ble with increas­ing num­ber of par­ti­cles, which allows for an effec­tive par­al­leliza­tion. Com­pared to the sequen­tial imple­men­ta­tion, we found no influ­ence of the par­al­leliza­tion on sim­u­la­tion results.

    sim­u­la­tion condensed-​​matter granular-​​materials complex-​​systems

Items of some interest…

Posted on by

These are my recent Pin​board​.in links:

  • [1105.4335] Phys­i­cal approaches to the dynam­ics of genetic cir­cuits: A tutorial

    “Cel­lu­lar behav­ior is gov­erned by gene reg­u­la­tory processes that are intrin­si­cally dynamic and non­lin­ear, and are sub­ject to non-​​negligible amounts of ran­dom fluc­tu­a­tions. Such con­di­tions are ubiq­ui­tous in phys­i­cal sys­tems, where they have been stud­ied for decades using the tools of sta­tis­ti­cal and non­lin­ear physics. The goal of this review is to show how approaches tra­di­tion­ally used in physics can help in reach­ing a systems-​​level under­stand­ing of liv­ing cells. To that end, we present an overview of the dynam­i­cal phe­nom­ena exhib­ited by genetic cir­cuits and their func­tional sig­nif­i­cance. We also describe the the­o­ret­i­cal and exper­i­men­tal approaches that are being used to unravel the rela­tion­ship between cir­cuit struc­ture and func­tion in dynam­i­cal cel­lu­lar processes under the influ­ence of noise, both at the single-​​cell level and in cel­lu­lar pop­u­la­tions, where inter­cel­lu­lar cou­pling plays an impor­tant role.”

    systems-​​biology biological-​​engineering genetic-​​regulatory-​​networks emergent-​​design bio­chem­istry overview

  • [1106.0371] A Novel Image Seg­men­ta­tion Enhance­ment Tech­nique based on Active Con­tour and Topo­log­i­cal Alignments

    “Topo­log­i­cal align­ments and snakes are used in image pro­cess­ing, par­tic­u­larly in locat­ing object bound­aries. Both of them have their own advan­tages and lim­i­ta­tions. To improve the over­all image bound­ary detec­tion sys­tem, we focused on devel­op­ing a novel algo­rithm for image pro­cess­ing. The algo­rithm we pro­pose to develop will based on the active con­tour method in con­junc­tion with topo­log­i­cal align­ments method to enhance the image detec­tion approach. The algo­rithm presents novel tech­nique to incor­po­rate the advan­tages of both Topo­log­i­cal Align­ments and snakes. Where the ini­tial seg­men­ta­tion by Topo­log­i­cal Align­ments is firstly trans­formed into the input of the snake model and begins its evolve­ment to the inter­ested object bound­ary. The results show that the algo­rithm can deal with low con­trast images and shape cells, demon­strate the seg­men­ta­tion accu­racy under weak image bound­aries, which respon­si­ble for lack­ing accu­racy in image detect­ing tech­niques. We have achieved bet­ter seg­men­ta­tion and bound­ary detect­ing for the image, also the abil­ity of the sys­tem to improve the low con­trast and deal with over and under segmentation.”

    image-​​segmentation algo­rithms nudge-​​targets

  • [1106.2508] A Prac­ti­cal Imple­men­ta­tion of the Bernoulli Factory

    “…While sev­eral prac­ti­cal uses of the method have been pro­posed in Monte Carlo appli­ca­tions, these require an imple­men­ta­tion frame­work that is flex­i­ble, gen­eral and effi­cient. We present such a frame­work for func­tions that are either strictly lin­ear, con­cave, or con­vex on the unit inter­val using a series of enve­lope func­tions defined through a cas­cade, and show that this method not only greatly reduces the num­ber of input bits needed in prac­tice com­pared to other cur­rently pro­posed solu­tions for more spe­cific prob­lems, but can eas­ily be cou­pled to more asymp­tot­i­cally effi­cient meth­ods to allow for the­o­ret­i­cally strong results.”

    algo­rithms numerical-​​methods Monte-​​Carlo-​​simulation probability-​​theory nudge-​​targets

  • [1105.1729] Evo­lu­tion­ary search for novel super­hard materials

    “We have devel­oped a method for pre­dic­tion of the hard­est crys­tal struc­tures in a given chem­i­cal sys­tem. It is based on the evo­lu­tion­ary algo­rithm USPEX and electronegativity-​​based hard­ness model that we have aug­mented with bond-​​valence model and graph the­ory. These exten­sions enable cor­rect descrip­tion of the hard­ness of lay­ered, mol­e­c­u­lar and low-​​symmetry crys­tal struc­tures. Apply­ing this method to C and TiO2, we have (i) obtained a num­ber of low-​​energy car­bon struc­tures with hard­ness slightly lower than dia­mond and (ii) proved that TiO2 in any of its pos­si­ble poly­morphs can­not be the hard­est oxide, its hard­ness being below 17 GPa.”

    materials-​​science genetic-​​algorithm condensed-​​matter sim­u­la­tion nudge-​​targets

  • [1109.0573] Phase Retrieval via Matrix Completion

    “This paper con­sid­ers the fun­da­men­tal prob­lem of recov­er­ing a gen­eral sig­nal, an image for exam­ple, from the mag­ni­tude of its Fourier trans­form. This prob­lem, also known as phase retrieval, arises in many appli­ca­tions and has chal­lenged engi­neers, physi­cists, and math­e­mati­cians for decades. Its ori­gin comes from the fact that detec­tors can often times only record the squared mod­u­lus of the Fres­nel or Fraun­hofer dif­frac­tion pat­tern of the radi­a­tion that is scat­tered from an object. In such set­tings, one can­not mea­sure the phase of the opti­cal wave reach­ing the detec­tor and, there­fore, much infor­ma­tion about the scat­tered object or the opti­cal field is lost since, as is well known, the phase encodes a lot of the struc­tural con­tent of the image we wish to form.”

    image-​​processing inverse-​​problems signal-​​processing system-​​identification frequency-​​space algo­rithms nudge-​​targets numerical-​​methods

  • [1109.0807] Har­monic Analy­sis of Boolean Net­works: Deter­mi­na­tive Power and Perturbations

    “Con­sider a large Boolean net­work with a feed for­ward struc­ture. Given a prob­a­bil­ity dis­tri­b­u­tion for the inputs, can one find-​​possibly small-​​collections of input nodes that deter­mine the states of most other nodes in the network?…”

    Boolean-​​networks Kauff­ma­nia com­plex­ol­ogy discrete-​​mathematics mathematical-​​recreations nudge-​​targets

  • [0801.0830] Evo­lu­tion of cen­tral pat­tern gen­er­a­tors for the con­trol of a five-​​link bipedal walk­ing mechanism

    “With the aim of pro­duc­ing a sta­ble human-​​like bipedal gait, a five-​​link pla­nar walk­ing mech­a­nism is cou­pled with a cen­tral pat­tern gen­er­a­tor (CPG) neural net­work, con­sist­ing of units based on Matsuoka’s half-​​center oscil­la­tor model with a firm basis in neu­ro­phys­i­ol­ogy. As a min­i­mal­is­tic approach to bipedal walk­ing, this type of walk­ing mech­a­nism con­tains only four actu­a­tors, and is lack­ing feet and ankles. The mech­a­nism is sim­u­lated with accu­rate physics, allow­ing real­is­tic fit­ness eval­u­a­tions for the cre­ation of CPG con­trollers through evo­lu­tion­ary com­pu­ta­tion. The oscil­la­tory para­me­ters, inter­nal con­nec­tiv­ity struc­ture, and exter­nal feed­back path­ways of the net­works are deter­mined through genetic algo­rithms (GA) opti­miza­tion. The evolved CPG net­works are trans­ferred to a hard­ware imple­men­ta­tion of the mech­a­nism, to test their per­for­mance under real-​​world dynam­ics. Results con­firm that the bio­log­i­cally inspired CPG model is very well suited for con­trol­ling legged loco­mo­tion, since a diverse man­i­fes­ta­tion of CPG net­works (with and with­out exter­nal feed­back) have been observed to suc­ceed dur­ing the course of GA eval­u­a­tions. Obser­va­tions also imply that while the CPG mech­a­nism is inher­ently able to sus­tain a sta­ble gait, the uti­liza­tion of feed­back path­ways makes the gait more human-​​like and is needed to pro­vide a means to adapt to irreg­u­lar­i­ties in the environment.”

    robot­ics engineering-​​design genetic-​​algorithm neural-​​networks cyber­net­ics nudge-​​targets

  • [1109.3351] Phys­i­cal lim­its on coop­er­a­tive protein-​​DNA bind­ing and the kinet­ics of com­bi­na­to­r­ial tran­scrip­tion regulation

    “Much of the com­plex­ity observed in gene reg­u­la­tion orig­i­nates from coop­er­a­tive protein-​​DNA bind­ing. While stud­ies of the tar­get search of pro­teins for their spe­cific bind­ing sites on the DNA have revealed design prin­ci­ples for the quan­ti­ta­tive char­ac­ter­is­tics of protein-​​DNA inter­ac­tions, no such prin­ci­ples are known for the coop­er­a­tive inter­ac­tions between DNA-​​binding pro­teins. We con­sider a sim­ple the­o­ret­i­cal model for two inter­act­ing tran­scrip­tion fac­tor (TF) species, search­ing for and bind­ing to two adja­cent tar­get sites hid­den in the genomic back­ground. We study the kinetic com­pe­ti­tion of a dimer search path­way and a monomer search path­way, as well as the steady-​​state reg­u­la­tion func­tion medi­ated by the two TFs over a broad range of TF-​​TF inter­ac­tion strengths. Using a tran­scrip­tional AND-​​logic as exem­plary func­tional con­text, we iden­tify the func­tion­ally desir­able regime for the inter­ac­tion. We find that both weak and very strong TF-​​TF inter­ac­tions are favor­able, albeit with dif­fer­ent char­ac­ter­is­tics. How­ever, there is also an unfa­vor­able regime of inter­me­di­ate inter­ac­tions where the genetic response is pro­hib­i­tively slow.”

    biological-​​engineering genetic-​​regularory-​​networks systems-​​biology emergent-​​design nudge-​​targets

  • [1109.6874] #h00t: Cen­sor­ship Resis­tant Microblogging

    “Microblog­ging ser­vices such as Twit­ter are an increas­ingly impor­tant way to com­mu­ni­cate, both for indi­vid­u­als and for groups through the use of hash­tags that denote top­ics of con­ver­sa­tion. How­ever, groups can be eas­ily blocked from com­mu­ni­cat­ing through block­ing of posts with the given hash­tags. We pro­pose #h00t, a sys­tem for cen­sor­ship resis­tant microblog­ging. #h00t presents an inter­face that is much like Twit­ter, except that hash­tags are replaced with very short hashes (e.g., 24 bits) of the group iden­ti­fier. Nat­u­rally, with such short hashes, hash­tags from dif­fer­ent groups may col­lide and #h00t users will actu­ally seek to cre­ate col­li­sions. By encrypt­ing all posts with keys derived from the group iden­ti­fiers, #h00t client soft­ware can fil­ter out other groups’ posts while mak­ing such fil­ter­ing dif­fi­cult for the adver­sary. In essence, by lever­ag­ing col­li­sions, groups can tun­nel their posts in other groups’ posts. A cen­sor could not block a given group with­out also block­ing the other groups with col­lid­ing hash­tags. We eval­u­ate the fea­si­bil­ity of #h00t through traces col­lected from Twit­ter, show­ing that a sin­gle mod­ern com­puter has enough com­pu­ta­tional through­put to encrypt every tweet sent through Twit­ter in real time. We also use these traces to ana­lyze the band­width and anonymity trade­offs that would come with dif­fer­ent vari­a­tions on how group iden­ti­fiers are encoded and hash­tags are selected to pur­pose­fully col­lide with one another.”

    social-​​media steganog­ra­phy robust­ness activism cute

  • [1107.0414] A ran­dom walk on image patches

    “In this paper we address the prob­lem of under­stand­ing the suc­cess of algo­rithms that orga­nize patches accord­ing to graph-​​based met­rics. Algo­rithms that ana­lyze patches extracted from images or time series have led to state-​​of-​​the art tech­niques for clas­si­fi­ca­tion, denois­ing, and the study of non­lin­ear dynam­ics. The main con­tri­bu­tion of this work is to pro­vide a the­o­ret­i­cal expla­na­tion for the above exper­i­men­tal obser­va­tions. Our approach relies on a detailed analy­sis of the com­mute time met­ric on pro­to­typ­i­cal graph mod­els that epit­o­mize the geom­e­try observed in gen­eral patch graphs.…”

    image-​​segmentation image-​​analysis algo­rithms com­bi­na­torics nudge-​​targets

  • [1107.0385] An algo­rithm for autonomously plot­ting solu­tion sets in the pres­ence of turn­ing points

    “Plot­ting solu­tion sets for par­tic­u­lar equa­tions may be com­pli­cated by the exis­tence of turn­ing points. Here we describe an algo­rithm which not only over­comes such prob­lem­atic points, but does so in the most gen­eral of set­tings. Appli­ca­tions of the algo­rithm are high­lighted through two exam­ples: the first pro­vides ver­i­fi­ca­tion, while the sec­ond demon­strates a non-​​trivial appli­ca­tion. The lat­ter is fol­lowed by a thor­ough run-​​time analy­sis. While both exam­ples deal with bivari­ate equa­tions, it is dis­cussed how the algo­rithm may be gen­er­al­ized for space curves in $R^{3}$.”

    visu­al­iza­tion math­e­mat­ics graph­ics approx­i­ma­tion algo­rithms nudge-​​targets

  • [1105.1033] Adap­tively Learn­ing the Crowd Kernel

    “We intro­duce an algo­rithm that, given n objects, learns a sim­i­lar­ity matrix over all n^2 pairs, from crowd­sourced data alone. The algo­rithm sam­ples responses to adap­tively cho­sen triplet-​​based relative-​​similarity queries. Each query has the form “is object ‘a’ more sim­i­lar to ‘b’ or to ‘c’?” and is cho­sen to be max­i­mally infor­ma­tive given the pre­ced­ing responses. The out­put is an embed­ding of the objects into Euclid­ean space (like MDS); we refer to this as the “crowd ker­nel.” SVMs reveal that the crowd ker­nel cap­tures promi­nent and sub­tle fea­tures across a num­ber of domains, such as “is striped” among neck­ties and “vowel vs. con­so­nant” among letters.”

    clas­si­fi­ca­tion ontology-​​discovery crowd­sourc­ing feature-​​extraction algo­rithms nudge-​​targets performance-​​space-​​analysis

  • [1109.1030] An Algo­rithm for Detect­ing Intrin­si­cally Knot­ted Graphs

    “We describe an algo­rithm that rec­og­nizes some (per­haps all) intrin­si­cally knot­ted (IK) graphs, and can help find knot­less embed­dings for graphs that are not IK. The algo­rithm, imple­mented as a Math­e­mat­ica pro­gram, has already been used by Gold­berg, Mattman, and Naimi [6] to greatly expand the list of known minor min­i­mal IK graphs, and to find knot­less embed­dings for some graphs that had pre­vi­ously resisted attempts to clas­sify them as IK or non-​​IK.”

    com­bi­na­torics topol­ogy algo­rithms nudge-​​targets

  • [1109.5635] Approx­i­mat­ing Edit Dis­tance in Near-​​Linear Time

    “We show how to com­pute the edit dis­tance between two strings of length n up to a fac­tor of 2^{~O(sqrt(log n))} in n^(1+o(1)) time. This is the first sub-​​polynomial approx­i­ma­tion algo­rithm for this prob­lem that runs in near-​​linear time, improv­ing on the state-​​of-​​the-​​art n^(1/3+o(1)) approx­i­ma­tion. Pre­vi­ously, approx­i­ma­tion of 2^{~O(sqrt(log n))} was known only for embed­ding edit dis­tance into l_​1, and it is not known if that embed­ding can be com­puted in less than qua­dratic time.”

    algo­rithms string-​​editing Levenshtein-​​distance rewriting-​​systems bioin­for­mat­ics nudge-​​targets

  • [1107.1866] Priority-​​based task reas­sign­ments in hier­ar­chi­cal 2D mesh-​​connected sys­tems using tableaux

    “Task reas­sign­ments in 2D mesh-​​connected sys­tems (2D-​​MSs) have been researched and sim­u­lated for sev­eral decades. We pro­pose a hier­ar­chi­cal 2D mesh-​​connected sys­tem (2D-​​HMS) in order to exploit the reg­u­lar nature of a 2D-​​MS. In our approach priority-​​based task assign­ments and reas­sign­ments in a 2D-​​HMS are rep­re­sented by tableaux and their algo­rithms. We pro­vide exam­ples of priority-​​based task reas­sign­ments in a 2D-​​HMS in which task relo­ca­tions are sim­ply reduced to a jeu de taquin slide.”

    sched­ul­ing operations-​​research algo­rithms grid-​​computing opti­miza­tion nudge-​​targets

  • [1101.4744] Clus­ter­ing func­tional data using wavelets

    “We present two meth­ods for detect­ing pat­terns and clus­ters in high dimen­sional time-​​dependent func­tional data. Our meth­ods are based on wavelet-​​based sim­i­lar­ity mea­sures, since wavelets are well suited for iden­ti­fy­ing highly dis­crim­i­nant local time and scale fea­tures. The mul­tires­o­lu­tion aspect of the wavelet trans­form pro­vides a time-​​scale decom­po­si­tion of the sig­nals allow­ing to visu­al­ize and to clus­ter the func­tional data into homo­ge­neous groups. For each input func­tion, through its empir­i­cal orthog­o­nal wavelet trans­form the first method uses the dis­tri­b­u­tion of energy across scales gen­er­ate a handy num­ber of fea­tures that can be suf­fi­cient to still make the sig­nals well dis­tin­guish­able. Our new sim­i­lar­ity mea­sure com­bined with an effi­cient fea­ture selec­tion tech­nique in the wavelet domain is then used within more or less clas­si­cal clus­ter­ing algo­rithms to effec­tively dif­fer­en­ti­ate among high dimen­sional pop­u­la­tions. The sec­ond method uses dis­sim­i­lar­ity mea­sures between the whole time-​​scale rep­re­sen­ta­tions and are based on wavelet-​​coherence tools. The clus­ter­ing is then per­formed using a k-​​centroid algo­rithm start­ing from these dis­sim­i­lar­i­ties. Prac­ti­cal per­for­mance of these meth­ods that jointly designs both the fea­ture selec­tion in the wavelet domain and the clas­si­fi­ca­tion dis­tance is demon­strated through sim­u­la­tions as well as daily pro­files of the French elec­tric­ity power demand.”

    clas­si­fi­ca­tion time-​​series feature-​​extraction machine-​​learning multiobjective-​​optimization ontology-​​discovery wavelets nudge-​​targets

  • [1105.3726] Con­trol­ling Com­plex Net­works with Com­pen­satory Perturbations

    “The response of com­plex net­works to per­tur­ba­tions is of utmost impor­tance in areas as diverse as ecosys­tem man­age­ment, emer­gency response, and cell repro­gram­ming. A fun­da­men­tal prop­erty of net­works is that the per­tur­ba­tion of one node can affect other nodes, in a process that may cause the entire or sub­stan­tial part of the sys­tem to change behav­ior and pos­si­bly col­lapse. Recent research in meta­bolic and food-​​web net­works has demon­strated the con­cept that net­work dam­age caused by exter­nal per­tur­ba­tions can often be mit­i­gated or reversed by the appli­ca­tion of com­pen­satory per­tur­ba­tions. Com­pen­satory per­tur­ba­tions are con­strained to be phys­i­cally admis­si­ble and amenable to imple­men­ta­tion on the net­work. How­ever, the sys­tem­atic iden­ti­fi­ca­tion of com­pen­satory per­tur­ba­tions that con­form to these con­straints remains an open prob­lem. Here, we present a method to con­struct com­pen­satory per­tur­ba­tions that can con­trol the fate of gen­eral net­works under such con­straints. Our approach accounts for the full non­lin­ear behav­ior of real com­plex net­works and can bring the sys­tem to a desir­able tar­get state even when this state is not directly acces­si­ble. Appli­ca­tions to genetic net­works show that com­pen­satory per­tur­ba­tions are effec­tive even when lim­ited to a small frac­tion of all nodes in the net­work and that they are far more effec­tive when lim­ited to the highest-​​degree nodes. The approach is con­cep­tu­ally sim­ple and com­pu­ta­tion­ally effi­cient, mak­ing it suit­able for the res­cue, con­trol, and repro­gram­ming of large com­plex net­works in var­i­ous domains.”

    emergent-​​design com­plex­ol­ogy con­trol biological-​​engineering nudge-​​targets

  • [1109.1275] A For­mal Ver­i­fi­ca­tion Approach to the Design of Syn­thetic Gene Networks

    “The design of genetic net­works with spe­cific func­tions is one of the major goals of syn­thetic biol­ogy. How­ever, con­struct­ing bio­log­i­cal devices that work “as required” remains chal­leng­ing, while the cost of uncov­er­ing flawed designs exper­i­men­tally is large. To address this issue, we pro­pose a fully auto­mated frame­work that allows the cor­rect­ness of syn­thetic gene net­works to be for­mally ver­i­fied in sil­ico from rich, high level func­tional spec­i­fi­ca­tions. Given a device, we auto­mat­i­cally con­struct a math­e­mat­i­cal model from exper­i­men­tal data char­ac­ter­iz­ing the parts it is com­posed of. The spe­cific model struc­ture guar­an­tees that all exper­i­men­tal obser­va­tions are cap­tured and allows us to con­struct finite abstrac­tions through poly­he­dral oper­a­tions. The cor­rect­ness of the model with respect to tem­po­ral logic spec­i­fi­ca­tions can then be ver­i­fied auto­mat­i­cally using meth­ods inspired by model check­ing. Over­all, our pro­ce­dure is con­ser­v­a­tive but it can fil­ter through a large num­ber of poten­tial device designs and select few that sat­isfy the spec­i­fi­ca­tion to be imple­mented and tested fur­ther exper­i­men­tally. Illus­tra­tive exam­ples of the appli­ca­tion of our meth­ods to the design of sim­ple syn­thetic gene net­works are included.”

    genetic-​​regulatory-​​networks bioin­for­mat­ics biological-​​engineering design-​​automation emergent-​​design acceptance-​​testing performance-​​measure nudge

  • [1108.1150] Epis­ta­sis can lead to frag­mented neu­tral spaces and con­tin­gency in evolution

    “Under neu­tral rec­i­p­ro­cal sign epis­ta­sis, two genetic changes are jointly neu­tral, even though their indi­vid­ual effects are dele­te­ri­ous. By using the widely stud­ied map­ping from an RNA sequence to sec­ondary struc­ture, we inves­ti­gate the effect of this kind of epis­ta­sis on neu­tral spaces cor­re­spond­ing to net­works of geno­types that fold to the same sec­ondary struc­ture. Neu­tral net­works for RNA struc­tures with n bonds are typ­i­cally frag­mented into at least 2n dif­fer­ent neu­tral com­po­nents that can­not be con­nected by sin­gle point muta­tions. By exhaus­tive enu­mer­a­tion of all RNA sec­ondary struc­tures of sequences of length 15 we show that most net­works are not dom­i­nated by one neu­tral com­po­nent, but are rather bro­ken up into mul­ti­ple large com­po­nents. Although they gen­er­ate the same phe­no­type, com­po­nents of a sin­gle neu­tral net­work are het­ero­ge­neous, show­ing wide vari­a­tions in their robust­ness and their evolv­abil­ity. Both prop­er­ties are cor­re­lated with com­po­nent size, rather than with the size of their under­ly­ing neu­tral net­work. In par­tic­u­lar, sets of acces­si­ble phe­no­types can vary quite strongly between com­po­nents. Thus, the poten­tial for future inno­va­tion is con­tin­gent on which neu­tral com­po­nent a pop­u­la­tion occu­pies. We fur­ther argue that neu­tral rec­i­p­ro­cal sign epis­ta­sis may have sim­i­lar con­se­quences for neu­tral evo­lu­tion of other bio­log­i­cal sys­tems as well.”

    com­bi­na­torics RNA neutral-​​networks com­plex­ol­ogy bioin­for­mat­ics polymer-​​models mathematical-​​recreations nudge-​​targets

  • Old​Fonts​.com | About Us

    “Will­son founded 3IP in 1989 to self-​​publish a book of pre­ten­tious nature essays. Soon after, he found him­self tin­ker­ing with type design, and 3IP has since become known for its library of authentic-​​looking hand­writ­ing fonts—many of them mod­eled after his­tor­i­cal penmanship—and antique text simulations.”

    typog­ra­phy fonts hand­writ­ing

  • Col­lec­tive Wis­dom — Crooked Timber

    “More broadly, a sim­ple dic­tum such as ‘lis­ten to the experts’ isn’t going to work, pre­cisely because our most pow­er­ful meth­ods of gen­er­at­ing new knowl­edge (viz. the sci­ences) are not so much based on lis­ten­ing to indi­vid­ual experts, as on includ­ing these experts (and many oth­ers) in broader social sys­tems which expose them con­tin­u­ally to the ideas of oth­ers and vice-​​versa. Design­ing (or – per­haps bet­ter– nur­tur­ing) such sys­tems is hard to think about and hard to do – but it has to be the way forward.”

    via:arsyed wisdom-​​of-​​crowds com­plex­ol­ogy inno­va­tion cultural-​​assumptions cre­den­tial­ing problem-​​solving what-​​is-​​true-​​is-​​what-​​gets-​​said

  • [1109.1146] A Dis­trib­uted Mincut/​Maxflow Algo­rithm Com­bin­ing Path Aug­men­ta­tion and Push-​​Relabel

    “We develop a novel dis­trib­uted algo­rithm for the min­i­mum cut prob­lem. We pri­mar­ily aim at solv­ing large sparse prob­lems. Assum­ing ver­tices of the graph are par­ti­tioned into sev­eral regions, the algo­rithm per­forms path aug­men­ta­tions inside the regions and updates of the push-​​relabel style between the regions. The inter­ac­tion between regions is con­sid­ered expen­sive (regions are loaded into the mem­ory one-​​by-​​one or located on sep­a­rate machines in a net­work). The algo­rithm works in sweeps — passes over all regions. Let $B$ be the set of ver­tices inci­dent to inter-​​region edges of the graph. We present a sequen­tial and par­al­lel ver­sions of the algo­rithm which ter­mi­nate in at most $2|B|^2+1$ sweeps. The com­pet­ing algo­rithm by Delong and Boykov uses push-​​relabel updates inside regions. In the case of a fixed par­ti­tion we prove that this algo­rithm has a tight $O(n^2)$ bound on the num­ber of sweeps, where $n$ is the num­ber of ver­tices. We tested sequen­tial ver­sions of the algo­rithms on instances of maxflow prob­lems in com­puter vision. Exper­i­men­tally, the num­ber of sweeps required by the new algo­rithm is much lower than for the Delong and Boykov’s vari­ant. Large prob­lems (up to $108$ ver­tices and $6cdot 108$ edges) are solved using under 1GB of mem­ory in about 10 sweeps.”

    algo­rithms operations-​​research nudge-​​targets

  • [1105.4953] A fast near­est neigh­bor search algo­rithm based on vec­tor quantization

    “In this arti­cle, we pro­pose a new fast near­est neigh­bor search algo­rithm, based on vec­tor quan­ti­za­tion. Like many other branch and bound search algo­rithms [1,10], a pre­pro­cess­ing recur­sively par­ti­tions the data set into dis­jointed sub­sets until the num­ber of points in each part is small enough. In doing so, a search-​​tree data struc­ture is built. This pre­lim­i­nary recur­sive data-​​set par­ti­tion is based on the vec­tor quan­ti­za­tion of the empir­i­cal dis­tri­b­u­tion of the ini­tial data-​​set. Unlike pre­vi­ously cited meth­ods, this kind of par­ti­tions does not a pri­ori allow to elim­i­nate sev­eral brother nodes in the search tree with a sin­gle test. To over­come this dif­fi­culty, we pro­pose an algo­rithm to reduce the num­ber of tested brother nodes to a min­i­mal list that we call “friend Voronoi cells”. The com­plete descrip­tion of the method requires a deeper insight into the prop­er­ties of Delau­nay tri­an­gu­la­tions and Voronoi diagrams”

    algo­rithms search-​​algorithms data-​​analysis nudge-​​targets

  • [1108.0986] A prox­i­mal point algo­rithm for sequen­tial fea­ture extrac­tion applications

    “We pro­pose a prox­i­mal point algo­rithm to solve LAROS prob­lem, that is the prob­lem of find­ing a “large approx­i­mately rank-​​one sub­ma­trix”. This LAROS prob­lem is used to sequen­tially extract fea­tures in data. We also develop a new stop­ping cri­te­rion for the prox­i­mal point algo­rithm, which is based on the dual­ity con­di­tions of eps-​​optimal solu­tions of the LAROS prob­lem, with a the­o­ret­i­cal guar­an­tee. We test our algo­rithm with two image data­bases and show that we can use the LAROS prob­lem to extract appro­pri­ate com­mon fea­tures from these images.”

    algo­rithms image-​​segmentation feature-​​extraction nudge-​​targets

  • [1011.2348] Ergodic Con­trol and Poly­he­dral approaches to PageR­ank Optimization

    “We study a gen­eral class of PageR­ank opti­miza­tion prob­lems which con­sist in find­ing an opti­mal out­link strat­egy for a web site sub­ject to design con­straints. We con­sider both a con­tin­u­ous prob­lem, in which one can choose the inten­sity of a link, and a dis­crete one, in which in each page, there are oblig­a­tory links, fac­ul­ta­tive links and for­bid­den links. We show that the con­tin­u­ous prob­lem, as well as its dis­crete vari­ant when there are no con­straints cou­pling dif­fer­ent pages, can both be mod­eled by con­strained Markov deci­sion processes with ergodic reward, in which the web­mas­ter deter­mines the tran­si­tion prob­a­bil­i­ties of web­surfers. Although the num­ber of actions turns out to be expo­nen­tial, we show that an asso­ci­ated poly­tope of tran­si­tion mea­sures has a con­cise rep­re­sen­ta­tion, from which we deduce that the con­tin­u­ous prob­lem is solv­able in poly­no­mial time, and that the same is true for the dis­crete prob­lem when there are no cou­pling con­straints. We also pro­vide effi­cient algo­rithms, adapted to very large net­works. Then, we inves­ti­gate the qual­i­ta­tive fea­tures of opti­mal out­link strate­gies, and iden­tify in par­tic­u­lar assump­tions under which there exists a “mas­ter” page to which all con­trolled pages should point. We report numer­i­cal results on frag­ments of the real web graph.”

    opti­miza­tion PageR­ank operations-​​research algo­rithms nudge-​​targets