Wikipedysta:Gus~plwiki/Ugly duckling theorem

Twierdzenie o brzydkim kaczątku (ang. The Ugly duckling theorem) stanowi, że żadna klasyfikacja nie jest możliwa bez pewnego rodzaju uprzedzeń. Zakładając skończenie wiele właściwości, które można łączyć przez logiczne łączniki i skończenie wiele obiektów, twierdzenie to dowodzi, że dowolne dwa różne obiekty dzielą taką samą liczbę właściwości. Twierdzenie to zostało nazwane na cześć opowieści Hansa Christiana Andersena z 1843 roku "Brzydkie kaczątko", ponieważ pokazuje, że kaczątko jest tak samo podobne do łabędzia, jak dwa kaczątka podobne są do siebie. Zaproponował je Satosi Watanabe w 1969 r.  : 376–377

Wzór matematyczny

Przykład Watanabe z użyciem obiektów A, B, C i właściwości F („pierwszy”), W („biały”). „0”, „1”, „ ¬ ”, „ ∧ ”, „ ∨ ” i „ ⊕ ” oznaczają „ fałsz ”, „ prawda ”, „ nie ”, „ i „, ” lub „ i „ wyłączny lub ” odpowiednio. Ponieważ F zdarza się implikować W, każdy predykat, który można utworzyć z F i W, pokrywa się z innym, stąd istnieje tylko 8 możliwych do rozszerzenia różnych predykatów, każdy pokazany na osobnej linii. Białe kaczuszki A i B zgadzają się co do 4 z nich (linia 2, 3, 4, 8), ale podobnie jak A i C (linia 3, 5, 7, 8), podobnie jak B i C (linia 1, 3, 6, 8).  : 368

Załóżmy, że wszechświat zawiera n obiektów, które chcemy podzielić na klasy lub kategorie. Nie ma z góry przyjętych pomysłów ani uprzedzeń co do tego, jakie kategorie są „naturalne” lub „normalne”, a jakie nie. Trzeba więc rozważyć wszystkie możliwe klasy, wszystkie możliwe sposoby tworzenia zbiorów z n obiektów. Są $2^{n}$ takie sposoby, jest to rozmiar zbioru potęgowego n obiektów. Można wykorzystać ten fakt do zmierzenia podobieństwa między dwoma obiektami: i można by zobaczyć, ile zbiorów mają one wspólnych. Jednak nie można. Dowolne dwa obiekty mają dokładnie taką samą liczbę wspólnych klas, jeśli możemy utworzyć dowolną możliwą klasę, a mianowicie $2^{n-1}$ (połowa wszystkich klas). Aby to zobaczyć, można sobie wyobrazić, że każda klasa jest reprezentowana przez ciąg n-bitowy (liczbę całkowitą zakodowaną binarnie), z zerem dla każdego elementu spoza klasy i jednym dla każdego elementu w klasie. Jak się okazuje, jest $2^{n}$ takich ciągów.

Ponieważ istnieją wszystkie możliwe wybory zer i jedynek, dowolne dwie pozycje bitowe będą zgodne dokładnie w połowie przypadków. Można wybrać dwa elementy i zmienić kolejność bitów, tak aby były pierwszymi dwoma, i wyobrazić sobie liczby posortowane leksykograficznie. Pierwsze $2^{n}/2$ liczby będą miały bit # 1 ustawiony na zero, a drugie $2^{n}/2$ ustawiony na jeden. W każdym z tych bloków szczyt $2^{n}/4$ będzie miał bit # 2 ustawiony na zero i drugi $2^{n}/4$ będą mieć to jako jeden, więc zgadzają się na dwa bloki $2^{n}/4$ lub w połowie wszystkich przypadków. Nieważne, które dwa elementy się wybierze. Więc jeśli nie mamy z góry założonego uprzedzenia co do tego, które kategorie są lepsze, wszystko jest jednakowo podobne (lub równie niepodobne). Liczba predykatów spełnianych jednocześnie przez dwa nieidentyczne elementy jest stała we wszystkich takich parach i jest taka sama  jako liczba zadowolonych z jednego. Konieczny jest zatem jakiś rodzaj indukcji do wydawania osądów potrzebne jest uprzedzenie; tj. preferencje wyboru pewnych kategorii, a nie innych.

