У завданнях машинного навчання з оцінки якості моделей і порівняння різних алгоритмів використовуються метрики, які вибір і аналіз - неодмінна частина роботи датасатаніста.

У цій статті ми розглянемо деякі критерії якості в задачах класифікації, обговоримо, що є важливим при виборі метрики і може піти не так.

Метрики у завданнях класифікації

Для демонстрації корисних функцій sklearnі наочної вистави метрик ми будемо використовувати наш датасет по відтоку клієнтів телеком-оператора, з яким ми познайомилися в першій статті курсу.

Завантажимо необхідні бібліотеки та подивимося на дані

Import pandas як pd import matplotlib.pyplot як plot з matplotlib.pylab import rc, plot import seaborn як sns від sklearn. from sklearn.metrics import precision_recall_curve, classification_report from sklearn.model_selection import train_test_split df = pd.read_csv("../../data/telecom_churn.csv")

Df.head(5)

Передобробка даних

# Зробимо мапінг бінарних колонок # і закодуємо dummy-кодуванням штат (для простоти, краще не робити так для дерев'яних моделей) d = ("Yes": 1, "No": 0) df["International plan"] = df[" International plan"].map(d) df["Voice mail plan"] = df["Voice mail plan"].map(d) df["Churn"] = df["Churn"].astype("int64" ) le = LabelEncoder() df["State"] = le.fit_transform(df["State"]) ohe = OneHotEncoder(sparse=False) encoded_state = ohe.fit_transform(df["State"].values.reshape(- 1, 1)) tmp = pd.

Accuracy, precision та recall

Перед переходом до самих метриків необхідно запровадити важливу концепцію для опису цих метрик у термінах помилок класифікації. confusion matrix(матриця помилок).
Припустимо, що у нас є два класи і алгоритм, що передбачає належність кожного об'єкта одному з класів, тоді матриця помилок класифікації буде виглядати наступним чином:

	True Positive (TP)	False Positive (FP)
	False Negative (FN)	True Negative (TN)

Тут – це відповідь алгоритму на об'єкті, а – справжня мітка класу на цьому об'єкті.
Таким чином, помилки класифікації бувають двох видів: False Negative (FN) та False Positive (FP).

Навчання алгоритму та побудова матриці помилок

X = df.drop("Churn", axis=1) y = df["Churn"] # Ділимо вибірку на train і test, всі метрики оцінюватимемо на тестовій датасеті X_train, X_test, y_train, y_test = train_test_split(X, y , stratify=y, test_size=0.33, random_state=42) # Навчаємо рідну логістичну регресію lr = LogisticRegression(random_state=42) lr.fit(X_train, y_train) # Скористаємося функцією побудови матриці , normalize=False, title="(!LANG:Confusion matrix", cmap=plt.cm.Blues): """ This function prints and plots the confusion matrix. Normalization can be applied by setting `normalize=True`. """ plt.imshow(cm, interpolation="nearest", cmap=cmap) plt.title(title) plt.colorbar() tick_marks = np.arange(len(classes)) plt.xticks(tick_marks, classes, rotation=45) plt.yticks(tick_marks, classes) if normalize: cm = cm.astype("float") / cm.sum(axis=1)[:, np.newaxis] print("Normalized confusion matrix") else: print("Confusion matrix, without normalization") print(cm) thresh = cm.max() / 2. for i, j in itertools.product(range(cm.shape), range(cm.shape)): plt.text(j, i, cm, horizontalalignment="center", color="white" if cm > thresh else "black") plt.tight_layout() plt.ylabel("True label") plt.xlabel("Predicted label") font = {"size" : 15} plt.rc("font", **font) cnf_matrix = confusion_matrix(y_test, lr.predict(X_test)) plt.figure(figsize=(10, 8)) plot_confusion_matrix(cnf_matrix, classes=["Non-churned", "Churned"], title="Confusion matrix") plt.savefig("conf_matrix.png") plt.show()!}

Accuracy

Інтуїтивно зрозумілою, очевидною та майже невикористовуваною метрикою є accuracy – частка правильних відповідей алгоритму:

Ця метрика марна у завданнях з нерівними класами і це легко показати на прикладі.

Допустимо, ми хочемо оцінити роботу спам-фільтру пошти. У нас є 100 не-спам листів, 90 з яких наш класифікатор визначив правильно (True Negative = 90, False Positive = 10) та 10 спам-листів, 5 з яких класифікатор також визначив правильно (True Positive = 5, False Negative = 5 ).
Тоді accuracy:

Однак якщо ми просто будемо пророкувати всі листи як не-спам, то отримаємо більш високу accuracy:

При цьому, наша модель абсолютно не має жодної передбачувальної сили, тому що ми спочатку ми хотіли визначати листи зі спамом. Подолати це нам допоможе перехід із загальною для всіх класів метрики до окремих показників якості класів.

Precision, recall та F-мера

Для оцінки якості роботи алгоритму кожному з класів окремо введемо метрики precision (точність) і recall (повнота).

Precision можна інтерпретувати як частку об'єктів, названих класифікатором позитивними і при цьому дійсно позитивними, а recall показує, яку частку об'єктів позитивного класу з усіх об'єктів позитивного класу знайшов алгоритм.

Саме введення precision не дозволяє нам записувати всі об'єкти в один клас, тому що в цьому випадку ми отримуємо зростання рівня False Positive. Recall демонструє здатність алгоритму виявляти цей клас взагалі, а precision – здатність відрізняти цей клас від інших класів.

Як ми зазначали раніше, помилки класифікації бувають двох видів: False Positive та False Negative. У статистиці перший вид помилок називають помилкою І-го роду, а другий - помилкою ІІ-го роду. У нашій задачі визначення відпливу абонентів, помилкою першого роду буде прийняття лояльного абонента за того, хто йде, оскільки наша нульова гіпотеза полягає в тому, що ніхто з абонентів не йде, а ми цю гіпотезу відкидаємо. Відповідно, помилкою другого роду буде "перепустка" абонента, що йде, і помилкове прийняття нульової гіпотези.

Precision і recall не залежать, на відміну accuracy, від співвідношення класів і тому застосовні за умов незбалансованих вибірок.
Часто у реальній практиці стоїть завдання знайти оптимальний (для замовника) баланс між цими двома метриками. Класичним прикладом є завдання визначення відпливу клієнтів.
Очевидно, що ми не можемо шукати всіхклієнтів, що йдуть у відтік і тількиїх. Але визначивши стратегію та ресурс для утримання клієнтів, ми можемо підібрати потрібні пороги по precision та recall. Наприклад, можна зосередитися на утриманні тільки високоприбуткових клієнтів або тих, хто піде з більшою ймовірністю, оскільки ми обмежені ресурсами колл-центру.

Зазвичай, при оптимізації гіперпараметрів алгоритму (наприклад, у разі перебору по сітці GridSearchCV) використовується одна метрика, поліпшення якої ми очікуємо побачити на тестовій вибірці.
Існує кілька різних способів об'єднати precision і recall в агрегований критерій якості. F-мера (загалом ) - середнє гармонічне precision і recall:

