Hi, On Mon, Mar 12, 2018 at 3:24 AM, Nil Geisweiller <ngeis...@googlemail.com> wrote: > Hi, > > I'm adding Linas, the author of the pattern matcher, who knows it better > than I do. Also, generally speaking, feel free to use the opencog list, that > way all opencog community can participate. > > On 03/11/2018 09:24 PM, Alexey Potapov wrote:
>> >> It just searches for pairs of bounding boxes one of which is higher than >> another /within the same frame/. >> We expect coordinates of BBs to be compared only within same frame, so the >> time should depend on the number of frames linearly. >> Unfortunately, it grows quadratically, and becomes too large for rather >> short videos. > > > OK, so you're saying that in principle you only need to iterate through the > frames, and fetching the corresponding coordinates should be constant, thus > it should be linear overall. Several remarks, some obvious, some maybe not: 1) The atomspace is optimized for long-term storage of knowledge representations, and for certain tasks applied to KR, e.g. subgraph isomorphism (pattern matching) 2) The atomspace is not optimized for numerical computation or general computation, so that adding two numbers with NumberNodes might be thousands if not millions of times slower than doing it "natively". That said, there are some interesting stunts that could improve generic computation by factors of hundreds or thousands, or more, if that was desired. 3) Fleeting short-term, rapidly changing data should use Values, not Atoms (!!!) 4) There is some rudimentary support for a "space-time server" to store location position data, but its not well integrated or refined: its just a super-naive octree store. Much work is needed to make it generically useful. >> Maybe, we could represent these data and queries in a better way, but the >> problem (with virtual links) seems general. The problem here is that the >> search is quadratic while it can in principle be linear. 5) The pattern matcher tries to be quite very smart about where to start searches and how to move forward in them. However, no one has ever tried to digest numeric data with it before, so failures of this kind - quadratic vs. linear, are not surprising. They're certainly fixable but (probably) not in an afternoon or two. At this point, its a rather very complex and elaborate block of code trying to do lots of things, and it very much needs a full-time devoted expert to maintain it. It will take more than weeks - maybe months to really understand what's going on inside of it. Viz. It needs an experienced pro, not a code-monkey to maintain it. >> The PM >> documentation says that its computational time can be even exponential for >> unordered links... That's not the PM, that's a fundamental mathematical statement about the isomorphism problem for unordered sets. For N elements to be matched to N variables, there are N-factorial alternatives. That's not "fixable". > One would need to look at what the pattern matcher is doing in that > instance. I suspect it chooses a sub-optimal starting point. Possibly. See above comments about numbers. >> I thought that PM is a basic function in sense that it doesn't need to be >> 'intelligent', but is one of building blocks for 'intelligent' functions >> like the backward chaining. Its not "intelligent" but it is complicated. If it looks simple, then in a certain sense, we've succeeded. :-) I want software that works well, is easy and pleasant to use, and looks "simple" to the user. > what the URE is more suitable for. Although of course the boundary is > completely blurry, as you know, but you see what I mean. We're trying to figure out the boundary by touch and feel. > I think it is solvable. In particular take a look at > https://github.com/opencog/atomspace/blob/master/opencog/query/InitiateSearchCB.h Yes. I did not catch the inital part of this, so cannot offer more. But that is where the inital starting points for a search get picked. I'm totally swamped so please don't send me long complicated blobs of code cause I won;t be able to respond quickly. >> I believe that either PM should have a guaranteed linear computational >> time, The subgraph isomorphism problem is an NP-complete problem, last time I looked. When its fast, its only because the query is hanging out in the simple side of the lambda cube. I think that for "most" queries, the pattern matcher runs in O(SAT) time that is O(Davis-Putnam) time, because it kind-of-ish performs some of the similar kind of graph pruning exploration. Sort-of-ish. But only partly. It could be made more completely Davis-Putnam by someone who has the brain cells and the time on their hands. > Nil > >> >> Best regards, >> Alexey. Linas. -- cassette tapes - analog TV - film cameras - you -- You received this message because you are subscribed to the Google Groups "opencog" group. To unsubscribe from this group and stop receiving emails from it, send an email to opencog+unsubscr...@googlegroups.com. To post to this group, send email to opencog@googlegroups.com. Visit this group at https://groups.google.com/group/opencog. To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAHrUA34jY%2BA8bS%2BzD7UKuz8ZyV_1EPrBA7iND%2Bn8JSSuL6AycA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
