nhaliday + acm + list   36

Solution concept - Wikipedia
In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

Many solution concepts, for many games, will result in more than one solution. This puts any one of the solutions in doubt, so a game theorist may apply a refinement to narrow down the solutions. Each successive solution concept presented in the following improves on its predecessor by eliminating implausible equilibria in richer games.

nice diagram
concept  conceptual-vocab  list  wiki  reference  acm  game-theory  inference  equilibrium  extrema  reduction  sub-super 
12 weeks ago by nhaliday
gt.geometric topology - Intuitive crutches for higher dimensional thinking - MathOverflow
Terry Tao:
I can't help you much with high-dimensional topology - it's not my field, and I've not picked up the various tricks topologists use to get a grip on the subject - but when dealing with the geometry of high-dimensional (or infinite-dimensional) vector spaces such as R^n, there are plenty of ways to conceptualise these spaces that do not require visualising more than three dimensions directly.

For instance, one can view a high-dimensional vector space as a state space for a system with many degrees of freedom. A megapixel image, for instance, is a point in a million-dimensional vector space; by varying the image, one can explore the space, and various subsets of this space correspond to various classes of images.

One can similarly interpret sound waves, a box of gases, an ecosystem, a voting population, a stream of digital data, trials of random variables, the results of a statistical survey, a probabilistic strategy in a two-player game, and many other concrete objects as states in a high-dimensional vector space, and various basic concepts such as convexity, distance, linearity, change of variables, orthogonality, or inner product can have very natural meanings in some of these models (though not in all).

