Projekt oceny rówieśniczej - wybór wykresu w celu uzyskania dokładnych rankingów / ocen

Tło. Piszę kod do półautomatycznej gradacji, używając gradacji rówieśniczej jako części procesu gradacji. Uczniowie otrzymują pary esejów na raz, a uczniowie mają suwak do wyboru, który jest lepszy io ile lepszy. np. suwak może wyglądać mniej więcej tak:

A---X-B

Na podstawie wyników oceny rówieśniczej eseje są klasyfikowane, a nauczyciel oceni najwyższe X% i dolne X%, a wyniki wszystkich esejów zostaną automatycznie obliczone na podstawie tego. Wymyśliłem już metody przeprowadzania tego procesu rankingu / oceniania; ta część działa dobrze.

Moje pytanie. Jak wybrać pary esejów do przekazania studentom?

Symulacje sugerują, że potrzebujemy eseju, który zostanie oceniony co najmniej 3 razy, aby uzyskać dokładny ranking. Dlatego każdy esej powinien pojawić się w co najmniej 3 parach przedstawionych do oceny rówieśniczej.

Możemy to potraktować jako problem z wykresem. Pomyśl o esejach jak o węzłach. Każda krawędź reprezentuje parę esejów, które są prezentowane podczas procesu oceniania rówieśniczego. Powyższe wyniki dokładności sugerują, że stopień każdego węzła (lub większości węzłów) powinien wynosić co najmniej 3. Jakiego rodzaju wykresu powinienem użyć? Jak wygenerować wykres, który będzie używany podczas oceniania rówieśniczego?

Jednym z wyzwań jest to, że jeśli masz klastry na wykresie, to wypaczy oceny rówieśników. Na przykład, nie chcielibyśmy mieć wysokiej jakości esejów ocenianych równorzędnie, głównie w stosunku do esejów wysokiej jakości, ponieważ to wypaczyłoby wyniki oceny rówieśniczej.

Co byś polecił?

Myślę, że ten problem można modelować za pomocą niekierowanego wykresu przy użyciu czegoś takiego:

• Zacznij od zajęcia węzła z najmniejszym stopniem i połącz go z następnym
• Kontynuuj, aż średni stopień wyniesie co najmniej 3
• Maksymalizuj łączność węzłów
• Zminimalizuj liczbę klików

Czy to dobre podejście? Jeśli nie, co poleciłbyś zamiast tego?

Składają się na to dwie części: (a) wybór wykresu ( projekt eksperymentalny ) w celu ustalenia, które pary esejów zostaną ocenione przez uczniów w procesie oceniania rówieśniczego, oraz (b) uszeregowania wszystkich esejów na podstawie ocen rówieśniczych studenta, określ, który nauczyciel powinien uszeregować. Zasugeruję kilka metod dla każdego.

Wybór wykresu

Opis problemu Pierwszym krokiem jest wygenerowanie wykresu. Innymi słowy, musisz wybrać, które pary esejów pokazać uczniom podczas ćwiczenia oceniania rówieśniczego.

Sugerowane rozwiązanie. Do tego zadania sugeruję wygenerowanie losowego wykresu , wybieranego losowo równomiernie ze zbioru wszystkich 3-regularnych (prostych) wykresów.$G$

Uzasadnienie i szczegóły. Wiadomo, że losowy wykres nieregularny jest dobrym ekspanderem. W rzeczywistości zwykłe wykresy mają asymptotycznie optymalny współczynnik ekspansji. Ponieważ wykres jest losowy, powinno to wyeliminować ryzyko wypaczenia gradacji. Wybierając losowo jednolity wykres, masz pewność, że twoje podejście jest jednakowo sprawiedliwe dla wszystkich uczniów. Podejrzewam, że jednolicie losowy 3-regularny wykres będzie optymalny dla twoich celów.$d$

Rodzi to pytanie: jak wybrać 3-regularny (prosty) wykres na wierzchołkach, równomiernie losowo?$n$

Na szczęście istnieją znane algorytmy do tego. Zasadniczo wykonujesz następujące czynności:

