induction using Longest Common Subsequence

  • 4 Replies
  • 1247 Views
*

Zero

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 403
  • Fictional character
    • SYN CON DEV LOG
induction using Longest Common Subsequence
« on: September 18, 2015, 11:33: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!


*

ranch vermin

  • Not much time left.
  • Starship Trooper
  • *******
  • 410
  • Its nearly time!
Re: induction using Longest Common Subsequence
« Reply #1 on: September 18, 2015, 11:46:48 am »
how can tsitest be a subsequence of those 2 sentences if it isnt actually in the sentences exactly? Looks good tho.

*

Zero

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 403
  • Fictional character
    • SYN CON DEV LOG
Re: induction using Longest Common Subsequence
« Reply #2 on: September 18, 2015, 01:06:54 pm »
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, 02:02:50 pm by Zero »

*

ranch vermin

  • Not much time left.
  • Starship Trooper
  • *******
  • 410
  • Its nearly time!
Re: induction using Longest Common Subsequence
« Reply #3 on: September 18, 2015, 01:37: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?

*

Zero

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 403
  • Fictional character
    • SYN CON DEV LOG
Re: induction using Longest Common Subsequence
« Reply #4 on: September 18, 2015, 02:12: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.

 


Raspberry Pi 3 Software Environment
by keghn (AI Programming)
October 20, 2017, 11:24:56 pm
The Banach–Tarski Paradox
by Maviarab (General Chat)
October 20, 2017, 05:35:12 pm
2D or not 2D...
by Maviarab (Graphics)
October 20, 2017, 05:16:30 pm
FFmpeg - individual frames to video
by keghn (Graphics and Video Software)
October 20, 2017, 04:45:11 pm
Help creating a name for a fake PDA from the 80's
by Art (General Project Discussion)
October 20, 2017, 02:33:54 pm
Can you Handle a Mandel (brot)?
by ranch vermin (Graphics)
October 20, 2017, 02:12:16 pm
XKCD Comic : Cast Iron Pan
by Tyler (XKCD Comic)
October 20, 2017, 12:02:13 pm
home robots
by Freddy (New Users Please Post Here)
October 20, 2017, 03:10:00 am

Users Online

47 Guests, 0 Users

Most Online Today: 55. Most Online Ever: 208 (August 27, 2008, 09:36:30 am)

Articles