Algorytm: Wyszukiwanie binarne, gdy wartości są niepewne

Potrzebuję algorytmu do wyszukiwania binarnego, gdy test na każdym kroku może dać zły wynik.

Tło: Muszę umieścić uczniów na najbardziej odpowiednim z 12 poziomów trudności. Obecne podejście jest brutalne i zadaje 60 pytań wielokrotnego wyboru o 4 odpowiedziach o rosnącym stopniu trudności, zatrzymujących się po trzech błędach i umieszczających ucznia na poziomie: floor((score - 1) / 5) + 1z minimum 1.

Obawiamy się, że klienci są wyłączeni, gdy stają przed testem z maksymalnie 60 pytaniami, zanim będą mogli faktycznie korzystać z programu, dlatego chcielibyśmy zminimalizować liczbę pytań zadawanych w teście. Obawiamy się również, że klienci pomijają test kwalifikacyjny (ponieważ wydaje się długi), a następnie rezygnują z programu, ponieważ wydaje się zbyt łatwy.

Mediana miejsca docelowego znajduje się faktycznie na poziomie 2, więc 50 +% uczniów uzyska wynik <11 (tj. Odpowiedź <14 pytań). Anegdotycznie może to być spowodowane tym, że się nudzą i przestają poważnie traktować pytania (są to małe dzieci).

Proponowane rozwiązanie: Zaimplementuj test jako wyszukiwanie binarne ponad dwunastu elementów, zaczynając od pytania na poziomie trudności 6/7 i postępując w oparciu o to, czy odpowiedzą na pytanie poprawnie, czy nie. Teoretycznie może to znaleźć odpowiedni poziom trudności w 3-4 pytaniach.

Problem: Jak można się domyślić na podstawie istniejącego testu, który kończy się po trzech błędnych odpowiedziach i przy użyciu 60 pytań do wyboru między 12 poziomami, chcemy uwzględnić studentów z poprawnymi odpowiedziami (co powinni zrobić 25% czasu) lub przypadkowo udzielanie błędnych odpowiedzi (tłuste palce, błędnie odczytane pytania itp.). Jest to jeszcze ważniejsze w przypadku wyszukiwania binarnego, ponieważ znalezienie poprawnej odpowiedzi na pierwsze pytanie może umieścić cię w górnej połowie poziomów trudności, nawet jeśli wszystkie pozostałe pytania będą błędne.

Czy istnieje więc uznany algorytm wyszukiwania binarnego, w którym nie można zagwarantować, że pojedynczy test jest dokładny?

Naiwnie mogę wypróbować 3 lub 5 pytań na każdym etapie, a ponieważ wczesne pytania mają większy wpływ na końcowy wynik niż pytania późniejsze, być może dodam te dodatkowe pytania tylko do pierwszych kroków, a nie do kolejnych. Czy jest w tym coś więcej?

Potraktuj problem jak szereg prawdopodobieństw bayesowskich; początkowo załóżmy, że istnieje 1/13 szansy, że dziecko znajduje się tuż poniżej każdego poziomu, a dla kompletności 1/13 szansy, że jest poza górą. Następnie: 1) Znajdź poziom środkowy tablicy, tj. Poziom, na którym prawdopodobieństwo bycia powyżej niego jest najbliższe 50% 2) Zadaj dziecku pytanie z tego poziomu. 3) Użyj reguły Bayesa, aby zaktualizować prawdopodobieństwo każdej komórki, zakładając 25% poziom błędu. Przerwij i zwróć najbardziej prawdopodobny poziom, gdy jedna komórka osiągnie wystarczająco wysokie prawdopodobieństwo, lub, jak sądzę, gdy zabraknie pytań na poziomie.

Bardziej rygorystyczne podejście do tego algorytmu jest tutaj ; Polecam przeczytać przed wdrożeniem.