В даному випадку визначає вагу точності в метриці, і при цьому середнє гармонічне (з множником 2, щоб у разі precision = 1 і recall = 1 мати )
F-мера досягає максимуму при повноті і точності, що дорівнює одиниці, і близька до нуля, якщо один з аргументів близький до нуля.
У sklearn є зручна функція _metrics.classification reportповертає recall, precision та F-заходу для кожного з класів, а також кількість екземплярів кожного класу.

Report = classification_report(y_test, lr.predict(X_test), target_names=["Non-churned", "Churned"]) print(report)

class	precision	recall	f1-score	support
Non-churned	0.88	0.97	0.93	941
Churned	0.60	0.25	0.35	159
avg/total	0.84	0.87	0.84	1100

Тут слід зазначити, що у разі завдань із незбалансованими класами, які превалюють у реальній практиці, часто доводиться вдаватися до технік штучної модифікації датасету для вирівнювання співвідношення класів. Їх існує багато і ми не будемо їх торкатися, можна подивитися деякі методи та вибрати відповідний для вашого завдання.

AUC-ROC та AUC-PR

При конвертації речового відповіді алгоритму (як правило, ймовірності приналежності до класу, окремо див. SVM) в бінарну мітку, ми повинні вибрати будь-який поріг, при якому 0 стає 1. Природним і близьким здається поріг, рівний 0.5, але він не завжди виявляється оптимальним, наприклад, при вищезгаданому відсутності балансу класів.

Одним із способів оцінити модель в цілому, не прив'язуючись до конкретного порогу, є AUC-ROC (або ROC AUC) – площа ( A rea U nder C urve) під кривою помилок ( R eceiver O perating C haracteristic curve). Дана крива являє собою лінію від (0,0) до (1,1) в координатах True Positive Rate (TPR) та False Positive Rate (FPR):

TPR нам вже відома, це повнота, а FPR показує, яку частку з об'єктів negative класу алгоритм передбачив неправильно. В ідеальному випадку, коли класифікатор не робить помилок (FPR = 0, TPR = 1) ми отримаємо площу під кривою, що дорівнює одиниці; в іншому випадку, коли класифікатор випадково видає ймовірності класів, AUC-ROC буде прагнути до 0.5, оскільки класифікатор видаватиме однакову кількість TP та FP.
Кожна точка на графіку відповідає вибору деякого порога. Площа під кривою в даному випадку показує якість алгоритму (більше – краще), крім цього, важливою є крутість самої кривої – ми хочемо максимізувати TPR, мінімізуючи FPR, а значить, наша крива в ідеалі має прагнути точки (0,1).

Код відображення ROC-кривий

Sns.set(font_scale=1.5) sns.set_color_codes("muted") plt.figure(figsize=(10, 8)) fpr, tpr, thresholds = roc_curve(y_test, lr.predict_proba(X_test)[:,1], pos_label=1) lw = 2 plt.plot(fpr, tpr, lw=lw, label="ROC curve") plt.plot(, ) plt.xlim() plt.ylim() plt.xlabel("False Positive Rate ") plt.ylabel("True Positive Rate") plt.title("ROC curve") plt.savefig("ROC.png") plt.show()

Критерій AUC-ROC стійкий до незбалансованих класів (спойлер: на жаль, не все так однозначно) і може бути інтерпретований як ймовірність того, що випадково обраний positive об'єкт буде проранжований класифікатором вище (матиме більш високу ймовірність бути positive), ніж випадково обраний negative об'єкт .

Розглянемо таку задачу: нам необхідно вибрати 100 релевантних документів із 1 мільйона документів. Ми намашинлернили два алгоритми:

• Алгоритм 1повертає 100 документів, 90 з яких є релевантними. Таким чином,

• Алгоритм 2повертає 2000 документів, 90 з яких є релевантними. Таким чином,

Швидше за все, ми вибрали б перший алгоритм, який видає дуже мало False Positive на тлі свого конкурента. Але різниця у False Positive Rate між цими двома алгоритмами кончемала – всього 0.0019. Це є наслідком того, що AUC-ROC вимірює частку False Positive щодо True Negative і в завданнях, де нам не такий важливий другий (більший) клас, може давати не зовсім адекватну картину при порівнянні алгоритмів.

Для того, щоб поправити положення, повернемося до повноти та точності:

• Алгоритм 1

• Алгоритм 2

Тут вже помітна суттєва різниця між двома алгоритмами – 0.855 в точності!

Precision і recall також використовують для побудови кривої та, аналогічно AUC-ROC, знаходять площу під нею.

Тут можна відзначити, що на маленьких датасетах площа під PR-кривою може бути надто оптимістичною, тому що обчислюється за методом трапецій, але зазвичай у таких завданнях даних достатньо. За подробицями про взаємини AUC-ROC та AUC-PR можна звернутися сюди.

Logistic Loss

Окремо стоїть логістична функція втрат, яка визначається як:

тут це відповідь алгоритму на об'єкті, справжня мітка класу на об'єкті, а розмір вибірки.

Докладно про математичну інтерпретацію логістичної функції втрат вже написано в рамках поста про лінійні моделі.
Дана метрика нечасто виступає у бізнес-вимогах, але часто – у завданнях на kaggle.
Інтуїтивно можна уявити мінімізацію logloss як завдання максимізації accuracy шляхом штрафу за невірні передбачення. Однак необхідно зазначити, що logloss дуже штрафує за впевненість класифікатора в невірній відповіді.

Розглянемо приклад:

Def logloss_crutch(y_true, y_pred, eps=1e-15): return - (y_true * np.log(y_pred) + (1 - y_true) * np.log(1 - y_pred)) print("Logloss при невпевненій класифікації %f " % logloss_crutch(1, 0.5)) >> Logloss при невпевненій класифікації 0.693147 print("Logloss при впевненій класифікації та вірній відповіді %f" % logloss_crutch(1, 0.9)) >> Logloss при впевненій класифікації та вірній відповіді"3 0 1 Logloss при впевненій класифікації та неправильній відповіді %f" % logloss_crutch(1, 0.1)) >> Logloss при впевненій класифікації та неправильній відповіді 2.302585

Зазначимо, як драматично виросла logloss при невірній відповіді та впевненій класифікації!
Отже, помилка одному об'єкті може дати істотне погіршення загальної помилки на вибірці. Такі об'єкти часто бувають викидами, які слід не забувати фільтрувати чи розглядати окремо.
Все стає на свої місця, якщо намалювати графік logloss:

Видно, що чим ближче до нуля відповідь алгоритму при ground truth = 1, тим вище значення помилки і крутіше росте крива.

Підсумуємо:

• У разі багатокласової класифікації потрібно уважно стежити за метриками кожного з класів та дотримуватися логіки рішення завдання, а не оптимізації метрики
• У разі нерівних класів потрібно підбирати баланс класів для навчання та метрику, яка коректно відображатиме якість класифікації
mephistopheies і madrugado за допомогу у підготовці статті.

У процесі підготовки завдання для вступного випробування на літню школу GoTo ми виявили, що російською мовою практично відсутній якісний опис основних метрик ранжирування (завдання стосувалося окремого випадку задачі ранжування - побудови рекомендаційного алгоритму). Ми в E-Contenta активно використовуємо різні метрики ранжирування, тому вирішили виправити це більш непорозуміння, написавши цю статтю.

Завдання ранжирування зараз виникає всюди: сортування веб-сторінок згідно з заданим пошуковим запитом, персоналізація стрічки новин, рекомендації відео, товарів, музики… Одним словом, тема гаряча. Є навіть спеціальний напрямок у машинному навчанні, яке займається вивченням алгоритмів ранжирування, здатних самонавчатись - навчання ранжування (learning to rank). Щоб вибрати з усього різноманіття алгоритмів та підходів найкращий, необхідно вміти оцінювати їхню якість кількісно. Про найпоширеніші метрики якості ранжування і йтиметься далі.

Коротко про завдання ранжирування

Ранжування – завдання сортування набору елементівз міркувань їх релевантності. Найчастіше релевантність розуміється стосовно когось об'єкту. Наприклад, в задачі інформаційного пошуку об'єкт - це запит, елементи - всілякі документи (посилання на них), а релевантність - відповідність документа запиту, в задачі рекомендацій об'єкт - це користувач, елементи - той чи інший рекомендований контент (товари, відео, музика ), а релевантність - ймовірність того, що користувач скористається (купить/лайкнет/перегляд) даним контентом.

Формально, розглянемо N об'єктів та M елементів . Реузальтат роботи алгоритму ранжування елементів для об'єкта - це відображення, яке зіставляє кожному елементу вагу, що характеризує ступінь релевантності елемента об'єкту (чим більша вага, тим більш релевантний об'єкт). При цьому, набір ваг задає перестановку на наборі елементів елементів (вважаємо, що безліч елементів упорядковане) виходячи з їх сортування за зменшенням ваги.

Щоб оцінити якість ранжирування, необхідно мати певний «еталон», з яким можна було б порівняти результати алгоритму. Розглянемо - еталонну функцію релевантності, що характеризує «справжню» релевантність елементів для даного об'єкта (- елемент ідеально підходить, - повністю нерелевантний), а так само відповідну їй перестановку (за спаданням).

Існує два основних способи отримання:
1. На основі історичних даних. Наприклад, у разі рекомендацій контенту, можна взяти перегляди (лайки, покупки) користувача та присвоїти переглянутим вагам відповідних елементів 1 (), а решті - 0.
2. На основі експертної оцінки. Наприклад, завдання пошуку, для кожного запиту можна залучити команду асессорів, які вручну оцінять релевантності документів запиту.

Варто зазначити, що коли набуває лише екстремальних значень: 0 і 1, то перестановку зазвичай не розглядають і враховують лише безліч релевантних елементів, для яких .

Мета метрики якості ранжування- визначити, наскільки отримані алгоритмом оцінки релевантності та відповідна їм перестановка відповідають істиннимзначенням релевантності. Розглянемо основні метрики.

Mean average precision

Mean average precision at K ( [email protected]) - одна з найчастіше використовуваних метрик якості ранжування. Щоб розібратися в тому, як вона працює, почнемо з «основ».

Примітка: "*precision" метрики використовується в бінарних задачах, де приймає лише два значення: 0 та 1.

Precision at K

Precision at K ( [email protected]) - точність на K елементах - базова метрика якості ранжування одного об'єкта. Допустимо, наш алгоритм ранжування видав оцінки релевантності кожного елемента . Відібравши серед них перші елементи з найбільшим, можна порахувати частку релевантних. Саме це і робить precision at K:

Зауваження: під розуміється елемент , який у результаті перестановки опинився на позиції. Так, - елемент з максимальним , - елемент з другим за величиною і так далі.

Average precision at K

Precision at K – метрика проста для розуміння та реалізації, але має важливий недолік – вона не враховує порядок елементів у «топі». Так, якщо з десяти елементів ми вгадали лише один, то не важливо, на якому місці він був: на першому, або на останньому, - у будь-якому випадку. При цьому очевидно, що перший варіант набагато кращий.

Цей недолік нівелює метрика ранжування average precision at K ( [email protected]) , яка дорівнює сумі [email protected]за індексами k від 1 до K тільки для релевантних елементів, поділеному на K:

Так, якщо з трьох елементів ми релевантним виявився тільки що знаходиться на останньому місці, то якщо вгадали лише той, що був на першому місці, то , а якщо вгадані були всі, то .

Тепер і [email protected]нам по зубах.

Mean average precision на K

Mean average precision at K ( [email protected]) - одна з найчастіше використовуваних метрик якості ранжування. В [email protected]і [email protected]якість ранжирування оцінюється для окремого об'єкта (користувача, пошукового запиту). На практиці об'єктів безліч: ми маємо справу із сотнями тисяч користувачів, мільйонами пошукових запитів тощо. Ідея [email protected]полягає в тому, щоб порахувати [email protected]для кожного об'єкта та усереднити:

Зауваження: ідея ця цілком логічна, якщо припустити, що всі користувачі однаково потрібні та однаково важливі. Якщо ж це не так, то замість простого усереднення можна використовувати виважене, домноживши [email protected]кожного об'єкта на відповідну його «важливість» вагу.

Normalized Discounted Cumulative Gain

Normalized discounted cumulative gain (nDCG)- Ще одна поширена метрика якості ранжування. Як і у випадку з [email protected], Почнемо з основ.

Cumulative Gain at K

Знову розглянемо один об'єкт та елементи з найбільшим. Cumulative gain at K ( [email protected]) - базова метрика ранжирування, яка використовує просту ідею: що релевантні елементи у цьому топі, то краще:

Ця метрика має очевидні недоліки: вона не нормалізована і не враховує позицію релевантних елементів.

Зауважимо, що на відміну від [email protected], [email protected]може використовуватись і у разі небінарних значень еталонної релевантності.

Discounted Cumulative Gain at K

Discounted cumulative gain at K ( [email protected]) - модифікація cumulative gain at K, що враховує порядок елементів у списку шляхом примноження релевантності елемента на вагу, що дорівнює зворотному логарифму номера позиції:

Примітка: якщо приймає тільки значення 0 і 1, то , і формула набуває більш простого вигляду:

Використання логарифму як функції дисконтування можна пояснити такими інтуїтивними міркуваннями: з погляду ранжування позиції на початку списку відрізняються набагато сильніше, ніж позиції його кінці. Так, у разі пошукового двигуна між позиціями 1 і 11 ціла прірва (лише в декількох випадках зі ста користувач заходить далі першої сторінки пошукової видачі), а між позиціями 101 і 111 особливої ​​різниці немає - до них мало хто доходить. Ці суб'єктивні міркування чудово виражаються за допомогою логарифму:

Discounted cumulative gain вирішує проблему обліку позиції релевантних елементів, але лише ускладнює проблему з відсутністю нормування: якщо варіюється в межах , то вже набуває значення не зовсім зрозуміло відрізку. Вирішити цю проблему покликана наступна метрика

Normalized Discounted Cumulative Gain at K

Як можна здогадатися з назви, normalized discounted cumulative gain at K ( [email protected]) - не що інше, як нормалізована версія [email protected]:

де - це максимальне (I - ideal) значення. Оскільки ми домовилися, що набуває значення в , то .

Таким чином, успадковує від облік позиції елементів у списку і при цьому набуває значення в діапазоні від 0 до 1.

Зауваження: за аналогією з [email protected]можна порахувати , усереднений по всіх об'єктах.

Mean reciprocal rank

Mean reciprocal rank (MRR)- ще одна метрика якості ранжування, що часто використовується. Задається вона такою формулою:

де - reciproсal rank для -го об'єкта - дуже проста за своєю сутністю величина, що дорівнює зворотному ранку першого правильно вгаданого елемента.

Mean reciprocal rank змінюється в діапазоні та враховує позицію елементів. На жаль він робить це тільки для одного елемента - одного чітко передбаченого, не звертаючи уваги на всі наступні.

Метрики на основі рангової кореляції

Окремо варто виділити метрики якості ранжирування, що базуються на одному з коефіцієнтів. рангової кореляції. У статистиці, ранговий коефіцієнт кореляції - це коефіцієнт кореляції , який враховує не самі значення, лише їх ранг (порядок). Розглянемо два найбільш поширені рангові коефіцієнти кореляції: коефіцієнти Спірмена і Кенделла.

Ранговий коефіцієнт кореляції Кенделла

Перший з них - коефіцієнт кореляції Кенделла, який ґрунтується на підрахунку узгоджених.
(і неузгоджених) пар у перестановок - пар елементів, яким перестановки надали однаковий (різний) порядок:

Ранговий коефіцієнт кореляції Спірмена

Другий - ранговий коефіцієнт кореляції Спірмена - насправді є чим іншим як кореляції Пірсона, порахованої на значеннях рангів. Є досить зручна формула, що виражає його з рангів безпосередньо:

де – коефіцієнт кореляції Пірсона.

Метрики на основі рангової кореляції мають вже відомі нам недоліки: вони не враховують позицію елементів (ще гірше ніж [email protected], т.к. кореляція вважається за всіма елементами, а не за K елементами з найбільшим рангом). Тому практично використовуються дуже рідко.

Метрики на основі каскадної моделі поведінки

До цього ми не заглиблювалися у те, як користувач (далі ми розглянемо окремий випадок об'єкта - користувач) вивчає запропоновані йому елементи. Насправді, неявно ми зробили припущення, що перегляд кожного елемента незалежнийвід переглядів інших елементів – свого роду «наївність». Насправді ж, елементи найчастіше проглядаються користувачем по черзі, і те, чи переглядає користувач наступний елемент, залежить від його задоволеності попередніми. Розглянемо приклад: у відповідь пошуковий запит алгоритм ранжирування запропонував користувачеві кілька документів. Якщо документи позиції 1 і 2 виявилися вкрай релевантні, то ймовірність того, що користувач перегляне документ на позиції 3 мала, т.к. він буде цілком задоволений першими двома.

Подібні моделі поведінки користувача, де вивчення запропонованих йому елементів відбувається послідовно, і ймовірність перегляду елемента залежить від релевантності попередніх. каскадними.

Expected reciprocal rank

Expected reciprocal rank (ERR)- Приклад метрики якості ранжування, заснованої на каскадній моделі. Задається вона такою формулою:

де ранг розуміється за порядком спадання. Найцікавіше у цій метриці – ймовірності. При їх розрахунку використовуються припущення каскадної моделі:

де - ймовірність того, що користувач буде задоволений об'єктом з рангом. Ці ймовірності вважаються на основі значень. Так як у нашому випадку, то можемо розглянути простий варіант:

який можна прочитати, як: справжня релевантність елемента, що опинився на позиції На закінчення наведемо кілька корисних посилань

УДК 519.816

С. В. СЕМЕНІХІН Л. А. ДЕНІСОВА

Омський державний технічний університет

МЕТОД МАШИННОГО НАВЧАННЯ РАНЖУВАННЯ

НА ОСНОВІ МОДИФІКОВАНОГО ГЕНЕТИЧНОГО АЛГОРИТМУ ДЛЯ МЕТРИКИ ІРСО

Розглянуто завдання ранжирування документів на сторінці результатів інформаційного пошуку та питання машинного навчання ранжирування. Запропоновано підхід до оптимізації функції ранжирування з використанням метрики якості ІОС на основі модифікованого генетичного алгоритму. Проведено дослідження розроблених алгоритмів (на тестових колекціях ЬЕТО^) та показано їх ефективність для машинного навчання ранжирування.

Ключові слова: інформаційний пошук, машинне навчання ранжування, релевантність, оптимізація, генетичні алгоритми.

1. Введення. У сучасних інформаційно-пошукових системах (ІПС) обсяги даних, якими оперує система, настільки великі, що ключовим завданням стає ранжування релевантних документів у відповідь на пошуковий запит користувача. На цьому етапі розвитку ІПС найбільший інтерес представляє машинне навчання (МО) ранжирування. Існуючі підходи до МО, засновані на чисельних методах (зокрема, на градієнтних методах) або на аналітичних розрахунках, мають ряд недоліків, які суттєво впливають на якість інформаційного пошуку та тимчасові витрати, необхідні для ранжування релевантних документів.

На початку проведених досліджень було розглянуто спискові підходи до машинного навчання ранжирування , з яких використовується метод градієнтного спуску . У розглянутих роботах МО зводиться до оптимізації метрики якості пошуку (МКП), однак використовуються тільки метрики, представлені безперервними функціями. Це обмеження часто призводить до того, що в результаті оптимізації функція ранжування має менш високі оцінки за багатьма важливими прийнятими показниками (DCG, nDCG, Graded Mean Reciprocal Rank і т.д.), що є дискретними функціями. У роботі запропоновано застосування генетичних алгоритмів (ГА) при навчанні ранжування для мінімізації функції втрат Хубер з використанням експертних оцінок релевантності як еталонні значення. Також було запропоновано підхід до МО на основі оптимізації дискретних метрик якості інформаційного пошуку.

2. Постановка задачі машинного навчання ранжування. У більшості сучасних інформаційно-пошукових систем функція ранжирування будується на основі n простих ранжуючих функцій (ПРФ) і може бути записана у вигляді:

де SRF¡ - ¡-а проста ранжуюча функція для документа d і запиту д, WCi - ваговий коефіцієнт ¡-ої простої ранжує функції, п - кількість ПРФ в системі ранжування.

У ході машинного навчання ранжування використано набір пошукових документів Б та запитів Про із тестової колекції ЬБТОЯ. Для всіх запитів деО сформована пара з кожним документом dеD. Для кожної такої пари ІПС визначає значення релевантності, що використовуються для ранжування пошукової видачі. Для того, щоб зробити оцінку якості ранжування, системі потрібні еталонні значення релевантності Е для кожної пари документ-запит ^, д). З цією метою використовуються експертні оцінки релевантності.

