Сравнение алгоритмов вычисления точного теста Фишера - lanit-tercom-school/analyzeme GitHub Wiki

Из центра биоинформатики прислали 4 статьи, касающиеся алгоритмов вычисления точного теста Фишера.
Вот папка на Яндекс Диске: https://docviewer.yandex.ru/?url=ya-disk-public%3A%2F%2FTzhJY9LUeqlfZRz9Eo7P7M6DGAF5ba9qm6RbIs2DqH8%3D%3A%2FPapers.zip&name=Papers.zip&c=5863f2f9e5f8
Одна из статей ссылается на еще одну статью по этой теме 1981-ого года, "An Algorithm for Finding the Exact Significance Levels of r × c Contingency Tables" (Marcello Pagano and Katherine Taylor Halvorsen).

Рассмотрим целесообразность реализации каждого из них:

Алгоритм, изложенный в файле Mehta_80(2xk).pdf (Mehta & Patel, 1980), проигрывает любому другому, описанному далее:
в статье Пагано и Хальворсена указывается, что их алгоритм лучше, даже несмотря на то, что новый алгоритм способен работать с таблицами любого размера.

Впрочем, для точного вычисления точного теста Фишера для таблиц произвольного размера лучше всего подходит алгоритм, описанный в файле Mehta_83.pdf (Mehta & Patel, 1983). В предисловии к статье есть следующее предложение: "The present article provides an alternative algorithm for the exact treatment of r x c contingency tables which considerably extends the bounds of computational feasibility relative to the algorithm provided by Pagano and Halvorsen" .
Также в статье приведена таблица, вот некоторые ее фрагменты:

2x4 .32 .82
3x3 .31 .81
3x5 2.38 34.02
5x5 1.30 87.45
5X5 2.04 815.36
5x5 14.22 4910.74

Первые два числа - размерности таблицы, затем идет скорость работы алгоритма из Mehta_83.pdf, затем идет скорость алгоритма Пагано и Хальворсена на таблице той же размерности.
Как видно, алгоритм из Mehta_83.pdf гораздо быстрее.

Однако при вычислении таблицы размером 2xC можно использовать его модификацию, описанную в файле Requena_06.pdf (F. Requenaa,∗, N. Martín Ciudad, 2006) , которая (согласно авторам статьи), ощутимо быстрее(вплоть до нескольких раз).

Промежуточный итог: Для точного вычисления точного теста Фишера лучше использовать алгоритм из Mehta_83.pdf для таблиц размера RxC и алгоритм из Requena_06.pdf для таблиц размера 2xC.

Поскольку для больших таблиц любой алгоритм точного вычисления точного теста Фишера будет плох, иногда имеет смысл воспользоваться неточным вычислением этого теста. Для этого в файле Mehta_86(hibrid).pdf (Mehta & Patel, 1986) предложен алгоритм неточного вычисления этого теста. Он имеет достаточно малую ошибку(он гораздо точнее чем хи-квадрат), но работает гораздо быстрее любого другого алгоритма(в самом файле есть таблица со сравнением скоростей).
Надо отметить, что алгоритм из Requena_06.pdf также можно модифицировать для неточного вычисления теста(из статьи: "The proposed modifications are compatible with other improvements already proposed for the Network Algorithm, and especially with the Hybrid Algorithm of Mehta and Patel.").

Итого:

	Точно	Неточно
Размер таблиц - RxC	Mehta_83.pdf	Mehta_86(hibrid).pdf
Размер таблиц - 2xC	Requena_06.pdf	Requena_06.pdf - hibrid modification