Quantcast

Posts tagged with graph theory




Michael Conover: Information Visualization for Large-Scale Data Workflows

  • data geometry
  • memes
  • visual analysis of program structure
  • visual analysis of propaganda
  • image
  • compare last week’s analysis and share with colleagues
  • geom_bin2d rather than geom_point(alpha=...) in ggplot2
  • ggpairs
  • automated grading: in addition to unit testing, 1) parse syntax trees of submissions, 2) define edit distance between them, 3) induces a network structure, 4) identify clusters, 5) give feedback to a representative member of the cluster and cc: everyone else




Car Concept Visual Memex via sfdp by Tomasz Malisiewicz

hi-res




Birds appear to offer, in their behavior, neurophysiology, and neuroanatomy a striking case of parallel evolution of consciousness. Evidence of near human-like levels of consciousness has been most dramatically observed in African grey parrots. Mammalian and avian emotional networks and cognitive microcircuitries appear to be far more homologous than previously thought. Moreover, certain species of birds have been found to exhibit neural sleep patterns similar to those of mammals, including REM sleep and, as was demonstrated in zebra finches, neurophysiological patterns, previously thought to require a mammalian neocortex. Magpies in particular have been shown to exhibit striking similarities to humans, great apes, dolphins, and elephants in studies of mirror self-recognition.

Evidence that human and non-human animal emotional feelings arise from homologous subcortical brain networks provide compelling evidence for evolutionarily shared primal affective qualia.

“The absence of a neocortex does not appear to preclude an organism from experiencing affective states. Convergent evidence indicates that non-human animals have the neuroanatomical, neurochemical, and neurophysiological substrates of conscious states along with the capacity to exhibit intentional behaviors. Consequently, the weight of evidence indicates that humans are not unique in possessing the neurological substrates that generate consciousness. Non-human animals, including all mammals and birds, and many other creatures, including octopuses, also possess these neurological substrates.”

the Cambridge Declaration on Consciousness, 2012

hat tip to fibrations

(Source: fcmconference.org)




I don’t think so, for the following reasons:

  • Companies are still run imperfectly.
  • Costs are still not as efficiently optimised as possible.
  • Workers don’t produce output at the highest conceivable rate in their current occupation.
  • Plenty of potential engaged in low-productivity work, unemployed, or otherwise not producing (e.g., in school).
  • People do wrong, imperfect things all the time. So there’s room for improvement.

I realise this argument is incomplete. Just because there’s room to grow doesn’t mean we’ll get there. However I think this line of reasoning may prove productive even if my version of it doesn’t get quite there. So let’s press on.

Half a century after Solow, many economists and rest-of-us still think of economic growth as an exogenous “magical” process driven by abstract words such as “technology” or “skill” or “trade” or “innovation”—rather than as the macro sum of correct micro decisions taken by individuals at the company two towns over.

Solow growth model

Some of that surely is to blame on things like Y=C+I+G+NX. Everything “the government” spends is G—regardless of whether it’s spent on a really good idea, implemented well, or on a pie-in-the-sky promise of a half-price incinerator with huge cost overrun. This is like "economists’ K working to constrain our thinking". Or like the Mpemba effect where one first assumes temperature is one-dimensional (false) and then infers that “you have to go through here to get to there”.

 

I prefer to think about a time-varying graph

image.

  • Most of the people (nodes) in the graph I do not trade with directly.
  • The stores I shop at are “popular” nodes. Everyone in my neighbourhood hops 1 to our grocery store. And the grocery store hops 1 or 2 to many many suppliers all over the country (and outside our country).
  • Salaried people have one very-very thick edge connecting to their sole employer.
  • And so on.

With this model it’s less tempting to use abstract words like “technology” without getting more specific. Clearly this new highway will reduce transit times for many of the transaction-edges. And therefore reduce costs broadly, ergo growth. But its effects are (a) localised to those who touch that edge (or an edge that touches that edge) (b) helping some more than others (even hurting a few on net) and [c] rather than being inevitable, come from the good work of individuals, who could have screwed it up. Now it’s tempting to, rather than wish for some magical entrepreneurs or inventors, look at ordinary decisions; not divide the world into “government vs private enterprise”; consider the individuals in particular places who are helped or hurt rather than an average … basically I find this much more grounded and less prone to theoretical histrionics.