Для проведення дослідження використана ІПС, у якій ранжування проводиться на основі N = 5 простих ранжуючих функцій SRFi(WC)l г = 1, N, які утворюють векторний критерій оптимальності:

де WCе (WC) - вектор параметрів, що варіюються; (ШС), (ЯБ) - простору параметрів та векторних критеріїв відповідно.

Застосування генетичних алгоритмів для МО ранжування уможливлює максимізацію дискретних метрик якості, таких як nDCG. Метрика nDCG ранжування документів у пошуковій системі визначається відповідно до виразу:

DCG @ n = X 2---

RF (q, d) = X WC. ■ SRF., i=1 1 1

де grade(p) - середня оцінка релевантності, виставлена ​​експертами документу, розташованому на позиції p у списку результатів, gradee; 1/log2(2 + p) - коефіцієнт, що залежить від позицій документа (перші документи мають більшу вагу).

Тоді нормалізована версія NDCG запишеться як

N000@п = ВЗГ@П/г,

де г - фактор нормалізації, який дорівнює максимально можливому значенню 0С [email protected]п для даного запиту (тобто дорівнює ТОВ ідеального ранжування).

Таким чином, для оптимізації (максимізації) метрики пОСО цільова функція (ЯМ) запишеться в наступному вигляді

3. Метрики якості ранжування пошукової видачі. При ранжируванні документів у пошуковій видачі ролі критеріїв виступають метрики якості. Зі списку загальноприйнятих метрик оцінки якості ІПС вибрано три основні, що оцінюють точність, релевантність та повноту інформаційного пошуку.

1. Критерій точності інформаційного пошуку

де a – кількість знайдених релевантних документів, b – кількість документів, помилково прийнятих за релевантні.

2. Критерій Bpref, що оцінює релевантність інформаційного пошуку, використовується для обробки завдання з R релевантними документами та обчислюється за формулою

Bpref = - ^ (1 - Non Re ¡Before(r)/R). (4)

Тут символом r позначений відомий релевантний документ, а NonRelBefore(r) - число відомих нерелевантних документів, ранжованих вище, ніж r (при обчисленні враховуються лише перші R оцінених нерелевантних документів з прогону).

3. Критерій повноти пошукової видачі

r = a/(a+с),

де a – кількість знайдених релевантних документів, з – кількість не знайдених релевантних документів.

4. Тестові колекції. У задачі машинного навчання ранжування необхідний набір документів та запитів із відповідними оцінками релевантності, визначеними експертами. Ці дані використовуються для машинного навчання ранжує функції, а також для оцінки якості

ранжування пошукової видачі системою У процесі МО тестові колекції використовуються як навчальна вибірка і, отже, мають значний вплив на результати. Для проведення досліджень використано тестову колекцію документів та запитів LETOR. Ця колекція використовується у дослідженнях у сфері пошуку інформації підрозділами Microsoft Research. У табл. 1 наведено характеристики тестових колекцій LETOR.

5. Модифікований генетичний алгоритм. Для використання генетичних алгоритмів у машинному навчанні ранжирування завдання має бути поставлене таким чином, щоб рішення було закодовано у вигляді вектора (генотипу), де кожен ген може бути бітом, числом або іншим об'єктом. В даному випадку генотип представлений вектором вагових коефіцієнтів відповідних факторів ранжування. p align="justify"> Умовою зупинки виконання генетичного алгоритму є знаходження оптимального рішення, вичерпання числа поколінь або часу, відведеного на еволюцію.

Слід зазначити, що ГА найефективніші у пошуках області глобального екстремуму, проте вони можуть повільно працювати, коли необхідно знайти локальний мінімум у цій галузі. Пропонований спосіб уникнути цього недоліку - створення модифікованого генетичного алгоритму (МГА), який перемикатиметься на локальний (швидкодіючий) алгоритм оптимізації після знаходження області глобального оптимуму за допомогою базового ГА. Пропонований у роботі МГА є гібридним методом на основі класичного ГА і методу Нелдера - Міда (симплекс-алгоритма). Метод Нелдера - Міда, що часто використовується алгоритм нелінійної оптимізації, є чисельним методом для знаходження мінімуму цільової функції у багатовимірному просторі. Пропонований у цій роботі гібридний алгоритм MGA переключається на метод Нелдера - Міда після виконання умов зупинки ГА. Блок-схема алгоритму MGA показано на рис. 1.

При виконанні досліджень прийнято обмеження на кількість обчислень цільової функції (Nrf = 16 000) при пошуку області глобального екстремуму та умова переходу на алгоритм локальної оптимізації на основі методу Нелдера - Міда (після того, як базовий генетичний алгоритм виконає 75% Nrf операцій).

6. Результати. В результаті проведених досліджень за допомогою алгоритму машинного навчання

Таблиця 1

Кількість документів та запитів у тестових колекціях

Назва тестової колекції Назва підсистеми Кількість запитів Кількість документів

LETOR 4.0 MQ2007 1692 69623

LETOR 4.0 MQ2008 784 15211

LETOR 3.0 OHSUMED 106 16140

LETOR 3.0 Gov03td 50 49058

LETOR 3.0 Gov03np 150 148657

LETOR 3.0 Gov03hp 150 147606

LETOR 3.0 Gov04td 75 74146

LETOR 3.0 Gov04np 75 73834

LETOR 3.0 Gov04hp 75 74409

Рис. 1. Блок-схема гібридного алгоритму МвЛ на основі генетичних алгоритмів та методу Нелдера-Міда

ранжирування LTR-MGA отримано вектор вагових коефіцієнтів WC* для ранжування функції. Далі на основі даних із тестової колекції ЬЕТОЯ проведена оцінка якості ранжування, для чого обчислені метрики якості. Дискретна метрика якості ранжування [email protected]оцінює якість перших п документів відповіді системи. Загальноприйнятими метриками для оцінки якості ранжирування є [email protected], [email protected]і [email protected]Проте для більш детального розгляду змін метрики в залежності від розглянутих значень [email protected]для всіх п від 1 до 10. Для порівняння ефективності розробленого алгоритму з існуючими рішеннями проведено порівняльний аналіз із використанням ранжуючих алгоритмів, наданих у колекціях ЬЕТОЯ 3.0. Результати виконання алгоритмів для тестових колекцій ТБ2003 та ТБ2004 для метрики NDCG представлені на рис. 2. Результати показують, що алгоритм LTR-MGA перевершує тестові алгоритми, причому найбільш високі значення мають

ються для [email protected](На рівні першого документа). Перевага алгоритму LTR-MGA викликана тим, що, на відміну від розглянутих в експериментах тестових функцій, що ранжують, в запропонованому підході для оптимізації функції ранжування саме метрика NDCG використовується в якості цільової функції.

