Author Topic: induction using Longest Common Subsequence  (Read 1048 times)

Zero

  • *
  • Autobot
  • ******
  • Posts: 201
  • Fictional character
    • AGI DEV LOG
induction using Longest Common Subsequence
« on: September 18, 2015, 10:21:20 AM »
Longest Common Subsequence (LCS) algorithms allow to find the longest subsequence common to all sequences in a set of sequences.

For a string example, consider the sequences "thisisatest" and "testing123testing". An LCS would be "tsitest".

An LCS algorithm can be easily enhanced to insert wildward characters where things are missing (done already). So, instead of "tsitest", we can get "t*s*i*test*"

Now, say you have a set of clauses, knowledge in the form of a list of simple strings:

Code: [Select]
Paul is a parent of John. Paul is a man. Paul is the father of John.

John is a parent of Miranda. John is a man. John is the father of Miranda.

Miranda is a parent of Sofia. Miranda is a woman. Miranda is the mother of Sofia.

Sofia is a parent of Chandler. Sofia is a woman. Sofia is the mother of Chandler.

Using LCS, we get:

Code: [Select]
shape:

  {1} is a parent of {2}. {3} is a {4}. {5} is the {6} of {7}.


possibilities:

  {1}        {2}        {3}        {4}        {5}        {6}        {7}
  Paul       John       Paul       man        Paul       father     John
  John       Miranda    John       man        John       father     Miranda
  Miranda    Sofia      Miranda    woman      Miranda    mother     Sofia
  Sofia      Chandler   Sofia      woman      Sofia      mother     Chandler

Here you can see that apparently the following is always true:

Code: [Select]
  {1} is the same as {3}
  {1} is the same as {5}
  {3} is the same as {5}
  {2} is the same as {7}
  when {4} is "man" then {6} is "father" and vice versa
  when {4} is "woman" then {6} is "mother" and vice versa

We can reduce it to:

Code: [Select]
shape:

  {1} is a parent of {2}. {1} is a {4}. {1} is the {6} of {2}.


possibilities:

  {1}        {2}        {4}        {6}
  Paul       John       man        father
  John       Miranda    man        father
  Miranda    Sofia      woman      mother
  Sofia      Chandler   woman      mother


rules:

  when {4} is "man" then {6} is "father" and vice versa
  when {4} is "woman" then {6} is "mother" and vice versa



Each chunk of knowledge is made of 3 sentences:

Code: [Select]
  A: {1} is a parent of {2}    => nothing in rules

  B: {1} is a {4}              => {4} in rules

  C: {1} is the {6} of {2}     => {6} in rules + everything from A is here


If one of these sentences is missing, how can we induce it?

If A is missing, we can be sure that it should be here if C is here, because everything from A is in C (A contains {1} and {2}, and C contains them both). So if C is here, A has to be here. We have to state every possible value of {6}.

Code: [Select]
  sufficient: "1" is the father of "2"
  sufficient: "1" is the mother of "2"
  formulate: "1" is a parent of "2"


If B is missing, it should be here if we have both A and C. Since C is involved in rules, we have to state every possible value of {6} and apply the corresponding value of {4}.

Code: [Select]
  necessary: "1" is a parent of "2"
  necessary: "1" is the father of "2"
  formulate: "1" is a man

  necessary: "1" is a parent of "2"
  necessary: "1" is the mother of "2"
  formulate: "1" is a woman


If C is missing, we do like B missing.

Code: [Select]
  necessary: "1" is a parent of "2"
  necessary: "1" is a man
  formulate: "1" is the father of "2"

  necessary: "1" is a parent of "2"
  necessary: "1" is a woman
  formulate: "1" is the mother of "2"


Obviously, this is induction, so it can lead to mistakes. For instance, if we have only two men and both have a car, the bot would induce that every man has a car. Clauses that are formulated this way should be used as supposition only.

All this needs to be tested. I don't guarantee that it works!

PRO|STAMINA [ programming game ]
AGI DEV LOG [ In Goto We Trust ]

ranch vermin

  • Not much time left.
  • *******
  • Starship Trooper
  • Posts: 386
  • Not much time.
Re: induction using Longest Common Subsequence
« Reply #1 on: September 18, 2015, 10:34:48 AM »
how can tsitest be a subsequence of those 2 sentences if it isnt actually in the sentences exactly? Looks good tho.
A bit from here, a bit from there, and bring it together and see the whole picture.