Instead of focussing on growth as a 1-D number (Mpemba), trying to correlate it with size of government or regress it against “trust index” or “ethnofract index” or other abstract highfalutins, the GDP number can only be gotten by integrating all the micro elements—which is, I think, as it should be. Then instead of counting on the magical 2% number to stay around 2% year after year, it’s nicely surprising if the total value of transactions this year was again at its record historical high. And when people can squeeze even a higher total of value throughput through the year (out of what? out of natural resources? out of ingenuity? out of Saudi muppets?) you have to wonder where that growth came from—if it was from a sequence of very old “industrial revolutions” or from many companies doing things a little better this year than they did last year. (¬∀, but on net.)

 

Will smart machines make low-wage jobs redundant?

P Krugman asserts in his blog post about Robert Gordon’s paper

machines may soon be ready to perform many tasks that currently require large amounts of human labor. …[I]t’s all too easy to make the case that most Americans will be left behind, because smart machines will end up devaluing the contribution of workers, including highly skilled workers whose skills suddenly become redundant.

So: yes, armies of back-office pencil-pushers have been replaced in the IT revolution by computers. Thank goodness: what a boring, repetitive worklife. But besides record-keeping and verification and copying and automated checking of things, what is it that humans do that’s been replaced by machines? Travel agents? Brick-and-mortar stores with poor selection and high prices? A lot of things computers are good at, like spidering the web, is not something that we previously paid humans to do.

For example Indeed.com, a billion-dollar company created within the last decade, uses electronic computation, networks, and O(100) software engineers to usefully index job search results from disparate sources across the Web. Who lost that job? This is basically a billion-dollar free lunch vis-à-vis unemployment.

Another example that comes to mind is the auto-scan machines at the grocery store. These machines actually make a single clerk more productive. Not that her wages went up necessarily, but the efficiency of the economy did.

So why do peole think automation will replace low-wage jobs? If it’s based on evidence rather than me sitting on my couch and spitballing I’m willing to listen. But from my armchair I see people computing electronic tasks that no human used to do, Siri computing what the iPhone users said, Toyota and NewBalance augmenting humans with machines, machine learning/AI/statistical forecasting making digital things better but again not disemploying anyone.

Despite the appeal of using widespread unemployment as a basis for dystopian fiction, I don’t see anyone scrambling at the profit opportunity to make window-washing droids, janitorial droids, pizza-delivery droids, anything that requires operating in a broad ambiente. The machines seem to be great for repeating the same task in a well-defined scenario, same as factory robots at the Toyota since decades ago.




A tiny portion of Doug Hofstadter’s “semantic network”.
via jewcrew728, structure of entropy

hi-res




A sensible partial order ranking countries in the 2008 Olympics
—made by the guy who wrote PuTTY
I love posets because of situations like this. Not everything in life is completely one-dimensional, but that’s not to say it’s 100% disorderly either! Mathematics has some pretty good ideas for how to rationally label the world, sometimes.
  
Tatham’s description of the dilemma of ranking countries absolutely on 3 criteria reminds me of
multicriteria modelling
Arrow’s impossibility theorem
various multicriteria bargains or decisions to be made in regular life, like
which house to buy
which job to take
which city to move to
which président to elect
which school to attend
which product to recommend to a customer
all of which, if they’re quantifiable at all, usually consist of multiple independent, uncombinable factors (Would you like your président to be humane, or good with the economy? Well, I’d ideally like both… Would you like your employer to not beat you, or to pay you a living wage? Um, again, ideally both…). In the most naïve approach are combined with a linear weighting. (A concave weighting with positive cross-partials should be more sensible.)
As Tatham notes, using the magic of irrational numbers it’s possible to guarantee uniqueness of a ranking—but would the ranking be any good?
Well given that we know K Arrow’s Impossibility result, maybe we should just reduce our expectations. Instead of trying to squeeze a 2-ton elephant into a miniskirt made for Kate Moss, maybe we should relax the requirements and just hope to get a poset. That can be more doable.
It’s an application of Vilfredo Pareto’s genius idea.