Для того, щоб оцінити якість ранжирування при використанні запропонованого алгоритму LTR-MGA, обчислено значення метрик якості ранжирування документів у пошуковій видачі (рис. 3). Порівняння результатів ранжирування (табл. 2) при використанні базової ранжируючої функції, базового алгоритму LTR-GA та модифікованого алгоритму LTR-MGA свідчить про перевагу останнього.

Крім того, при дослідженні виконано оцінку часу, необхідного для МО ранжирування. Це необхідно для підтвердження того, що запропонований метод LTR-MGA перевершує в цьому показнику підхід, заснований на використанні традиції.

Рис. 2. Порівняння алгоритмів машинного навчання ранжування

за метрикою NDCG для тестових колекцій: зліва – набір даних Gov03td, праворуч – набір даних Gov04td

Рис. 3. Оцінка метрик якості ранжування для базової ранжируючої формули та алгоритмів навчання LTR-GA та LTR-MGA

Метрики якості ранжування для різних алгоритмів машинного навчання.

Таблиця 2

Метрика якості ранжування Базова ранжуюча функція LTR-GA LTR-MGA Підвищення значення метрики, %

Точність 0,201 0,251 0,267 26,81

[email protected](перші 5 документів) 0,149 0,31 0,339 90,47

[email protected](перші 10 документів) 0,265 0.342 0,362 29,14

Bpref 0,303 0,316 0,446 51,49

Повнота 0,524 0,542 0,732 39,03

* Сірим виділено найкращі значення для відповідної метрики

ного генетичного алгоритму (ЬТЯ-ОЛ). Результати порівняння тимчасових витрат на виконання алгоритмів ЬТЯ-ОЛ та ЬТЯ-МОЛ наведено в табл. 3.

7. Висновок. Таким чином, проведені дослідження показали, що при використанні запропонованого підходу значення розглянутих метрик ранжування в ІПС збільшуються (в середньому на 19,55% порівняно з алгоритмом ЬТЯ-ОЛ). Це підтверджує, що ЬТЯ-МОЛ працює коректно і значно покращує функцію ранжирування, тобто успішно вирішує завдання оптимізації. За допомогою модифікованого алгоритму

за рахунок застосування методу локальної оптимізації та введених обмежень на кількість обчислень цільової функції час машинного навчання знизився (в середньому на 17,71% порівняно з використанням традиційного генетичного алгоритму ЬТЯОЛ).

Розроблений алгоритм машинного навчання ранжування ЬТЯ-МОЛ може бути використаний в ІПС, що використовують модель ранжування на основі комбінації простих функцій, що ранжують. Однак слід врахувати деякі обмеження щодо застосування запропонованого підходу. На основі

Оцінка часу виконання машинного навчання ранжування в залежності від розміру навчальної вибірки

Таблиця 3

Розмір текстової колекції документів

Час виконання LTR-GA

Час виконання LTR-MGA

Зменшення часу виконання, %

Середнє значення

*Сірим кольором виділено найкращі значення для відповідного розміру тестової колекції

отриманих результатів виявлено, що після МО найбільший приріст має та метрика якості ранжування, значення якої приймалося як цільова функція. У той самий час інші метрики можуть мати істотного поліпшення, а деяких випадках навіть погіршити свої значення. Як один з можливих підходів до усунення цього недоліку передбачається вирішувати задачу оптимізації як багатокритеріальну: рівномірно покращувати кілька основних метрик ранжирування пошукової видачі, замість оптимізувати одну. Крім того, у подальших дослідженнях планується розробити методику побудови цільової функції на основі лінійної згортки основних метрик якості ранжирування для покращення процесу інформаційного пошуку.

бібліографічний список

1. Tie-Yan Liu. Навчання до Rank for Information Retrieval // Journal Foundations and Trends in Information Retrieval. Vol. 3, issue 3. March 2009. P. 225-331.

2. Christopher J. C. Burges, Tal Shaked, Erin Renshaw. Підготовка до рівня використання Gradient Descent // Proceeding ICML "05 Proceedings of the 22nd international conference on Machine learning. 2005. P. 89-96.

3. Семеніхін, С. В. Дослідження підходів до машинного навчання ранжирування документів пошуковою системою на базі генетичних алгоритмів / С. В. Семеніхін // Росія молода: передові технології – у промисловість. – 2013. – № 2. – С. 82 – 85.

4. Багатокритеріальна оптимізація на основі генетичних алгоритмів при синтезі систем керування: моногр. / Л. А. Денісова. – Омськ: Вид-во ОмДТУ, 2014. – 170 с. - ISBN 978-5-8149-1822-2.

5. Денисова, Л. А. Автоматизація параметричного синтезу системи регулювання з використанням генетичного алгоритму / Л. А. Денисова, В. А. Мещеряков // Автоматизація у промисловості. – 2012. – № 7. – С. 34 – 38.

6. Huber, Peter J. Robust Estimation of Location Parameter // Annals of Statistics. – 1964. – № 53. – P. 73-101.

7. Семеніхін, С. В. Автоматизація інформаційного пошуку на базі багатокритеріальної оптимізації та генетичних алгоритмів / С. В. Семеніхін, Л. А. Денисова // Динаміка систем, механізмів та машин. – 2014. – № 3. – С. 224 – 227.

8. Tie-Yan Liu, Jun Xu, Tao Qin, Wenying Xiong та Hang Li. LETOR: Benchmark Dataset для вивчення на облік для облікового запису // SIGIR 2007 Workshop на обігу до об'єкта для обговорення. – 2007. – С. 3-10.

9. Агєєв, М. С. Офіційні метрики Р0МІП "2004 / М. С. Агєєв, І. Е Кураленок // II Російський семінар з оцінки методів інформаційного пошуку (РОМІП 2004), Пущино, 2004: тр.; під ред. І. С. Некрестьянова.- СПб.: НДІ хімії СПбГУ.- С. 142-150.

10. J. A. Nelder, R. Mead, A simplex method for function minimization, The Computer Journal 7 (1965). 308-313.

СЕМЕНІХІН Святослав Віталійович, аспірант кафедри "Автоматизовані системи обробки інформації та управління". Адреса для листування: [email protected]ДЕНІСОВА Людмила Альбертівна, доктор технічних наук, доцент кафедри "Автоматизовані системи обробки інформації та управління". Адреса для листування: [email protected]

Найчастіше у практиці системного аналітика, що становить FRD, зустрічаються речі, що неформалізуються. Прикладом може бути вимоги типу:

• Програма повинна працювати швидко
• Додаток повинен споживати мало трафіку
• Відеоматеріал має бути якісним.

Такі вимоги, записані в FRD «як є», є жахливим джерелом проблем згодом. Формалізація таких вимог — постійний біль голови аналітика. Зазвичай аналітик вирішує завдання у два прийоми: спочатку висувається «еквівалентна» формальна вимога, потім у процесі спілкування (із замовником, експертом предметної області тощо) доводиться, що така формальна вимога може замінити вихідну вимогу. Взагалі кажучи, отримана нами вимога не є функціональною; воно визначає не «що» повинна вміти робити система, а «як робити». При цьому "як робити" має бути сформульовано з конкретною якісною характеристикою.