Zero

  • *
  • Autobot
  • ******
  • Posts: 201
  • Fictional character
    • AGI DEV LOG
Re: induction using Longest Common Subsequence
« Reply #2 on: September 18, 2015, 11:54:54 AM »
Because "tsitest" is a subsequence, not a substring. From wikipedia => It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Looks good? thanks!  :)

EDIT: What bothers me is this:

Quote
If B is missing, it should be here if we have both A and C.

Why? Because we take every sentence containing {1}?



Anyway, even if we don't go this far, I'll include some kind of a [get common from] command in my toy nonamed language. It will take a list of strings as input, and output a glob pattern showing similarities found in those strings, probably word by word.

Code: [Select]
  [test our new command]
  about: Paul is a parent of John. Paul is a man. Paul is the father of John.
  with: John is a parent of Miranda. John is a man. John is the father of Miranda.
  with: Miranda is a parent of Sofia. Miranda is a woman. Miranda is the mother of Sofia.
  with: Sofia is a parent of Chandler. Sofia is a woman. Sofia is the mother of Chandler.
  get common from: <this>
  print: <this>

output => "1" is a parent of "2". "1" is a "3". "1" is the "4" of "2".
« Last Edit: September 18, 2015, 12:50:50 PM by Zero »
PRO|STAMINA [ programming game ]
AGI DEV LOG [ In Goto We Trust ]

ranch vermin

  • Not much time left.
  • *******
  • Starship Trooper
  • Posts: 386
  • Not much time.
Re: induction using Longest Common Subsequence
« Reply #3 on: September 18, 2015, 12:25:27 PM »
when it comes to language, im for interchangable synonyms to increase interactivity past your average text chain assignment system,   quite similar to this and your other post.

my only issue is detecting them automatically.  as this one is no?
A bit from here, a bit from there, and bring it together and see the whole picture.

Zero

  • *
  • Autobot
  • ******
  • Posts: 201
  • Fictional character
    • AGI DEV LOG
Re: induction using Longest Common Subsequence
« Reply #4 on: September 18, 2015, 01:00:21 PM »
Yes. Problem is the step from the features you detect, to the conclusions you can build on them. This step needs to be worked on.
PRO|STAMINA [ programming game ]
AGI DEV LOG [ In Goto We Trust ]

 

Welcome

Please login or register.



Login with username, password and session length
Friday Funny
by kei10 (General Chat)
Today at 02:54:18 AM
mini a.i puzzles
by Freddy (General AI Discussion)
February 26, 2017, 09:01:05 PM
How to Predict Stock Prices Easily - Intro to Deep Learning #7 Siraj Raval
by keghn (General AI Discussion)
February 26, 2017, 04:21:26 PM
trivia questions
by yotamarker (General AI Discussion)
February 26, 2017, 03:05:54 PM
Life
by Art (AI in Film and Literature.)
February 26, 2017, 03:14:36 AM
Robot Message in a Bottle
by 8pla.net (Home Made Robots)
February 25, 2017, 04:04:21 AM
La-Masterpiece
by LOCKSUIT (Graphics)
February 24, 2017, 10:26:32 PM
Auto-Food-Drone type delivery
by Art (General Chat)
February 24, 2017, 06:52:28 PM
Robust bipedal Cassie to transform robot mobility
by Tyler (Robotics News)
February 24, 2017, 04:48:44 PM
Artificial intelligence: Understanding how machines learn
by Tyler (Robotics News)
February 24, 2017, 10:49:13 AM
Hard at work: A review of the Laevo Exoskeleton
by Tyler (Robotics News)
February 23, 2017, 04:48:12 PM
Shell Ocean Discovery XPRIZE: Semi-finalists set sail on a journey to illuminate the ocean
by Tyler (Robotics News)
February 22, 2017, 10:48:25 PM
Drones for good 2.0: How WeRobotics is redefining the use of unmanned systems in developing countries
by Tyler (Robotics News)
February 22, 2017, 04:48:07 PM
At what point should an intelligent machine be considered a person?
by Tyler (Robotics News)
February 22, 2017, 10:48:24 AM
Ocado evaluating robotic manipulation for online shopping orders
by Tyler (Robotics News)
February 21, 2017, 10:50:46 PM
Motor control systems: Bode plots and stability
by Tyler (Robotics News)
February 21, 2017, 04:48:52 PM

Users Online

18 Guests, 0 Users

Most Online Today: 33. Most Online Ever: 208 (August 27, 2008, 08:24:30 AM)

Articles