A sensible partial order ranking countries in the 2008 Olympics

—made by the guy who wrote PuTTY

I love posets because of situations like this. Not everything in life is completely one-dimensional, but that’s not to say it’s 100% disorderly either! Mathematics has some pretty good ideas for how to rationally label the world, sometimes.

  

Tatham’s description of the dilemma of ranking countries absolutely on 3 criteria reminds me of

  • multicriteria modelling
  • Arrow’s impossibility theorem
  • various multicriteria bargains or decisions to be made in regular life, like
  • which house to buy
  • which job to take
  • which city to move to
  • which président to elect
  • which school to attend
  • which product to recommend to a customer

all of which, if they’re quantifiable at all, usually consist of multiple independent, uncombinable factors (Would you like your président to be humane, or good with the economy? Well, I’d ideally like both… Would you like your employer to not beat you, or to pay you a living wage? Um, again, ideally both…). In the most naïve approach are combined with a linear weighting. (A concave weighting with positive cross-partials should be more sensible.)

As Tatham notes, using the magic of irrational numbers it’s possible to guarantee uniqueness of a ranking—but would the ranking be any good?

Well given that we know K Arrow’s Impossibility result, maybe we should just reduce our expectations. Instead of trying to squeeze a 2-ton elephant into a miniskirt made for Kate Moss, maybe we should relax the requirements and just hope to get a poset. That can be more doable.

It’s an application of Vilfredo Pareto’s genius idea.

(Source: godplaysdice.blogspot.com)


hi-res




It’s wrong to say that faith and science are opposites,

  • not only because that’s playing into the presentist viewpoint of American fundamentalists fighting to teach creationism in science class versus /r/atheism, but because
  • scientists don’t choose their research programmes at random. They “have a hunch” — or an aesthetic sense impels them. But staking your career on  the belief that a particular line of investigation will be fruitful, both in a scientific sense and in a value-to-humanity sense, requires stronger language than merely “I think so” or “I have a hunch”. I think it’s fair to say that scientists have faith in their research programmes.