Це була преамбула до тези, що системний аналітик повинен добре володіти математичним апаратом і заодно вміти пояснювати «математику» замовнику. А тепер розглянемо приклад.

Про завдання класифікації

Припустимо, що ми пишемо FRD системи контекстної реклами, схожої на Amazon Omakase . Одним із модулів нашої майбутньої системи буде контекстний аналізатор:

Аналізатор приймає на вході текст веб-сторінки та здійснює його контекстний аналіз. Те, як він це робить, нас особливо не цікавить; важливо, що на виході ми отримуємо набір товарних категорій (безліч яких заздалегідь визначено). Далі, на основі цих категорій, ми можемо показувати банери, товарні посилання (як Amazon) тощо. Аналізатор для нас поки що є чорною скринькою, якій ми можемо поставити запитання (у вигляді тексту документа) та отримати відповідь.

Замовник хоче, щоб аналізатор «добре визначав контекст». Нам треба сформулювати, що ця вимога означає. Спочатку поговоримо про контекст як такий, тобто. про той самий набір категорій, який повертається аналізатором. Можна визначити це завдання класифікації , коли документу (веб-сторінці) зіставляється безліч класів із заздалегідь певного числа; у разі класи — це товарні категорії. Завдання класифікації часто зустрічається у обробці текстів (наприклад, спам-фільтри).

Метрики оцінки

Розглянемо метрики оцінки, які застосовуються до завдання класифікації. Припустимо, що ми знаємо правильнікатегорії для певної кількості документів. Згрупуємо відповіді нашого гіпотетичного аналізатора наступним чином:

• Істинно-позитивні ( true positives) — ті категорії, які ми очікували побачити та отримали на виході
• Хибно-позитивні ( false positives) — категорії, яких бути на виході не повинно та аналізатор їх помилково повернув на виході
• Хибно-негативні ( false negatives) — категорії, які ми очікували побачити, але аналізатор їх не визначив
• Істинно-негативні ( true negatives) - категорії, яких бути на виході не повинно і на виході аналізатора, вони теж абсолютно правильно відсутні.

Назвемо тестовою вибіркою безліч документів (сторінок), для яких ми знаємо правильні відповіді. Якщо підрахувати по кожній категорії число влучень (вважаємо попадання по парамдокумент — категорія), отримаємо канонічну табличку розподілу відповідей:

Ліва колонка таблиці – це «правильні» поєднання документів та категорій (присутності яких ми очікуємо на виході), права – неправильні. Верхній рядок таблиці – позитивні (positive) відповіді класифікатора, нижній – негативні (у нашому випадку – відсутність категорії у відповіді). Якщо число всіх пар документ - категоріяодно N, то неважко побачити, що

Загалом тепер можна записати вимогу замовника у вигляді (число неправильних відповідей дорівнює нулю) і на цьому зупинитися. Однак на практиці таких систем не буває і аналізатор, зрозуміло, працюватиме з помилками щодо тестової вибірки. Зрозуміти відсоток помилок нам допоможе метрика правильності (accuracy):

У чисельнику бачимо діагональ матриці — сумарне число правильних відповідей, який ділиться загальне число питань. Наприклад, аналізатор, що дав 9 правильних відповідей з 10 можливих, має оцінку 90%.

Метрика F 1

Простим прикладом незастосовності accuracy-метрики є завдання визначення взуттєвого бренду. Допустимо, ми хочемо підрахувати кількість згадок взуттєвих брендів у тексті. Розглянемо задачу класифікації, метою якої буде визначити, чи є вказана сутність взуттєвим брендом (Timberland, Columbia, Ted Baker, Ralph Lauren тощо). Інакше кажучи, ми розбиваємо сутності в тексті на два класи: A – Взуттєвий бренд, B – Все інше.

Тепер розглянемо вироджений класифікатор, який просто повертає клас B (Все інше) для будь-якихсутностей. Для цього класифікатора кількість істинно-позитивних відповідей дорівнюватиме 0. Взагалі кажучи, давайте подумаємо на тему, а чи часто при читанні тексту в інтернеті нам зустрічаються взуттєві бренди? Виявляється, як не дивно, що у випадку 99.9999% слів тексту не є взуттєвими брендами. Побудуємо матрицю розподілу відповідей для вибірки 100.000:

Обчислимо його accuracy, який дорівнює 99990 / 100000 = 99.99%! Отже, ми легко побудували класифікатор, який, по суті, не робить нічого, однак має величезний відсоток правильних відповідей. У той же час, цілком зрозуміло, що завдання визначення взуттєвого бренду ми не вирішили. Справа в тому, що правильні сутності в нашому тексті сильно розбавлені іншими словами, які для класифікації ніякого значення не мають. З огляду на цей приклад цілком зрозуміло бажання використовувати інші метрики. Наприклад, значення tnявно є «сміттєвим» — воно начебто означає правильну відповідь, але розростання tnв результаті сильно «пригнічує» внесок tp(який нам важливий) у формулі accuracy.

Визначимо міру точності (P, precision) як:

Як неважко помітити, міра точності характеризує, скільки отриманих від класифікатора позитивних відповідей є правильними. Чим більша точність, тим менша кількість помилкових попадань.

Проте міра точності не дає уявлення про те, чи всі правильні відповіді повернув класифікатор. І тому існує так звана міра повноти (R, recall):

Міра повноти характеризує здатність класифікатора «вгадувати» якнайбільше позитивних відповідей з очікуваних. Зауважимо, що помилково-позитивні відповіді не впливають на цю метрику.

Precision та Recall дають досить вичерпну характеристику класифікатора, причому «з різних кутів». Зазвичай при побудові таких систем доводиться весь час балансувати між двома цими метриками. Якщо ви намагаєтеся підвищити Recall, роблячи класифікатор більш оптимістичним, це призводить до падіння Precision через збільшення числа помилково-позитивних відповідей. Якщо ж ви підкручує свій класифікатор, роблячи його більш «песимістичним», наприклад, суворіше фільтруючи результати, то при зростанні Precision це викликає одночасне падіння Recall через відбраковування якогось числа правильних відповідей. Тому зручно для характеристики класифікатора використовувати одну величину, так звану метрику F1:

Фактично це просто середнє гармонічне величин P та R. Метрика F 1 досягає свого максимуму 1 (100%), якщо P = R = 100%.
(Неважко прикинути, що з нашого виродженого класифікатора F 1 = 0). Величина F 1 є однією з найпоширеніших метрик для таких систем. Саме F 1 ми будемо використовувати, щоб сформулювати порогову якість нашого аналізатора в FRD.

У обчисленні F 1 завдання класифікації є два основних підходу.

• Сумарний F 1: результати по всіх класах зводимо в одну єдину таблицю, за якою обчислюється метрика F 1 .
• Середній F 1: для кожного класу формуємо свою contingency matrix і своє значення F 1 потім беремо просте арифметичне середнє для всіх класів.