Funkcje boolowskie

Niech $x_{1},x_{2},\dots ,x_{n}$ będzie zbiorem wektorów o $k$ wartościach logicznych każdy. Brzydkie kaczątko jest wektorem najmniej podobnym do innych. Biorąc pod uwagę wartości logiczne, można to obliczyć za pomocą odległości Hamminga.

Jednak wybór funkcji logicznych do rozważenia może być nieco arbitralny. Być może były cechy wyprowadzone z oryginalnych cech, które są ważne dla identyfikacji brzydkiego kaczątka. Zbiór wartości logicznych w wektorze można rozszerzyć o nowe funkcje obliczane jako funkcje logiczne klasy $k$ oryginalne funkcje. Jedynym kanonicznym sposobem na to jest rozszerzenie go o wszystkie możliwe funkcje boolowskie. Wynikowe kompletne wektory mają $2^{k}$ funkcje. Twierdzenie o brzydkim kaczątku stwierdza, że nie ma brzydkiego kaczątka, ponieważ dowolne dwa kompletne wektory będą albo równe, albo różnią się dokładnie o połowę cech.

Dowód. Niech x i y będą dwoma wektorami. Jeśli są takie same, to ich kompletne wektory również muszą być takie same, ponieważ każda funkcja boolowska x będzie zgodna z tą samą funkcją logiczną y. Jeśli x i y są różne, to istnieje współrzędna $i$ gdzie $i$ -ta współrzędna $x$ różni się od $i$ -ta współrzędna $y$ . Teraz ukończone funkcje zawierają wszystkie funkcje logiczne $k$ Zmienne logiczne, z których każda dokładnie raz. Wyświetlanie tych funkcji boolowskich jako wielomianów w programie $k$ zmienne nad GF (2), podziel funkcje na pary $(f,g)$ gdzie $f$ zawiera $i$ -ta współrzędna jako wyraz liniowy i $g$ jest $f$ bez tego liniowego terminu. Teraz dla każdej takiej pary $(f,g)$, $x$ i $y$ uzgodni dokładnie jedną z dwóch funkcji. Jeśli zgadzają się co do jednego, muszą nie zgadzać się co do drugiego i odwrotnie. (Uważa się, że ten dowód pochodzi od Watanabe).

Dyskusja

Stamos (2003) podjął próbę rozwiązania twierdzenia o brzydkim kaczątku, pokazując, że niektóre sądy dotyczące ogólnego podobieństwa są niearbitralne w tym sensie, że są przydatne: dfgds

O ile niektóre właściwości nie zostaną uznane za bardziej istotne lub „ważone” za ważniejsze niż inne, wszystko będzie wyglądało tak samo podobnie, stąd Watanabe (1986) napisał: „wszelkie przedmioty, o ile są rozróżnialne, są jednakowo podobne”

W słabszej sytuacji, która przyjmuje nieskończenie wiele właściwości, Murphy i Medin (1985) podają przykład dwóch domniemanych sklasyfikowanych rzeczy, śliwek i kosiarek:

Zobacz też

• Brak darmowego lunchu w wyszukiwaniu i optymalizacji
• Brak twierdzenia o darmowym lunchu
• Tożsamość rzeczy nieodróżnialnych - klasyfikacja (dostrzegalność) jest możliwa (z uprzedzeniem lub bez), ale nie mogą istnieć oddzielne obiekty lub byty, które mają wszystkie wspólne właściwości. sdfgsdf

Uwagi

sdfg

[[Kategoria:Ontologia]]