1. Utwórz punkty. Możesz myśleć o tym jak o 3 kopiach każdego z wierzchołków. Generuj, równomiernie losowo, losowe idealne dopasowanie na tych punktach. (Innymi słowy, powtarzaj następującą procedurę, aż wszystkie punkty zostaną sparowane: wybierz dowolny niesparowany punkt i sparuj go z innym punktem wybranym losowo z zestawu niesparowanych punktów).$3n$$n$$3n$$3n$

2. Dla każdego dwóch punktów, które pasują do siebie, narysuj krawędź między odpowiadającymi wierzchołkami (których są kopią). To daje wykres wierzchołków.$n$

3. Następnie sprawdź, czy otrzymany wykres jest prosty (tzn. Nie ma pętli własnych i powtarzających się krawędzi). Jeśli nie jest to proste, odrzuć wykres i wróć do kroku 1. Jeśli jest to proste, gotowe. wypisz ten wykres.

Wiadomo, że ta procedura generuje jednolity rozkład na zbiorze 3-regularnych (prostych) wykresów. Wiadomo również, że w kroku 3 masz stałe prawdopodobieństwo zaakceptowania wynikowego wykresu, więc średnio algorytm wykona próby - więc jest to dość wydajne (np. Wielomianowy czas działania).$O(1)$

Widziałem takie podejście przypisywane Bollobas, Bender i Canfield. Podejście to jest również krótko streszczone na Wikipedii . Dyskusję można również znaleźć na tym blogu .

Technicznie rzecz biorąc, wymaga to, aby liczba była parzysta (w przeciwnym razie nie ma 3-regularnego wykresu na wierzchołkach). Jest to jednak łatwe do rozwiązania. Na przykład, jeśli jest nieparzysty, możesz losowo wybrać jeden esej, odłożyć go na bok, wygenerować losowy 3-regularny wykres w pozostałych esejach, a następnie dodać 3 dodatkowe krawędzie z eseju odłożonego do 3 losowo wybranych innych esejów. (Oznacza to, że pojawią się 3 eseje, które są oceniane 4 razy, ale to nie powinno wyrządzić żadnej szkody).$n$$n$$n$

Ranking wszystkich esejów

Opis problemu OK, więc teraz masz wykres i przedstawiłeś uczniom te pary esejów (zgodnie z zaznaczonymi krawędziami na wykresie), aby mogli ocenić podczas ćwiczenia oceniania rówieśniczego. Masz wyniki każdego porównania esejów. Teraz Twoim zadaniem jest wyliczyć liniowy ranking wszystkich esejów, aby pomóc ci określić, które z nich ma ocenić nauczyciel.

Rozwiązanie. Zasugerowałem użycie modelu Bradleya-Terry'ego . Jest to podejście matematyczne, które rozwiązuje dokładnie ten problem. Został zaprojektowany z myślą o klasyfikowaniu graczy w niektórych dyscyplinach sportowych na podstawie wyników meczów między parami graczy. Zakłada się, że każdy gracz ma (nieznaną) siłę, którą można określić ilościowo jako liczbę rzeczywistą, a prawdopodobieństwo, że Alice pokona Boba, zależy od pewnej gładkiej funkcji różnicy ich sił. Następnie, biorąc pod uwagę pary wygranych / przegranych, ocenia siłę każdego gracza.

To powinno być dla Ciebie idealne. Możesz traktować każdy esej jako gracza. Każde porównanie dwóch esejów (podczas procesu oceniania rówieśniczego) jest jak wynik między nimi. Model Bradleya-Terry'ego pozwoli ci wziąć wszystkie te dane i wyliczyć siłę dla każdego eseju, gdzie wyższe siły odpowiadają lepszym esejom. Teraz możesz wykorzystać te mocne strony do uporządkowania wszystkich esejów.

Szczegóły i dyskusja. W rzeczywistości model Bradley-Terry jest jeszcze lepszy niż to, o co prosiłeś. Poprosiłeś o liniowy ranking, ale model Bradleya-Terry'ego daje ocenę (w liczbach rzeczywistych) każdemu esejowi. Oznacza to, że wiesz nie tylko, czy esej jest silniejszy niż esej , ale przybliżone oszacowanie, jak bardzo jest ono silniejsze. Możesz na przykład użyć tego do poinformowania swojego eseju o rankingu.$i$$j$

Istnieją alternatywne sposoby wnioskowania o rankingach lub rankingach dla wszystkich esejów, biorąc pod uwagę posiadane dane. Na przykład metoda Elo jest inna. Kilka z nich streszczam w odpowiedzi na inne pytanie ; przeczytaj tę odpowiedź, aby uzyskać więcej informacji.

Jeszcze jeden komentarz: model Bradleya-Terry'ego zakłada, że ​​wynikiem każdego porównania między dwoma graczami jest wygrana lub przegrana (tj. Wynik binarny). Wygląda jednak na to, że faktycznie masz bardziej szczegółowe dane: suwak da przybliżoną ocenę tego, o ile lepiej równiarka ocenia jeden esej niż drugi. Najprostszym podejściem byłoby po prostu przypisanie każdego suwaka do wyniku binarnego. Jednak jeśli naprawdę chcesz, możesz być w stanie wykorzystać wszystkie dane, używając bardziej wyrafinowanej analizy. Model Bradleya-Terry'ego obejmuje regresję logistyczną. Jeśli uogólnisz to, aby użyć uporządkowanego logit , założę się, że możesz skorzystać z dodatkowych informacji, które masz z każdego suwaka, biorąc pod uwagę, że wyniki z suwaków nie są binarne, ale są jedną z kilku możliwości.

Efektywne wykorzystanie nauczyciela

Sugerujesz, aby nauczyciel ręcznie ocenił górną X% i dolną X% wszystkich esejów (korzystając z rankingu wyprowadzonego z wyników oceny rówieśniczej). To może zadziałać, ale podejrzewam, że nie jest to najbardziej efektywne wykorzystanie ograniczonego czasu nauczyciela. Zamiast tego chciałbym zaproponować alternatywne podejście.

Sugeruję, abyś ocenił podzbiór esejów nauczyciela, przy czym ten podzbiór został starannie wybrany, aby zapewnić najlepszą możliwą kalibrację dla wszystkich esejów, które nie zostały ocenione przez nauczyciela. Myślę, że może to pomóc, jeśli wybierzesz próbkę esejów obejmujących zakres możliwych odpowiedzi (więc dla każdego eseju jest jakiś esej oceniany przez nauczyciela, który nie jest zbyt daleko od niego). W tym celu mogę wymyślić dwa podejścia, które można rozważyć:

• Grupowanie. Weź oceny, które są produkowane przez model Terry-Bradley. Jest to zbiór liczb rzeczywistych, jedna liczba rzeczywista na esej. Teraz zgrupuj je. Załóżmy, że chcesz mieć stopień nauczyciela eseje. Jednym podejściem byłoby użycie średnich oznacza grupowanie (w tych jednowymiarowych punktach danych) do grupowania esejów w klastrów, a następnie losowe wybranie jednego eseju z każdego klastra do oceny przez nauczyciela - lub poproszenie nauczyciela o ocenę „ szef klastra ”każdego klastra.$n$$k$$k$$k$

• Najpierw najdalszy punkt. Alternatywą jest, aby spróbować wybrać podzbiór esejów, które są tak różne od siebie, jak to możliwe. Algorytm „najpierw najdalszy punkt” (FPF) jest do tego czystym podejściem. Załóżmy, że masz jakąś funkcję odległości która pozwala określić ilościowo odległość między dwoma esejami i : mała odległość oznacza, że ​​eseje są podobne, większa odległość oznacza, że ​​są niepodobne. Biorąc pod uwagę zestaw szkiców, niech jest odległością od do najbliższego szkicu w . Pierwszy algorytm najdalszego punktu oblicza listę$k$$d(e_i,e_j)$$e_i$$e_j$$S$$d(e,S) = \min_{e' \in S} d(e,e')$$e$$S$$k$szkice, w następujący sposób: jest próba maksymalizujący (ze wszystkich szkiców tak, że ). Algorytmy Generuje zestaw esejów, które są tak odmienne od siebie, jak to możliwe - co oznacza, że każdy z pozostałych esejów jest całkiem podobny do co najmniej jednego z tych . Dlatego uzasadnione byłoby, aby nauczyciel eseje wybrane przez algorytm FPF.$e_1,e_2,\dots,e_k$$e_{i+1}$$d(e,\{e_1,e_2,\dots,e_i\})$$e$$e \notin \{e_1,e_2,\dots,e_i\}$$k$$k$$k$

Podejrzewam, że którekolwiek z tych podejść może zapewnić dokładniejsze wyniki niż ocena przez nauczyciela najwyższych X% i najniższych X% esejów - ponieważ najlepsze i najgorsze eseje prawdopodobnie nie są reprezentatywne dla masy esejów w środku.

W obu podejściach można zastosować bardziej wyrafinowaną funkcję odległości, która uwzględnia nie tylko oszacowania siły oparte na ocenie rówieśniczej, ale także inne czynniki pochodzące z esejów. Najprostsza możliwa funkcja odległości uwzględniałaby tylko wynik modelu Terry'ego-Bradleya, tj. gdzie jest siłą esej oszacowana przez model Terry-Bradley oparty na wynikach klasyfikacji rówieśniczej. Możesz jednak zrobić coś bardziej zaawansowanego. Na przykład możesz obliczyć znormalizowaną odległość edycji Levenshteina między esejem i$d(e_1,e_2) = (s(e_1)-s(e_2))^2$$s(e)$$e$$e_1$$e_2$(traktując je jako ciągi tekstowe, obliczając odległość edycji i dzieląc przez długość większej z dwóch) i używaj tego jako kolejnego czynnika w funkcji odległości. Można również obliczyć wektory cech za pomocą modelu work-of-words na słowach w esejach i użyć odległości L2 między tymi wektorami cech (z cechami znormalizowanymi za pomocą tf-idf) jako kolejnego czynnika w funkcji odległości. Możesz użyć funkcji odległości, która jest średnią ważoną różnicy w sile (na podstawie szacunków Terry'ego-Bradleya), znormalizowanej odległości edycji i wszystkiego, co wydaje się pomocne. Taka bardziej zaawansowana funkcja odległość może pomóc zrobić lepszą pracę pomagając algorytm klastrowania wybrać, które są najlepsze eseje mieć stopień nauczyciela.$k$

kilka pomysłów opartych na nieprecyzyjnie opisanym nakładzie i wynikach oraz tym, co należy obliczyć (być może możesz to zmienić, uwzględniając to pytanie).

najwyraźniej jest to w zasadzie problem „gorącej lub nie” „twarzy”, który powstał wraz z założeniem Facebooka (jak pokazano w filmie „sieć społecznościowa”). w oryginalnej „grze” użytkownicy mieli dwa zdjęcia i wybrali między bardziej atrakcyjną kobietą. w twoim systemie można wybierać między dwoma esejami, z których jeden jest lepszy.

z niemal cyber-folkloru najwyraźniej algorytmy rankingowe Elo stosowane w systemach punktacji meczów szachowych mogą być użyte do obliczenia zbieżnego rozwiązania (w tym przypadku zasadniczo oszacuj wynik esejów zgodny z wyrażonym ukierunkowanym wykresem preferencji), ale nie widziałem jeszcze ostrożnego opis / opis tego.

inną opcją jest użycie Pagerank. która oblicza szacunkowy wpływ strony na podstawie grafu linków kierowanych. preferencje dotyczące esejów są analogiczne do linków do strony internetowej.

problem wydaje się również podobny do analizy cytowań, w której prace naukowe przytaczają inne prace i szacuje się ich wpływ. [ale zauważ, że Pagerank jest również wiodącym algorytmem w tej dziedzinie.]

[1] Dlaczego warto korzystać z rankingów Elo w algorytmie FaceMash? przepełnienie stosu

[2] System rankingowy Elo , wikipedia

[3] Pagerank , wikipedia

[4] analiza cytowań , wikipedia