Навіщо потрібен другий спосіб? Справа в тому, що розміри вибірки для різних класів можуть відрізнятися. Для якихось класів у нас може бути дуже мало прикладів, а для якихось багато. У результаті метрики одного «великого» класу, будучи зведеними до однієї загальної таблиці, «забиватимуть» решту. У ситуації, коли хочемо оцінити якість роботи системи більш-менш рівномірно всім класів, другий варіант підходить краще.

Навчальна та тестова вибірка

Вище ми розглядали класифікацію на єдиній вибірці, на яку нам відомі всі відповіді. Якщо це застосувати до контекстного аналізатора, який ми намагаємося описати, все виглядає трохи складніше.

Насамперед, ми маємо зафіксувати товарні категорії. Ситуація, коли гарантуємо якусь величину F 1 , а набір класів у своїй може необмежено розширюватися, практично тупикова. Тому додатково зазначається, що набір категорій фіксований.

Ми обчислюємо значення F 1 за заданою вибіркою, яка відома заздалегідь. Ця вибірка зазвичай називається навчальною. Однак ми не знаємо, як поведеться класифікатор на тих даних, які нам невідомі. Для цих цілей зазвичай використовується так звана тестова вибірка, іноді звана golden set. Різниця між навчальною та тестовою вибіркою чисто умоглядна: адже маючи кілька прикладів, ми можемо розрізати його на навчальну та тестову вибірку як нам завгодно. Але для самонавчання систем формування правильної навчальної вибірки дуже критично. Неправильно підібрані приклади можуть вплинути на якість роботи системи.

Типова ситуація, коли класифікатор показує хороший результат на навчальній вибірці і абсолютно провальний - на тестовій вибірці. Якщо наш алгоритм класифікації заснований на машинному навчанні (тобто залежить від навчальної вибірки), ми можемо оцінити його якість за складнішою «плаваючою» схемою. Для цього всі наявні у нас приклади ділимо, скажімо, на 10 частин. Вилучаємо першу частину та використовуємо її для навчання алгоритму; 90% прикладів, що залишилися, використовуємо як тестову вибірку і обчислюємо значення F 1 . Потім вилучаємо другу частину і використовуємо як навчальну; отримуємо інше значення F 1 і т.д. У результаті ми отримали 10 значень F 1 тепер беремо їх середнє арифметичне значення, яке і стане остаточним результатом. Повторюся, що це спосіб (так званий також cross-fold validation) має сенс лише алгоритмів, заснованих на машинному навчанні.

Повертаючись до написання FRD, помічаємо, що у нас ситуація набагато гірша. Ми маємо потенційно необмежений набір вхідних даних (всі веб-сторінки інтернету) і немає жодного способу оцінити контекст сторінки, крім як участь людини. Таким чином, наша вибірка може бути сформована тільки вручну, причому сильно залежати від капризів укладача (а рішення про те, чи віднести сторінку до якоїсь категорії приймає людина). Ми можемо оцінити міру F 1 на відомих прикладах, але ніяк не можемо дізнатися F 1 для всіх сторінок інтернету. Тому для потенційно необмежених наборах даних (таких, як веб-сторінки, яких багато), іноді застосовують «метод тику» (unsupervised). І тому випадковим чином вибирають кілька прикладів (сторінок) і з них оператор (людина) становить правильний набір категорій (класів). Потім ми можемо випробувати класифікатор цих вибраних прикладах. Далі, вважаючи, що вибрані нами приклади є типовими, ми можемо приблизно оцінити точність алгоритму (Precision). При цьому Recall ми оцінити не можемо (невідомо скільки правильних відповідей знаходяться за межами обраних нами прикладів), отже, не можемо обчислити і F 1 .

Таким чином, якщо ми хочемо дізнатися, як поводиться алгоритм на всіх можливих вхідних даних, найкраще, що зможемо оцінити в цій ситуації, це наближене значення Precision. Якщо всі згодні використовувати заздалегідь певну фіксовану вибірку, можна обчислити середні значення F 1 з цієї вибірки.

В підсумку?

А в результаті нам доведеться зробити таке:

1. Зафіксувати навчальну вибірку. Навчальна вибірка буде побудована виходячи з уявлень замовника про «правильний» контекст.
2. Зафіксувати набір категорій нашого аналізатора. Не можемо ми обчислювати F 1 за невизначеним набором класів?
3. Описати вимогу у вигляді: Аналізатор повинен визначати контекст із середньою величиною F 1 не менше ніж 80%.(наприклад)
4. Пояснити це замовнику.

Як бачимо, написати FRD таку систему нелегко (особливо останній пункт), але можливо. Що стосується порогового значення F 1 у таких випадках можна відштовхуватися від значень F 1 для схожих завдань класифікації.

На елементах усередині кожного списку. Частковий порядок зазвичай задається шляхом вказівки оцінки для кожного елемента (наприклад, "релевантний" або "не релевантний"; можливе використання і більше, ніж двох градацій). Мета ранжує моделі - найкращим чином (у певному сенсі) наблизити і узагальнити спосіб ранжування в навчальній вибірці на нові дані.

Навчання ранжирування - це ще досить молода область досліджень, що бурхливо розвивається, що виникла в 2000-і роки з появою інтересу в галузі інформаційного пошуку до застосування методів машинного навчання до завдань ранжування.

Енциклопедичний YouTube

• 1 / 5

  Під час навчання ранжируючої моделі і при її роботі, кожна пара документ-запит переводиться в числовий вектор з ранжуючих ознак (також званих ранжуючими факторами або сигналами), що характеризують властивості документа, запиту та їх взаємовідносини. Такі ознаки можна поділити на три групи:

  Нижче наведено деякі приклади ранжуючих ознак, що використовуються в широко відомому в даній галузі досліджень наборі даних LETOR:

  • Значення заходів TF, TF-IDF , BM25 і мовної моделі відповідності запиту різних зон документа (заголовка, URL, основного тексту, тексту посилань);
  • Довжини та IDF-суми зон документа;
  • Ранги документа, отримані різними варіантами таких алгоритмів ранжування посилань, як PageRank і HITS .

  Метрики якості ранжування

  Існує кілька метрик, якими оцінюють і порівнюють якість роботи алгоритмів ранжирування на вибірці з асесорними оцінками. Часто параметри ранжує моделі прагнуть підігнати так, щоб максимізувати значення однієї з цих метрик.

  Приклади метрик:

  Класифікація алгоритмів

  У своїй статті «Learning to Rank for Information Retrieval» та виступах на тематичних конференціях, Тай-Ян Лью з Microsoft Research Asia проаналізував існуючі на той момент методи для вирішення завдання навчання ранжування та запропонував їх класифікацію на три підходи, залежно від вхідного представлення, що використовується. даних та функції штрафу:

  Поточковий підхід

  Примітки

  1. Tie-Yan Liu (2009), Learning to Rank for Information Retrieval, Foundations and Trends in Information Retrieval: Vol. 3: No 3, с. 225-331, ISBN 978-1-60198-244-5, DOI 10.1561/1500000016. Доступні слайди із виступу Т. Лью на конференції WWW 2009.