5 ms·

> We know that universal solutions can’t exist and that all practical solutions require exotic high-dimensionality computational constructs that human brains wi

• jandrewrogers 1y ago
  I'm not aware of any convenient literature but it is relatively obvious once someone explains it to you (as it was explained to me). At its root it is a cutting problem, like graph cutting but much more general because it includes things like non-trivial geometric types and relationships. Solving the cutting problem is necessary to efficiently shard/parallelize operations over the data models. For classic scalar data models, representations that preserve the relationships have the same dimensionality as the underlying data model. A set of points in 2-dimensions can always be represented in 2-dimensions such that they satisfy the cutting problem (e.g. a quadtree-like representation). For non-scalar types like rectangles, operations like equality and intersection are distinct and there are an unbounded number of relationships that must be preserved that touch on concepts like size and aspect ratio to satisfy cutting requirements. The only way to expose these additional relationships to cutting algorithms is to encode and embed these other relationships in a (much) higher dimensionality space and then cut that space instead. The mathematically general case isn't computable but real-world data models don't need it to be. Several decades ago it was determined that if you constrain the properties of the data model tightly enough then it should be possible to systematically construct a finite high-dimensionality embedding for that data model such that it satisfies the cutting problem. Unfortunately, the "should be possible" understates the difficulty. There is no computer science literature for how one might go about constructing these cuttable embeddings, not even for a narrow subset of practical cases. The activity is also primarily one of designing data structures and algorithms that can represent complex relationships among objects with shape and size in dimensions much greater than three, which is cognitively difficult. Many smart people have tried and failed over the years. It has a lot of subtlety and you need practical implementations to have good properties as software. About 20 years ago, long before "big data", the iPhone, or any current software fashion, this and several related problems were the subject of an ambitious government research program. It was technically successful, demonstrably. That program was killed in the early 2010s for unrelated reasons and much of that research was semi-lost. It was so far ahead of its time that few people saw the utility of it. There are still people around that were either directly involved or learned the computer science second-hand from someone that was but there aren't that many left.
  • andoando 1y ago
    Ive spent years trying to tackle spatial representations on my own, so Im extremely curious here. How does the cutting problem relate to intelligence in the first place?
    • jandrewrogers 1y ago
      Indexing is a special case of AI. At the limit, optimal cutting and learning are equivalent problems. Non-trivial spatial representations push these two things much closer together than is normally desirable for e.g. indexing algorithms. Tractability becomes a real issue. Practically, scalable indexing of complex spatial relationships requires what is essentially a type of learned indexing, albeit not neural network based.
      • RaftPeople 1y ago
        > is essentially a type of learned indexing, albeit not neural network based. NN is just function approximation, why do you think that could not be a valuable part of the solution? It seems like a dynamically adjusted/learned function approximator is a good general tool to most of these hard problems.
  • calf 1y ago
    But then that sounds more like that person explained it wrong. They didn't explain why it is necessary to reduce to GRAPHCUT, it seems to me to beg the question. We should not assume this is true based on some vague anthropomorphic appeal to spatial locality, surely?
    • jandrewrogers 1y ago
      It isn’t a graph cutting problem, graph cutting is just a simpler, special case of this more general cutting problem (h/t IBM Research). If you can solve the general problem you effectively get efficient graph cutting for free. This is obviously attractive to the extent you can do both complex spatial and graph computation at scale on the same data structure instead of specializing for one or the other. The challenge with cutting e.g. rectangles into uniform subsets is that logical shard assignment must be identical regardless of insertion order and in the absence of an ordering function, with O(1) space complexity and without loss of selectivity. Arbitrary sets of rectangles overlap, sometimes heavily, which is the source of most difficulty. Of course, with practical implementations write scalability matters and incremental construction is desirable.