Към съдържанието
wannacode

Търсене по смисъл: най-близките k

Накратко: Търсенето по смисъл (semantic search) сравнява вектора на въпроса с векторите на текстовете и връща най-близките k по косинус, дори без обща дума.

Проблем

Един отговор не стига

Базата с отговори на поддръжката вече има шест текста:

// текст от базата с отговори: тема и текст
record Doc(String topic, String text) {}


// намерен текст и близостта му до въпроса
record Hit(Doc doc, double score) {}


// запис в индекса: текстът и векторът му
record Entry(Doc doc, int[] vector) {}


// базата с отговори на поддръжката
static final List<Doc> DOCS = List.of(
    new Doc("доставка", "доставката отнема до два дни"),
    new Doc("връщане", "върнете стоката до 14 дни и ще получите парите"),
    new Doc("плащане", "платете с карта или с наложен платеж"),
    new Doc("цена", "доставката до адрес струва 5 евро а до офис 3 евро"),
    new Doc("отказ", "ако банката откаже плащането опитайте с друга карта"),
    new Doc("гаранция", "гаранцията е две години от покупката"));


// въпросите на клиентите
static final String[] QUESTIONS = {
    "кога ще дойде пратката ми",
    "искам да върна стоката",
    "колко струва доставката до офис",
};

Ботът от урока за векторите прави всеки текст вектор и връща само най-близкия до въпроса:

Изход
кога ще дойде пратката ми → доставка: доставката отнема до два дни
искам да върна стоката → доставка: доставката отнема до два дни
колко струва доставката до офис → цена: доставката до адрес струва 5 евро а до офис 3 евро

Първият и третият въпрос са наред. Вторият клиент иска да върне стоката, а получава срока за доставка. Текстът за връщане не е далече: в урока за векторите той беше втори, с 0,635 срещу 0,842. Но ботът гледа само първия.

Идеята

Най-близките k

Търсенето не бива да залага всичко на един текст. Нека върне първите k: подредени от най-близкия, заедно с близостта.

Това е търсене по смисъл:

  1. Всеки текст от базата става вектор. Векторите се смятат веднъж и се пазят до текстовете. Това е индексът.
  2. Въпросът става вектор със същото пространство.
  3. Косинусът на въпроса до всеки запис в индекса.
  4. Подреждане от най-големия косинус и първите k.

Това са най-близките съседи от урока за k-NN. Там съседите бяха минали поръчки, а тук са текстове. Мярката е косинусът, не разстоянието.

Намерените k текста не са отговорът. Те отиват при езиковия модел, който ги чете и отговаря от тях. Това е следващата стъпка.

Виж го

Индексът

Векторите са от същото пространство като в урока за векторите: осемте най-чести думи в текста на магазина. Индексът е списък от записи: текстът и векторът му.

// индексът: векторът на всеки текст, сметнат веднъж
static List<Entry> buildIndex(Space space) {
    List<Entry> index = new ArrayList<>();
    for (Doc d : DOCS)
        index.add(new Entry(d, space.ofText(d.text())));
    return index;
}
Space space = new Space(TEXT, STOP, 8);
List<Entry> index = buildIndex(space);
for (Entry e : index)
    System.out.printf("%-10s%s%n", e.doc().topic(), Arrays.toString(e.vector()));
Изход
доставка  [2, 2, 3, 1, 4, 3, 2, 0]
връщане   [0, 6, 2, 1, 4, 3, 1, 0]
плащане   [0, 0, 0, 0, 0, 0, 0, 2]
цена      [7, 1, 12, 0, 1, 0, 0, 0]
отказ     [0, 0, 0, 0, 0, 0, 0, 6]
гаранция  [0, 0, 0, 0, 0, 0, 0, 0]

„плащане“ и „отказ“ имат само оста „карта“. „гаранция“ е само нули: думите ѝ ги няма в текста на магазина и малкият модел не знае за какво е. Към това ще се върнем в „Кога боли“.

Виж го

Първите k

Търсенето взима вектора на въпроса, смята косинуса до всеки запис, подрежда от най-близкия и връща първите k:

// първите k текста, най-близки до вектора на въпроса
static List<Hit> search(List<Entry> index, int[] v, int k) {
    List<Hit> hits = new ArrayList<>();
    for (Entry e : index)
        hits.add(new Hit(e.doc(), cosine(v, e.vector())));
    hits.sort(Comparator.comparing(Hit::score).reversed());
    return hits.subList(0, Math.min(k, hits.size()));
}
for (String q : QUESTIONS) {
    System.out.println(q);
    int[] v = space.ofText(q);
    for (Hit h : search(index, v, 3)) {
        String topic = h.doc().topic();
        System.out.printf("  %-10s%.3f%n", topic, h.score());
    }
}
Изход
кога ще дойде пратката ми
  доставка  0.655
  цена      0.439
  връщане   0.349
искам да върна стоката
  доставка  0.842
  връщане   0.635
  цена      0.537
колко струва доставката до офис
  цена      0.910
  доставка  0.646
  връщане   0.376

За връщането първият текст пак е „доставка“, но вторият е „връщане“. С k = 3 той е сред намерените. Ето същото на картинка. Векторите са в 8 измерения, затова картинката пази само колко далече е всеки текст от въпроса:

// първите k текста, най-близки до вектора на въпроса
static List<Hit> search(List<Entry> index, int[] v, int k) {
    List<Hit> hits = new ArrayList<>();
    for (Entry e : index)
        hits.add(new Hit(e.doc(), cosine(v, e.vector())));
    hits.sort(Comparator.comparing(Hit::score).reversed());
    return hits.subList(0, Math.min(k, hits.size()));
}


int[] v = space.ofText("искам да върна стоката");
for (Hit h : search(index, v, 3)) {
    String topic = h.doc().topic();
    System.out.printf("  %-10s%.3f%n", topic, h.score());
}
Стъпка по стъпка, с думи
  1. Въпросът „искам да върна стоката“ става вектор: [0, 0, 1, 0, 1, 1, 0, 0]. Той е точката в центъра.
  2. Косинусът до всеки запис в индекса. Колкото по-голям е косинусът, толкова по-близо е точката. Текст без обща ос е на външния кръг.
  3. Подредени от най-близкия: „доставка“, „връщане“, „цена“…
  4. k = 1: само „доставка“ (0,842). Клиентът иска да върне стоката, а получава срока за доставка.
  5. k = 2: „връщане“ (0,635) влиза. Правилният текст е сред намерените.
  6. k = 3: и „цена“ (0,537). Повече текстове: по-голям шанс правилният да е вътре, но и повече шум.
  7. Най-близките k = 3: „доставка“, „връщане“, „цена“. Правилният текст, „връщане“, е втори, затова търсенето връща k текста, а не един.

Пробвай

Предвиди изхода

Клиентът пише „искам друг цвят“. Нито една от думите не е в текста на магазина. Какво печата програмата?

int[] v = space.ofText("искам друг цвят");
for (Hit h : search(index, v, 3))
    System.out.printf("%s %.3f%n", h.doc().topic(), h.score());
Отговор

Пробвай

Попълни

Търсенето трябва да подреди от най-голямата близост към най-малката. Какво стои на мястото на ___?

// първите k текста, най-близки до вектора на въпроса
static List<Hit> search(List<Entry> index, int[] v, int k) {
    List<Hit> hits = new ArrayList<>();
    for (Entry e : index)
        hits.add(new Hit(e.doc(), cosine(v, e.vector())));
    hits.sort(Comparator.comparing(Hit::score).());
    return hits.subList(0, Math.min(k, hits.size()));
}

Пробвай

Намери грешката

Колега пише търсенето и за „искам да върна стоката“ получава „плащане“, „отказ“ и „гаранция“: все текстове с близост 0,000. На кой ред е грешката?

Избери реда с грешката.

Идеята

Колко да е k

С k = 1 ботът пропуска връщането. С k = 3 правилният текст е вътре, но идват и други: за „кога ще дойде пратката ми“ идват още „цена“ (0,439) и „връщане“ (0,349), които не отговарят на въпроса.

  • Малко k пропуска правилния текст, когато той не е пръв.
  • Голямо k носи шум. Всеки текст влиза в промпта: това са токени, които струват пари и място в прозореца на контекста. А моделът може да се хване за грешния текст.
  • Праг. Текст под определена близост не се връща изобщо. Така въпрос като „искам друг цвят“ не получава три случайни текста, а „не знам“.

