[Algoritme] text match *

[kingmuze]

Ik ben opzoek naar een een algoritme wat twee teksten bij elkaar zoekt. Bijvoorbeeld:

Heb het antwoord:
"Om Mozilla Firefox af te sluiten gebruikt u het kruisje rechtsbovenin de titelbalk"

En heb de vraag:
"Wat moet ik doen om Mozilla af te sluiten"
Of:
"Hoe sluit ik mijn firefox browser af"

Het zou mooi zijn als hij bij beide vragen hetzelfde antwoord krijgt. Je moet er van uit gaan dat iedere gebruiker een andere vraag intypt voor het zelfde antwoord. Nou heb ik al twee verschillende 'algoritmes' geprobeerd:
- Zoeken naar keywords binnen de vraag, die gelinkt zijn aan een antwoord
- Alle woorden in vragen/antwoorden bijhouden en met een soort Bayesian filtering bepalen welke woorden in een nieuwe vraag relevant zijn, om die vervolgens te matchen met de woorden in de database.

Q1: Hebben meer mensen ervaring met dergelijk probleem
Q2: Welke algoritmes zijn toegespitst op dergelijk probleem
Q3: Zijn hier goede whitepapers/pdfs/sites van? zoja waar
Q4: Welke algoritmes bestaan er om bijvoorbeeld de context van een vraag te bepalen

Thanks.

[simon]

Zoiets lijkt me redelijk taal afhankelijk, met de ene taal zijn er al functies voor, verder zou je woord voor woord kunnen vergelijken. Ik denk dat er ook op google veel over te vinden is

[bigbeng]

Ze hebben er zelfs hele opleidingen voor. Zo is er bijvoorbeeld Taal en Informatica dat je kunt studeren aan de UvT (voorheen KUB). Dit gaat helemaal in op de beginselen van semantiek en computers. En dus ook over hoe je een computer context kunt laten bepalen.

Lijkt me dus een iets te ingewikkeld onderwerp om in een topicje te behandelen.

Een aantal problemen die ik zo even kan bedenken:
• Gebruik van synoniemen
• Zelfde woorden met verschillende betekenis
• Grammatica regels op eenduidige wijze aan de computer leren

[Verwijderd]

Mjah, meest eenvoudige aanpak zo snel lijkt me gewoon per woord in de vraag kijken of het woord ook in het antwoord voorkomt en zo ja de relevantie verhogen. (Bijvoorbeeld een int relevantie en per hit met 1 verhogen) Daarna op volgorde van relevantie de antwoorden opleveren?

[kingmuze]

Inderdaad is het een ingewikkeld onderwerp. Bovenstaande punten zijn eigenlijk ook terug te vinden in de 2 punten die ik al heb geprobeerd. Heel veel gegoogled kom je wel vaak uit op bayesian. Maar er moeten toch meerdere algoritmes zijn die soortgelijk zijn.

[NMe]

Ik zou het houden op de keyword manier, en daarmee de antwoorden sorteren op relevantie. Ik neem aan dat je dit gebruikt voor een soort van help file voor je applicatie? Lijkt me niet de moeite om daar zoveel aandacht aan te schenken. Normaal gesproken wordt toch al van users verwacht dat ze gewoon zelf een vraag formuleren d.m.v. keywords, dus als jij überhaupt al keywords selecteert uit een vraag, dan ben je al aardig op weg.

[kingmuze]

Het is de bedoeling dat binnenkomende email wordt geanalyseerd volgens een algoritme en daarna automatisch een antwoord bij gezocht kan worden. Het werkt beneden de maat met keywords omdat je dan echt specifiek zoekt naar bepaalde keywords en de vragen hier ook duidelijk naar moet vragen. Zodra de vraag groter wordt dan 2 zinnen oid krijg je bijna altijd een foutief antwoord.

[Gomez12]

edit:
onzin na uitleg van kingmuze

Maar kunnen mensen per e-mail een vraag stellen en wil je dan dat er 1 antwoord retour gaat ??? Of mag het net zoals ns-reisinfo zijn dat je eerst een vraag mag opsturen en dat het systeem dan een wedervraag teruggeeft als het niet tot 1 antwoord komt.

En wat is de grootte van het systeem??? Hoeveel antwoorden staan er zo ongeveer in.

[ Voor 78% gewijzigd door Gomez12 op 06-09-2004 19:22 ]

[veer0318]

Je moet zoeken op kernwoorden. Die krijg je door woorden als 'en', 'de', 'ik', enz. eruit te filteren. Dan heb je een paar kernwoorden, die match je via een FULLTEXT, en dan neem je het hoogste resultaat.

Dit is natuurlijk niet een perfecte oplossing, maar werkt redelijk (uit ervaring).

[kingmuze]

Gomez12 schreef op 06 september 2004 @ 19:19:

edit:
onzin na uitleg van kingmuze

Maar kunnen mensen per e-mail een vraag stellen en wil je dan dat er 1 antwoord retour gaat ??? Of mag het net zoals ns-reisinfo zijn dat je eerst een vraag mag opsturen en dat het systeem dan een wedervraag teruggeeft als het niet tot 1 antwoord komt.

En wat is de grootte van het systeem??? Hoeveel antwoorden staan er zo ongeveer in.

In het systeem kunnen wel 1000 antwoorden of meer komen te staan en het idee is als volgt:
Een klant doet een support aanvraag. De supportmedewerker leest deze. Het systeem zoekt automatisch een gematched antwoord. Support medewerker controlleert deze, is het een goede match, klik op verzenden. Zoniet dan maakt de supportmedewerke een eigen antwoord en voegt deze toe aan het systeem,

[kingmuze]

veer0318 schreef op 06 september 2004 @ 19:20:
Je moet zoeken op kernwoorden. Die krijg je door woorden als 'en', 'de', 'ik', enz. eruit te filteren. Dan heb je een paar kernwoorden, die match je via een FULLTEXT, en dan neem je het hoogste resultaat.

Dit is natuurlijk niet een perfecte oplossing, maar werkt redelijk (uit ervaring).

Dat idee heb ik al uitgewerkt, met behulp van 'keywords' wordt er gekeken welk antwoord hierbij hoort (de vraag heeft bepaalde keywords aan zich gelinkt waarop gematched wordt). Echter zodra de klant andere woorden gebruikt komt er vaak een verkeerde match uit.

[veer0318]

Hmm, wat je dan zou moeten doen is een synoniemenlijst in een database pleuren, en tegen elk van de synoniemen te matchen . Is tergend langzaam, als je 't al voor elkaar krijgt zo'n lijst te krijgen...

[kingmuze]

veer0318 schreef op 06 september 2004 @ 21:55:
Hmm, wat je dan zou moeten doen is een synoniemenlijst in een database pleuren, en tegen elk van de synoniemen te matchen . Is tergend langzaam, als je 't al voor elkaar krijgt zo'n lijst te krijgen...

Inderdaad, het zou heel mooi zijn als het een soort van lerend idee krijgt. Elke keer als er een nieuw antwoord in het systeem komt leert hij weer iets bij over een synoniem, link tussen vraag en antwoord oid.

Zijn hier geen goede docs op internet over? Heb zelf nog nix echt goeds gevonden.

[veer0318]

Hmm... synoniemenlijsten zijn vast te koop (www.vandale.nl), maar zullen niet goedkoop zijn... Wellicht dat er gratis zijn, doch ik betwijfel de haalbaarheid van dit systeem... Ik denk dat een handmatig opgezette trefwoordenlijst efficienter werkt dan een willekeurige synoniemenlijst... Is wel (veel) meer werk, maar je hebt ook wat. Mag ik vragen wat voor helpdesk het is? Bij een helpdesk die écht veel te verwerken krijgt kan dit inderdaad een goede oplossing zijn, doch bij een helpdesk "die af en toe" en belletje krijgt, nah, denk 't niet dat dit de oplossing is...

[NMe]

kingmuze schreef op 06 september 2004 @ 22:01:
Inderdaad, het zou heel mooi zijn als het een soort van lerend idee krijgt. Elke keer als er een nieuw antwoord in het systeem komt leert hij weer iets bij over een synoniem, link tussen vraag en antwoord oid.

Hoe had je dat in gedachten dan? Als het geen keyword is, dan levert hij mogelijk verkeerde antwoorden, dus als een gebruiker na het zoeken op een onbestaand keyword op een resultaat klikt, dan hoeft dat totaal niet bij dat woord te passen. Dus hoe wou je dat registreren?

[kingmuze]

