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

11

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?


źródło
Po co w ogóle testować? Po prostu sam dostosuj pytania w teście
Scott Stensland
@ScottStensland, ciekawa myśl. Jednak faktyczny program to 12 „map” po 10 „lekcji” każda z każdą lekcją składającą się z 8-15 „działań” na płótnie HTML5 lub gier o bardzo zróżnicowanym designie. Uczniowie przechodzą przez mapy i otrzymują nagrody i wyróżnienia / certyfikaty po każdej lekcji i mapie. Gdybyśmy stale dostosowywali ich poziom po każdej grze, byłoby to dość dezorientujące i musielibyśmy gromadzić informacje zwrotne we wszystkich naszych istniejących grach i opracowywać zasady dotyczące opinii dla każdej gry.
@Kirill, czy istnieje prosty sposób na przeniesienie / przeniesienie pytania do innej sekcji?
@ jim Możesz zgłosić to moderatorowi z prośbą o przeniesienie pytania, możesz też usunąć to pytanie tutaj i utworzyć nowe identyczne pytanie. Zazwyczaj odradza się stosowanie crossspostingu (posiadanie identycznych pytań na różnych stronach jednocześnie). Podjąłem tę sugestię, ponieważ wydaje mi się, że jest to stosunkowo proste pytanie dotyczące statystyki / uczenia maszynowego, które uzyskałoby jasną odpowiedź znacznie szybciej.
Kirill,

Odpowiedzi:

2

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.

Timothy Nodine
źródło