Истинските системи обикновено взимат между 3 и 10 текста, но това е само пример. Колко точно, се мери с тестов набор от въпроси, за които знаеш правилния текст. Това е оценяването на търсенето.

Идеята

Кога боли

  • Точните неща. „къде е поръчка 10234“: номерът е непозната дума и векторът му е нули. Векторите хващат смисъл, а не точни низове. Номер на поръчка, код на продукт или имейл се търсят по равенство в базата. За имена и редки думи помага търсенето по думи, а истинските системи често смесват двете. Търсачките по думи са в урока за търсенето.
  • Думи, които моделът не знае. „гаранция“ е 0,000 до всеки въпрос и никога няма да бъде намерена. Истинският модел знае много повече думи, но същото става с вътрешния жаргон на фирмата и с нови имена на продукти.
  • Всеки въпрос минава през целия индекс. За шест текста това са шест косинуса. За милион текста с вектори от по 1024 числа са около милиард умножения на въпрос (примерно число). Затова векторните бази търсят приблизително: проверяват малка част от записите и почти винаги намират същите k. Те са в урока за векторните бази. Как се пуска и поддържа такава база, е работа за ZeroToOps.
  • Индексът остарява. Смениш ли текст, векторът му се смята наново. Смениш ли модела за вектори, се смята целият индекс: вектори от два модела не се сравняват помежду си.
  • Дълъг документ, един вектор. Векторът на цяла страница е смес от всичките ѝ теми. Как се реже документ на парчета, е в следващия урок.
По-точно, за любопитните

Истинските инструменти. Векторите идват от модел за вектори: вика се през API като другите модели или се пуска локално, най-често от Python. Пазят се във векторна база (например pgvector в PostgreSQL), която има индекс за приблизително търсене. На Python смятането с вектори обикновено е с NumPy. Практиката на ML е най-вече на Python, но търсенето се вика от всеки език: заявката към базата е същата. Тук всичко е на ръка, за да се вижда всяко число.

Подреждане на всичко или само на първите k. Подреждането на n записа е O(n log n). Ако k е малко, стига купчина с k елемента: всеки запис се сравнява с най-слабия в нея, и така са O(n log k) стъпки. Купчината е в урока за опашката с приоритет.

Равните близости. Подреждането на четирите езика е стабилно: равните остават в реда, в който са в базата. Затова „предвиди“ печата първите три текста. Не разчитай на това за смисъла: равни близости значат, че моделът не различава текстовете.

Разстоянието на картинката. Точката на всеки текст е на √(2 − 2·cos) от въпроса. Това е разстоянието между върховете на двата вектора, ако и двата са с дължина 1. Подредбата по него е същата като по косинуса.

Упражнение

Най-много k, но само близките

Реши в редактора си.

Напиши функция, която връща най-много k текста, но само тези с близост поне 0,5. Ако не остане нито един, тя връща „не знам, пращам на колега“. Пробвай я с k = 3 за „кога ще дойде пратката ми“, „искам да върна стоката“ и „искам друг цвят“.

Изход
кога ще дойде пратката ми: доставка 0.655
искам да върна стоката: доставка 0.842, връщане 0.635, цена 0.537
искам друг цвят: не знам, пращам на колега

Първият въпрос пази само „доставка“: „цена“ и „връщане“ са под прага. Вторият пази три текста, а третият не пази нищо и отива при човек.

Още задачи

  • Купчина вместо подреждане. Направи търсенето с купчина от k елемента. Изходът трябва да е същият.
  • Разлика между първия и втория. Отпечатай колко е разликата в близостта между първия и втория текст. Малка разлика значи, че търсенето не е сигурно.

Тест

Провери се

1. Защо търсенето връща k текста, а не само най-близкия?
2. Какво пази индексът?
3. Въпросът няма нито една дума, която моделът познава. Какво връща търсенето с k = 3?
4. Клиентът пише „къде е поръчка 10234“. Защо търсенето по смисъл не помага тук?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·