veer0318 schreef op 06 september 2004 @ 22:11:
Hmm... synoniemenlijsten zijn vast te koop (www.vandale.nl), maar zullen niet goedkoop zijn... Wellicht dat er gratis zijn, doch ik betwijfel de haalbaarheid van dit systeem... Ik denk dat een handmatig opgezette trefwoordenlijst efficienter werkt dan een willekeurige synoniemenlijst... Is wel (veel) meer werk, maar je hebt ook wat. Mag ik vragen wat voor helpdesk het is? Bij een helpdesk die écht veel te verwerken krijgt kan dit inderdaad een goede oplossing zijn, doch bij een helpdesk "die af en toe" en belletje krijgt, nah, denk 't niet dat dit de oplossing is...

Op dit moment komen er zon 100 mails per dag binnen waarmee 1 medewerker 1 complete dag mee bezig is. Het zou heel mooi zijn dat dit een stuk sneller afgehandeld kan worden waardoor de support medewerker (die ook goed is in andere geld opleverende zaken) ook andere zaken kan doen.

[kingmuze]

NMe84 schreef op 06 september 2004 @ 22:13:
[...]

Hoe had je dat in gedachten dan? Als het geen keyword is, dan levert hij mogelijk verkeerde antwoorden, dus als een gebruiker na het zoeken op een onbestaand keyword op een resultaat klikt, dan hoeft dat totaal niet bij dat woord te passen. Dus hoe wou je dat registreren?

Bij mijn tweede tryout heb ik het Bayesian filter toegepast. Elke keer als een woord voorkomt wordt het woord minder waard. Bijvoorbeeld neem de volgende 3 vragen:

"Hoe hard is de voorkant van een trein?"
"Wanneer is het tijd om goede tijden slechte tijden te kijken?"
"Is het krijgen van een slechte conditie is een van de gevolgen van niet sporten?"

de woorden is, een, de, het van, enzovoorts zijn woorden die vaak voorkomen. Dit registreerd het systeem en daarom krijgen deze woorden weinig waarde. Woorden waar het dan echt om draaid en dus redelijk uniek zijn in een vraag zoals trein, goede tijden slechte tijden en sporten en conditie kan dan gematched worden.

Dit systeem werkt goed als er niet te veel vragen over 1 onderwerp in het systeem zitten, doch wanneer je veel antwoorden over het zelfde onderwerp in het systeem zet krijg je al snel niet het goede antwoord.

[Sendy]

Ik zou zeggen dat als er zoveel supportvragen binnen komen, je misschien een dedicated klikkip (want je moet 100x per dag 'Verzenden' klikken) moet inhuren en die goeie 'geld opleverende' medewerker iets anders laten doen?

edit:
Sorry voor het niet zo techische antwoord

[ Voor 17% gewijzigd door Sendy op 06-09-2004 22:38 ]

[kingmuze]

Sendy schreef op 06 september 2004 @ 22:38:
Ik zou zeggen dat als er zoveel supportvragen binnen komen, je misschien een dedicated klikkip (want je moet 100x per dag 'Verzenden' klikken) moet inhuren en die goeie 'geld opleverende' medewerker iets anders laten doen?

edit:
Sorry voor het niet zo techische antwoord

dat is inderdaad oplossing 1.
Alleen: 100 x verzenden kost geen 8 uur :-) (de medewerker doet er nu wel 2a3 dagen over geloof ik).
Een extra werknemer is weer extra 1500 euro oid in de maand. Terwijl dit systeem een stuk goedkoper is op termijn.

[Hielko]

Ik denk dat een niet zo'n technisch antwoord wel het beste is.

Wat jij wilt is ongetwijfeld mogelijk. Het is echter dermate complex dat je beter 1 persoon gewoon fulltime helpdesk kan laten spelen dan een software oplossing proberen te maken.

Overigens denk ik dat je met neurale netwerken en aanverwante technieken wel wat leuks kan doen om dit probleem deels op te lossen.

[Verwijderd]

Wat jij wilt is echt retecomplex, het bedrijf www.q-go.com heeft zich in dergelijke toepassingen gemengd. Daar zit echt hele complexe logica achter.

[Verwijderd]

Ik zelf werk met kunstmatige intelligentie programma's als mijn zelfgeknutselde eliza.