It can take a bit of both theory and practice to merge one's intuition for these things with one's spatial intuition for vectors and vector spaces, but it can be done eventually (much as after one has enough exposure to measure theory, one can start merging one's intuition regarding cardinality, mass, length, volume, probability, cost, charge, and any number of other "real-life" measures).

For instance, the fact that most of the mass of a unit ball in high dimensions lurks near the boundary of the ball can be interpreted as a manifestation of the law of large numbers, using the interpretation of a high-dimensional vector space as the state space for a large number of trials of a random variable.

More generally, many facts about low-dimensional projections or slices of high-dimensional objects can be viewed from a probabilistic, statistical, or signal processing perspective.

Scott Aaronson:
Here are some of the crutches I've relied on. (Admittedly, my crutches are probably much more useful for theoretical computer science, combinatorics, and probability than they are for geometry, topology, or physics. On a related note, I personally have a much easier time thinking about R^n than about, say, R^4 or R^5!)

1. If you're trying to visualize some 4D phenomenon P, first think of a related 3D phenomenon P', and then imagine yourself as a 2D being who's trying to visualize P'. The advantage is that, unlike with the 4D vs. 3D case, you yourself can easily switch between the 3D and 2D perspectives, and can therefore get a sense of exactly what information is being lost when you drop a dimension. (You could call this the "Flatland trick," after the most famous literary work to rely on it.)
2. As someone else mentioned, discretize! Instead of thinking about R^n, think about the Boolean hypercube {0,1}^n, which is finite and usually easier to get intuition about. (When working on problems, I often find myself drawing {0,1}^4 on a sheet of paper by drawing two copies of {0,1}^3 and then connecting the corresponding vertices.)
3. Instead of thinking about a subset S⊆R^n, think about its characteristic function f:R^n→{0,1}. I don't know why that trivial perspective switch makes such a big difference, but it does ... maybe because it shifts your attention to the process of computing f, and makes you forget about the hopeless task of visualizing S!
4. One of the central facts about R^n is that, while it has "room" for only n orthogonal vectors, it has room for exp⁡(n) almost-orthogonal vectors. Internalize that one fact, and so many other properties of R^n (for example, that the n-sphere resembles a "ball with spikes sticking out," as someone mentioned before) will suddenly seem non-mysterious. In turn, one way to internalize the fact that R^n has so many almost-orthogonal vectors is to internalize Shannon's theorem that there exist good error-correcting codes.
5. To get a feel for some high-dimensional object, ask questions about the behavior of a process that takes place on that object. For example: if I drop a ball here, which local minimum will it settle into? How long does this random walk on {0,1}^n take to mix?

Gil Kalai:
This is a slightly different point, but Vitali Milman, who works in high-dimensional convexity, likes to draw high-dimensional convex bodies in a non-convex way. This is to convey the point that if you take the convex hull of a few points on the unit sphere of R^n, then for large n very little of the measure of the convex body is anywhere near the corners, so in a certain sense the body is a bit like a small sphere with long thin "spikes".
q-n-a  intuition  math  visual-understanding  list  discussion  thurston  tidbits  aaronson  tcs  geometry  problem-solving  yoga  👳  big-list  metabuch  tcstariat  gowers  mathtariat  acm  overflow  soft-question  levers  dimensionality  hi-order-bits  insight  synthesis  thinking  models  cartoons  coding-theory  information-theory  probability  concentration-of-measure  magnitude  linear-algebra  boolean-analysis  analogy  arrows  lifts-projections  measure  markov  sampling  shannon  conceptual-vocab  nibble  degrees-of-freedom  worrydream  neurons  retrofit  oscillation  paradox  novelty  tricki  concrete  high-dimension  s:***  manifolds  direction  curvature  convexity-curvature  elegance  guessing 
december 2016 by nhaliday

bundles : academeacmframemeta

related tags

aaronson  abstraction  academia  accretion  accuracy  acm  acmtariat  advanced  advice  age-generation  aging  algebra  algorithmic-econ  algorithms  AMT  analogy  apollonian-dionysian  applicability-prereqs  applications  approximation  arrows  art  atoms  backup  bandits  bayesian  berkeley  best-practices  big-list  big-picture  bioinformatics  bits  books  boolean-analysis  bounded-cognition  business  calculation  caltech  career  cartoons  chart  cheatsheet  checklists  chemistry  classic  clever-rats  code-dive  code-organizing  coding-theory  cog-psych  competition  complex-systems  complexity  composition-decomposition  computation  concentration-of-measure  concept  conceptual-vocab  concrete  concurrency  conference  confluence  confusion  constraint-satisfaction  contrarianism  convergence  convexity-curvature  coupling-cohesion  course  cracker-econ  criminal-justice  cs  culture  curvature  cycles  dan-luu  dark-arts  data-science  data-structures  debt  decision-making  decision-theory  deep-learning  definition  degrees-of-freedom  differential  dimensionality  direction  discussion  distribution  dropbox  duality  dumb-ML  econometrics  economics  econotariat  electromag  elegance  ends-means  engineering  entropy-like  equilibrium  erik-demaine  error  estimate  ethics  events  examples  expert  expert-experience  explanation  extrema  fall-2016  finance  finiteness  formal-values  fourier  frontier  functional  game-theory  garett-jones  gaussian-processes  generative  genomics  geometry  gowers  graph-theory  graphical-models  graphs  ground-up  growth  guessing  hardware  hi-order-bits  high-dimension  history  hmm  homepage  homogeneity  housing  hsu  hypothesis-testing  ideas  identity  IEEE  impact  impro  inference  info-foraging  information-theory  init  insight  integral  interdisciplinary  intricacy  intuition  iron-age  jargon  jobs  journos-pundits  knowledge  language  latent-variables  learning-theory  lecture-notes  lectures  legacy  lens  lesswrong  letters  levers  lifts-projections  limits  linear-algebra  linearity  liner-notes  links  linux  list  logic  machine-learning  macro  magnitude  management  manifolds  marginal-rev  market-failure  markets  markov  martingale  math  math.CA  math.CO  math.CV  math.GN  math.GR  math.NT  math.RT  mathtariat  measure  mechanism-design  mediterranean  meta:math  metabuch  metal-to-virtual  metameta  methodology  micro  microsoft  mit  ML-MAP-E  model-class  models  moments  mostly-modern  motivation  multi  music-theory  neuro  neurons  nibble  nips  nitty-gritty  novelty  numerics  objektbuch  occam  ocw  off-convex  online-learning  optimization  ORFE  org:bleg  org:edu  org:inst  org:med  os  oscillation  outcome-risk  overflow  p:**  p:***  p:null  p:someday  p:whenever  papers  paradox  parsimony  pdf  performance  philosophy  physics  pigeonhole-markov  pls  postmortem  pragmatic  pre-2013  presentation  prioritizing  probability  problem-solving  productivity  programming  project  proofs  properties  psychology  python  q-n-a  qra  quantum  quixotic  rand-approx  random  rationality  ratty  reading  recommendations  recruiting  reduction  reference  reflection  regularizer  regulation  relativity  research  research-program  retrofit  review  rhetoric  risk  roadmap  s:*  s:***  sampling  scholar-pack  scitariat  series  shannon  skeleton  sky  slides  smoothness  social  soft-question  space  spearhead  spectral  stanford  stat-mech  stats  stochastic-processes  stories  stream  street-fighting  studying  sub-super  subculture  submodular  summary  sv  symmetry  synthesis  system-design  systems  talks  tcs  tcstariat  tech  techtariat  telos-atelos  the-classics  thermo  thinking  thurston  tidbits  time-complexity  toolkit  top-n  topology  track-record  tricki  tutorial  twitter  unit  unix  unsupervised  usa  video  visual-understanding  waves  wiki  winter-2017  working-stiff  workshop  world-war  wormholes  worrydream  yoga  🎓  👳  🖥  🤖  🦉 

Copy this bookmark: