{"action":"created","issue":{"url":"https://api.github.com/repos/opencog/atomspace/issues/903","repository_url":"https://api.github.com/repos/opencog/atomspace","labels_url":"https://api.github.com/repos/opencog/atomspace/issues/903/labels{/name}","comments_url":"https://api.github.com/repos/opencog/atomspace/issues/903/comments","events_url":"https://api.github.com/repos/opencog/atomspace/issues/903/events","html_url":"https://github.com/opencog/atomspace/issues/903","id":180305819,"number":903,"title":"Proposal to represent Back Inference Tree as Atomese program","user":{"login":"ngeiswei","id":819225,"avatar_url":"https://avatars.githubusercontent.com/u/819225?v=3","gravatar_id":"","url":"https://api.github.com/users/ngeiswei","html_url":"https://github.com/ngeiswei","followers_url":"https://api.github.com/users/ngeiswei/followers","following_url":"https://api.github.com/users/ngeiswei/following{/other_user}","gists_url":"https://api.github.com/users/ngeiswei/gists{/gist_id}","starred_url":"https://api.github.com/users/ngeiswei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ngeiswei/subscriptions","organizations_url":"https://api.github.com/users/ngeiswei/orgs","repos_url":"https://api.github.com/users/ngeiswei/repos","events_url":"https://api.github.com/users/ngeiswei/events{/privacy}","received_events_url":"https://api.github.com/users/ngeiswei/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/opencog/atomspace/labels/enhancement","name":"enhancement","color":"207de5"},{"url":"https://api.github.com/repos/opencog/atomspace/labels/rule-engine","name":"rule-engine","color":"fef2c0"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":7,"created_at":"2016-09-30T13:37:49Z","updated_at":"2016-10-03T19:19:58Z","closed_at":null,"body":"# Motivation\r\n\r\nRepresenting a Back Inference Tree (or BIT) directly in the AtomSpace allows us to visualize with an AtomSpace visualizer how a BIT gets expanded and reduced as the inference goes. I suggest here to attempt to represent it directly as an Atomese program that encodes a forward chaining strategy!\r\n\r\n# Words of Caution\r\n\r\nI think my attempt is semi failed because it makes the BIT bloated and introduces computational overhead. For that reason I might not use it yet, and use a C++ representation instead. However, for demo purpose, or real inferences once the aforementioned issues have been addressed, this should definitely be the way to go.\r\n\r\nI merely present an example, the representational transformation algorithm not being the hard part.\r\n\r\n## Disclaimers about this example\r\n\r\n1. It leaves out the fitness functions. I will probably represent the fitness function associated to each target as a C++ structure, again till Atomese becomes powerful enough. The fitness function is only relevant for BIT expansion anyway, not its representation.\r\n\r\n2. Only and-branches are represented. To recall, a BIT is an or-and-tree. Or-branches for the multiplicity of rules that can match a target. And-branches for the multiplicity of premises that must be fulfilled in order to apply a rule. I believe that or-branches are easy to represent, merely incoming links of and-branches over same target, therefore they are ignored.\r\n\r\n# Example\r\n\r\n## Legend\r\n\r\n1. A to F are concepts\r\n2. $W to $Z are variables\r\n3. D stands for deduction\r\n4. X->Y stands for Inheritance X Y\r\n\r\n## BIT example\r\n\r\n```\r\n           A->F\r\n            |\r\n            D\r\n            |\r\n      A->$X ,  $X->F\r\n       /          \\\r\n      D            D\r\n     /              \\\r\nA->$Y,$Y->$X   $X->$Z,$Z->F\r\n                 |\r\n                 D\r\n                 |\r\n           $X->$W,$W->$Z\r\n```\r\n\r\n## AtomSpace KB\r\n\r\n```\r\nA->B\r\nB->C\r\nC->D\r\nD->E\r\nE->F\r\n```\r\n\r\nYou can see that given the KB, in order to be able to derive A->F, one needs to expand the BIT multiple times.\r\n\r\n## BIT expansion and Atomese representation\r\n\r\nLet's look at the representation of the BIT as it expands.\r\n\r\n### First 2 levels of the BIT\r\n\r\n```\r\n           A->F\r\n            |\r\n            D\r\n            |\r\n      A->$X ,  $X->F\r\n```\r\n\r\nAssociated hypergraph:\r\n\r\n```\r\nPut\r\n  $X\r\n  ExecutionOutput\r\n    Deduction\r\n    List A->$X $X->F A->F\r\n  Get\r\n    VariableList $X\r\n    And\r\n      A->$X\r\n      $X->F\r\n```\r\n\r\nThis is merely a deduction rule application. A BindLink could have been used but as you'll see, as we build the hypergraph incrementally it is better to use a combination of Put, Get, and as it turns out, Map links.\r\n\r\n### First 3 levels of the BIT\r\n\r\n```\r\n           A->F\r\n            |\r\n            D\r\n            |\r\n      A->$X ,  $X->F\r\n       /          \\\r\n      D            D\r\n     /              \\\r\nA->$Y,$Y->$X   $X->$Z,$Z->F\r\n```\r\n\r\nAssociated hypergraph:\r\n\r\n```\r\nPut\r\n  $X\r\n  ExecutionOutput\r\n    Deduction\r\n    List A->$X $X->F A->F\r\n  MapLink\r\n    Scope\r\n      $X\r\n      List\r\n        A->$X\r\n        $X->F\r\n    Put\r\n      VariableList $X $Y $Z\r\n      List\r\n        ExecutionOutput\r\n          Deduction\r\n          List A->$Y $Y->$X A->$X\r\n        ExecutionOutput\r\n          Deduction\r\n          List $X->$Z $Z->F $X->F\r\n      Get\r\n        VariableList $X $Y $Z\r\n        And\r\n          A->$Y\r\n          $Y->$X\r\n          $X->$Z\r\n          $Z->F\r\n```\r\n\r\nNotice 2 things:\r\n\r\n1. The inner Get grows and contains all the target leaves of the BIT. That is because we only want to bother applying the forward inference if it has groundings. If so, we are guarantied that the forward inference will go unstopped, and the entire and-tree can be reduced. If not, we need to expand it further. That is how Ari Heljakka BC worked, and I strongly believe for performance reasons is the way it should be done as well. I stress that cause it's not what is described in http://wiki.opencog.org/w/Unified_rule_engine#Overall_Backward_Chaining_Process and of course not what was implemented by William Ma.\r\n2. We use Map in the middle. This is the overhead I was talking about. That is because I need a way to pass the results from the children targets to the parent. The problem is that the Map does redundant work to turn the results of rule applications of the children into variable->ground mappings, and these mappings are mere subsets of the initial results from the inner Get. I don't see a good way to do otherwise. I see how a SequenceLink could be used to control the order so that the children are reduced first, but it's kinda ugly, and then I don't see how to stop the Get from being rerun (which would be much more time consuming). It might not be such a big overhead though, likely linear, but I'm sure we can do better.\r\n\r\n### Hypergraph of the whole BIT:\r\n\r\n```\r\nPut\r\n  $X\r\n  ExecutionOutput\r\n    Deduction\r\n    List A->$X $X->F A->F\r\n  MapLink\r\n    Scope\r\n      $X\r\n      List\r\n        A->$X\r\n        $X->F\r\n    Put\r\n      VariableList $X $Y $Z\r\n      List\r\n        ExecutionOutput\r\n          Deduction\r\n          List A->$Y $Y->$X A->$X\r\n        ExecutionOutput\r\n          Deduction\r\n          List $X->Z Z->F $X->F\r\n    MapLink\r\n      Scope\r\n        $X $Y $Z\r\n        List\r\n          A->$Y\r\n          $Y->$X\r\n          $X->$Z\r\n          $Z->F\r\n      Put\r\n        $X $Y $Z $W\r\n        List\r\n          A->$Y\r\n          $Y->$X\r\n          ExecOut\r\n            Deduction\r\n            List $X->$W $W->$Z $X->$Z\r\n          $Z->F\r\n        Get\r\n          VariableList $X $Y $Z $W\r\n          And\r\n            A->$Y\r\n            $Y->$X\r\n            $X->$W\r\n            $W->$Z\r\n            $Z->F\r\n```\r\n\r\n# Conclusion\r\n\r\nI'm still undecided whether to go with the C++ representation or that one. As I've already coded half of the C++ representation, I might just try both and compare. Ultimately I know the hypergraph representation can be improved and it's just a first attempt."},"comment":{"url":"https://api.github.com/repos/opencog/atomspace/issues/comments/251199676","html_url":"https://github.com/opencog/atomspace/issues/903#issuecomment-251199676","issue_url":"https://api.github.com/repos/opencog/atomspace/issues/903","id":251199676,"user":{"login":"linas","id":94368,"avatar_url":"https://avatars.githubusercontent.com/u/94368?v=3","gravatar_id":"","url":"https://api.github.com/users/linas","html_url":"https://github.com/linas","followers_url":"https://api.github.com/users/linas/followers","following_url":"https://api.github.com/users/linas/following{/other_user}","gists_url":"https://api.github.com/users/linas/gists{/gist_id}","starred_url":"https://api.github.com/users/linas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/linas/subscriptions","organizations_url":"https://api.github.com/users/linas/orgs","repos_url":"https://api.github.com/users/linas/repos","events_url":"https://api.github.com/users/linas/events{/privacy}","received_events_url":"https://api.github.com/users/linas/received_events","type":"User","site_admin":false},"created_at":"2016-10-03T19:19:58Z","updated_at":"2016-10-03T19:19:58Z","body":"Side question: what technical problem does the BIT solve? Why do you need it?"}}
{"actor":{"display_login":"linas"}}