Eliza werkt een beetje met alle technieken die ik net al genoemd zag, maar dat in mindering brengen van woorden is iets echt leuks vind ik. Ik ging vooral uit van een database met kernwoorden die eliza verleiden een uitspraak te doen.



Voor onder win xp, voor de C++ programmeur zit de source code erbij.

Achter de prompt moet je eliza.prg intypen, dat is een voorgecompileerde binairty in de directory /bin.

De root is / en je home is /home

Het lijkt iets op linux.

If you are not a programmer, it is not necessary to understand the data and code below...

void OpenFile()
{
// the 1 extra line to port your code to winfs(ufs)...
char translatedfilename[MAX_PATH]={0};GetDirectPathTranslation("/home/file.txt",translatedfilename,MAX_PATH-1);
// the normal shit in C++
FILE* f=fopen(translatedfilename,"rt");
if(!f)
return;

char data[16384];
fread(data,sizeof(char),16384,f);
fclose(f);
}

[H!GHGuY]

als je nu eens niet vertrekt vanaf de vragen/antwoorden, maar vanaf de zoekzin:

stel je krijgt:
"Wat moet ik doen om Mozilla af te sluiten"
kan je door zoals hierboven gezegd, enkele woorden al in mindering brengen.

blijven over: mozilla sluiten

daaruit wordt in een database opgezocht aan welke artikels mozilla gelinkt is, en aan welke artikels sluiten gelinkt is. daarmee doe je een soort van vermenigvuldiging zodat de relevantste artikels eerst komen.

eventueel kun je binnen 1 kernwoord dieper gaan linken, en bvb bij mozilla ook linken naar kernwoord 'sluiten' 'openen' 'startpagina' en bijhorende relevante artikels.

uiteindelijk kun je zelfs zover gaan dat je per woord / combinatie woorden een set artikels krijgt die door vaker te gebruiken (de helpdesk medewerker linkt immers sluiten, mozilla aan 'hoe sluit ik mozilla af' met hoge relevantie)

[kingmuze]

Hielko schreef op 06 september 2004 @ 22:47:
Ik denk dat een niet zo'n technisch antwoord wel het beste is.

Wat jij wilt is ongetwijfeld mogelijk. Het is echter dermate complex dat je beter 1 persoon gewoon fulltime helpdesk kan laten spelen dan een software oplossing proberen te maken.

Overigens denk ik dat je met neurale netwerken en aanverwante technieken wel wat leuks kan doen om dit probleem deels op te lossen.

[Gomez12]

En als je nou ipv 1 artikel de medewerker gewoon 20 relevante artikelen teruggeeft op een html pagina met daarnaast allemaal send-knopjes. Dan kiest de medewerker het goede antwoord en verstuurt dit naar de klant. En dan gelijk nog even het betreffende antwoord hoger waarderen aan de hand van de opgegeven keywoorden.

En als je de medewerker zelf ook nog de mogelijkheid biedt om een vraag te herschrijven ( denk aan : hoe moet ik IE sluiten??? herschrijven naar : hoe moet ik Internet Explorer sluiten ??? ) dan creeer je zelf een synoniemenlijst, je trefkans wordt groter.

Plus als het een in-house systeem is dan zou ik ervoor kiezen om gelijk de keywords ook naar de klant terug te sturen zodat hij weet waarop gezocht is.

Of kijk eens hoeveel google answers kost per vraag

[kingmuze]

Gomez12 schreef op 07 september 2004 @ 10:01:
En als je nou ipv 1 artikel de medewerker gewoon 20 relevante artikelen teruggeeft op een html pagina met daarnaast allemaal send-knopjes. Dan kiest de medewerker het goede antwoord en verstuurt dit naar de klant. En dan gelijk nog even het betreffende antwoord hoger waarderen aan de hand van de opgegeven keywoorden.

Dat is opzich een idee, alleen wanneer de medewerker 20 antwoorden moet doorlezen duurd het veel te lang. Dan kan de gebruiker bijna net zo goed zelf een antwoord opstellen en verzenden.

En als je de medewerker zelf ook nog de mogelijkheid biedt om een vraag te herschrijven ( denk aan : hoe moet ik IE sluiten??? herschrijven naar : hoe moet ik Internet Explorer sluiten ??? ) dan creeer je zelf een synoniemenlijst, je trefkans wordt groter.

Dat is inderdaad wel een goed idee om meerdere vragen voor een antwoord te gebruiken en eventueel ook op te slaan.