I’ll give an example of a research programme that I have faith in. Mostly unjustified faith, but I believe it nonetheless. (I could be wrong, of course — but still I can’t approach the world with no beliefs whatever — although some views of rationality would suggest that this unlivable mental life would be the most honourable way to live.)

  1. I believe there’s something wrong with economic theory. Call it a dark age on the way to enlightenment, call it an obsession with equilibrium-and-optimisation, call it the undue influence of Milton Friedman essays on the deeper, unspoken beliefs of economists vis-à-vis effect of careful studies or creative mathematics. ∃ many ways to describe the malaise | muddle | distraction | not even really sure what to call it.

    This is not based on "Economists didn’t foresee the financial crisis!" or a critique of the Washington Consensus. It’s not about Objectivists or people who don’t understand what a model is, but rather at real, non-crazy economists. It’s more based on statements like "Economics is in a terrible state"—Ariel Rubinstein. Or questions like: since information and search costs and other such things dominate the f**k out of the normal incentives-based thinking we use to armchair-speculate—then what is even the use of the partial-equilibrium intuitions or DSGE or anything like that?

    I also don’t think this idea would necessarily change the focus to more sociological or historical or cultural issues (like economists ignoring how utility functions come to be, or larger questions about history and culture and family norms … I actually think a lot of economists are already prepared to focus on those issues, they just need to make them mathematically tractable). Rather my gut instinct tells me that this research programme is “far upstream”—redirecting the river by diverting the water long before it becomes a rushing channel (sometimes called the MSNBC channel) that’s too powerful to redirect.
    nerve of cover
  2. I don’t know enough about sheaf theory or cohomology to say for certain whether they can be used for this or that. It’s just my spider sense tingling when I look at the ideas there. Most of the applications I’ve read about are to either physics problems or logic, or to higher mathematics itself (algebraic topology, algebraic geometry, topological analysis, … stuff that’s named as (adjective = way of thinking + noun = subject matter)).
    presheaf axioms
    That said I think there’s something to be found here in terms of new viewpoints on economic questions.
  3. Consider the Leontief input-output matrix (Cosma Shalizi recently wrote a lot about it in his book review of Red Plenty on Crooked Timber blog).
    hypothetical transactions from a leontief input/output matrix
    Mathematically savvy people know that every graph can be encoded as a matrix, and furthermore with the right base corpus and some knowledge of “characters” we can do one-directional graphs.
    social graph
  4. What’s the [putative] application to economics? Well instead of thinking about all this stuff we can’t observe or interpret yet—utility curves, willingness-to-pay outside the lab, valuations, etc.
    indifference curves
    (we don’t even know experimentally if there is such a thing as a valuation—and it’s kind of dubious—yet we go on as if these things exist because they’re axiomatic keystones of the only tractable theory around). Instead of continuing to rely on the theoretical stuff handed down from Bentham, let’s think about all the things we can measure—like transactions—and ask how we can use mathematics to make theories about those things and possibly infer back to the stuff we really want to know, like is capitalism making the world a better place.
  5. Transactions are one place to start. Prices (like the billion price project) are another. And the web now generates huge amounts of text—maybe we can do something with that. But let’s start by going back to the Leontief matrix.
    input output matrix
  6. In the formulation I learned in school, there’s a fixed time unit—like a year—and each dimension corresponds to an exactly comparable item class—so like a three button shirt and a four button shirt would be separate dimensions, but once we finally get down to a dimension, everything along that dimension is equivalence-classed.
  7. I can see three things missing from that picture.

    First of all, I want to be able to “zoom in” to different timescales and have my matrix change in the sensible way. In other words I want a mathematical object that operates on multiple timescales at once, with a coherent, consistent translation between the Leontief matrix of October 17th between 19:29 and 21:13 GMT, and the Leontief matrix of 1877 A.D. I believe things floating around sheaf theory are the place to look for that.
  8. Second of all, I want neighbourhood relationships (and even distances) between the items—so that a three-button blue blouse is “closer to” a four-button blue blouse than it is to a ferret named Bosco the Great sold at the Petco in Moravia, Illinois. So something from algebraic topology is necessary here.
    algebraic topology
    Maybe a tie-in to “lumpy human capital”—the most important kind of good because it’s what humans use to sustain themselves and help others. It’s acknowledge to be “lumpy” in that ten years of studying economic theory doesn’t prepare you to be a laundress or even necessarily to trade OTC derivatives. But we also know that in terms of neighbourhood relationships, economic theory studying is “closer to” finance than to farming. (Although most economists are not as close to finance as seems to be generally thought.)
  9. Both of those two points are more just æsthetic problems or issues with foundations. Like philosophical gripes could be solved, in the same way that a transition from cardinal utility to ordinal utility, even though I don’t think the outcomes of the ordinal utility theory were very different.
  10. Third, I want my matrix to be time-varying or dynamical. New trade partners come into existence, some businesses shutter their doors and file their dissolution papers, others are broken up and sold in parts, and even with an existing vendor I am not going to do the same business each year. Some of these numbers are available in XBRL format because public companies sometimes do business with each other.
  11. Fourth, and here is where I think it would be possible to get new ideas of things to measure. If I have some kind of dynamical, multi-level, “coloured” graph of all the trades in all the currencies and all the goods types in the world over the right number corpus, then I have a different mathematical conception of the world economy.
    a drawing of some foreign exchange flows I did whilst reading about cohomology ... this is the beginning of some ideas which are both graphical and hard to draw (because they're so convoluted).).
    I can draw boundaries like you would see in a cell complex and denote “a community” or “a municipality” or “a neighbourhood” or “a province” and when I perturb those boundaries some rationality conditions need to hold.
    cells with directed boundary
    Taking this viewpoint and applying only the maths that’s already been invented, people have already found a lot of invariants on graphs—cohomology invariants, generalisations of Gauss’ divergence theorem, different calcula on the interesting objects (like fox calculus)—and applying those theories to the conception of the super-duper Leontief matrix, we might find new things to measure, or new ways to make different sense of some measurements we already have.
    fox calculus
    If you remember this Perelman quote about calculating how fast Christ would have to run on the water to not sink in, or various nifty cancellations in the vacuum states of a gnarly physics theory — that is the kind of thing I’m thinking could be useful in theorising new invariants to measure from an überdy-googly Leontief trade matrix.
    string diagrams for the Frobenius algebra axioms

    Or from www.math.upenn.edu/~ghrist/preprints/ATSN.pdf we learn "The Euler characteristic χ of any compact triangulable space is independent of the particular [finite] simplicial structure imposed, as well as independent of the topological type.”
    ok, not a triangulated space. but this gives you the idea.
    Yum. Tell me more.
    another drawing from the first time I was reading about cohomology and thinking about its possible applications to a dynamical graph of actual transactions. Looking back on it this isn't super clear either. Maybe you get what I was "suggesting" though.
    For example we know some Gaussian-divergence ∑ relations that happen within the grey box of a firm—all the internal transactions have to add up to what’s written on the accounting statements. But what about applying this logic to a group of three firms that circularly trade with each other and also each has a composite edge (with different weights) adding up all of their trades to “outside the cycle”?

    Seems like some funky abstract nonsense could simplify problems like that and, crucially, tell us invariants that give us new ideas of what to measure.
  12. Fifth, this is not really related. I think the concept of symplecticity from physics nicely captures the essence of what tradeoffs are about.
    a symplectic manifold. drawn by r ghrist in the /preprints/ATSN.pdf
    But I’m still looking into this—I won’t definitely say that, it just seems like another fruit-lined avenue. 
  13. There are tie-ins to categories, causal diagrams, and other stuff wherein I may be just lumping together a lot of seemingly-related ideas.
    A causal diagram. (not to be confused with an acausal diagram!)
    So I’m not sure if looking at a super-duper Leontief matrix like described above would have nice tie-ins to causal graphs / structural equations à la Judea Pearl, but hey it might. At least one tie-in I can already think of is that all the goods actually transacted doesn’t tell you enough because there are threats and possible counterfactuals and CV’s that are sent in but get ignored or rejected, or smiles and pats on the back which are a kind of transaction that influences the economic outcomes without being tied directly to money or a goods transaction.
  14. Why go for even more abstraction, even “more” maths, when so many of the critiques of economics say it’s become too mathematical? Simple answer. More abstract mathematics requires fewer assumptions. So conclusions drawn using those tools are more likely to actually hold true in the real world. For example, is it more plausible that someone’s utility increases linearly, or monotonically with good X? Monotonically of course is much more realistic, although we could infer much more if linear were the case. But what’s the point of making easier inferences if they’re wrong because the assumptions don’t hold? Hence the interest in more general, more abstract mathematics.

Now, realistically? The scale of investigating this “hunch” in terms of concrete steps that lead A → B → C → D are way beyond what I will probably accomplish. Even if I dropped all side interests and all work, it would take at least a couple years to get publishable material out of these hunches.

But that’s exactly my point about science. I was told by a Zaazen practitioner that this is kind of a Zen-like paradox.a reflexive node (CYCLIC graph, not a dag) In order to investigate the premise that there are useful applications of sheaves & cohomology to economic theory, I first have to accept the premise that there are probably useful applications of sheaves & cohomology to economic theory.


cylical graph / circular logic

Glancing at the text above you can probably tell that my thoughts on this issue are formless, probably mischaracterising the mathematics I’ve only heard about but don’t yet understand. My mental conception of these things, if it could be understood via a perfect future theory of mental representation and fMRI snapshots of my mind thinking about this stuff, would be some mixture of formless and inaccurate.

So the important decisions (decisions of major direction, not adjustments or effort) are made amongst the formless, but can only be harvested as a form. Like the beginner’s mind, with its vagueness and formlessness, giving way to the expert’s mind, its definition, choateness, and exactitude. (Form and formlessness being complementary in the QM | vNA sense.) I think that’s Zen as well.













Listen to the doctor
crystilogic:

Kidney, this time with ions and color. It’s a whole crazy world down there. This is one of the thousands of small tubes that urine moves along on its way through the kidney, with all these transport proteins (little circles) and ion channels embedded in the membrane walls to move different things in and out.

Listen to the doctor

crystilogic:

Kidney, this time with ions and color. It’s a whole crazy world down there. This is one of the thousands of small tubes that urine moves along on its way through the kidney, with all these transport proteins (little circles) and ion channels embedded in the membrane walls to move different things in and out.