Plus als het een in-house systeem is dan zou ik ervoor kiezen om gelijk de keywords ook naar de klant terug te sturen zodat hij weet waarop gezocht is.

Of kijk eens hoeveel google answers kost per vraag

lol :-) maar de klant moet natuurlijk wel een idee krijgen dat ie met een medewerker mailed ipv automatisch verstuurde antwoorden. Daarom wordt ieder automatisch antwoord ook nog bevestigd door een medewerker.

[Verwijderd]

Ik ben ook met iets dergelijks bezig. Waar ik aan zat te denken, was om een bericht eerst op te delen in zinnen. Je kan dan per zin het onderwerp bepalen zoals jij dat ook al deed voor een hele email (door op de meest specifieke woorden te letten). Je zou dan antwoorden kunnen filteren op die onderwerpen, beginnend bij de meest specifieke zin, of iets in die richting.

Ik ben er alleen nog niet aan toe gekomen om dit uit te proberen. Heeft iemand hier misschien ervaring mee?

[kingmuze]

Verwijderd schreef op 07 september 2004 @ 10:12:
Ik ben ook met iets dergelijks bezig. Waar ik aan zat te denken, was om een bericht eerst op te delen in zinnen. Je kan dan per zin het onderwerp bepalen zoals jij dat ook al deed voor een hele email (door op de meest specifieke woorden te letten). Je zou dan antwoorden kunnen filteren op die onderwerpen, beginnend bij de meest specifieke zin, of iets in die richting.

Ik ben er alleen nog niet aan toe gekomen om dit uit te proberen. Heeft iemand hier misschien ervaring mee?

Ey Frixus, klinkt flex. Zou inderdaad mooi zijn als er meer mensen informatie over hebben.

Heb jij nog meer informatie over dit onderwerp? Links oid?

[Verwijderd]

Ik heb hier wel wat, maar 't is nog niet helemaal wat ik precies nodig heb. Link naar informatie over Bayesian filtering en spam filters: [link]http://www.paulgraham.com/better.html[/link].

Op zich is het idee daarvan wel goed, maar dan moet je er wel complexere keuzes mee kunnen maken. Wat ik bedoel: voor spam filtering heb je alleen de keuze spam of niet. Ik moet eigenlijk iets hebben wat kan kiezen: welke van deze 100en berichten?

[kingmuze]

Verwijderd schreef op 06 september 2004 @ 22:50:
Ik zelf werk met kunstmatige intelligentie programma's als mijn zelfgeknutselde eliza.

Eliza werkt een beetje met alle technieken die ik net al genoemd zag, maar dat in mindering brengen van woorden is iets echt leuks vind ik. Ik ging vooral uit van een database met kernwoorden die eliza verleiden een uitspraak te doen.

[afbeelding]

Voor onder win xp, voor de C++ programmeur zit de source code erbij.

Achter de prompt moet je eliza.prg intypen, dat is een voorgecompileerde binairty in de directory /bin.

De root is / en je home is /home

Het lijkt iets op linux.

If you are not a programmer, it is not necessary to understand the data and code below...

void OpenFile()
{
// the 1 extra line to port your code to winfs(ufs)...
char translatedfilename[MAX_PATH]={0};GetDirectPathTranslation("/home/file.txt",translatedfilename,MAX_PATH-1);
// the normal shit in C++
FILE* f=fopen(translatedfilename,"rt");
if(!f)
return;

char data[16384];
fread(data,sizeof(char),16384,f);
fclose(f);
}

[afbeelding]

Vet die zelfgemaakte AI bot Heb je ook ergens de source code staan (al dan niet gecompileerd voor windows) zodat we hem kunnen proberen. Waar heb je de theorie vandaan gehaald om tot de AI te komen? Hebje er links voor?

[dotcode]

Voor zoeken onder IIS wordt volgens mij gewoon de std indexing service gebruikt, als je nou een synoniemen lijst gebruikte en die als meta data opneemt in je file kan je van afdan ook zoeken op je de synoniemen.

stappen:
- maak synoniemen lijst
- maak content
- haal content door script om synoniemen aan meta data toe te voegen
- indexeer de zoek content

Nu zoek ook naar de synoniemen. Dit is natuurlijk niet zo mooi als een ai service, maar waarschijnlijk makelijker te implementeren