Problem med att samla data från parvis likhet information är allmänt förekommande i datavetenskap. Teoretiska behandlingar visar typiskt likhetsinformationen som mark-sanning och sedan designa algoritmer för att (ungefär) optimera olika graf-baserade objektiva funktioner. Men i de flesta tillämpningar är denna likhetsinformation endast baserad på någon heuristisk; sanningen i grunden är egentligen den okända korrekta sammanslagningen av datapunkterna och det verkliga målet är att uppnå ett lågt fel på datan. I detta arbete utvecklar vi ett teoretiskt förhållningssätt till kluster från detta perspektiv. I synnerhet motiveras av det senaste arbetet i inlärningsteori som frågar "vilka naturliga egenskaper hos en likhets (eller kärna) funktion räcker för att kunna lära sig väl?" vi frågar "vilka naturliga egenskaper hos en likhetsfunktion är tillräckliga för att kunna klunga väl?" För att studera denna fråga utvecklar vi en teoretisk ram som kan ses som en analog av PAC inlärningsmodell för kluster, där objektet för studien, snarare än att vara en koncept klass, är en klass av (begrepp, likhet funktion) par, eller motsvarande, en egenskap likhetsfunktionen bör tillfredsställa med avseende på marken sanningen kluster. Vi analyserar sedan både algoritmiska och informationsteoretiska frågor i vår modell. Även om ganska starka egenskaper behövs om målet är att producera en enda ungefär korrekt klusterbildning, finner vi att ett antal rimliga egenskaper är tillräckliga under två naturliga avkopplingar: a) lista kluster: analogt med begreppet list-avkodning, algoritmen kan producera en liten lista av kluster (som en användare kan välja mellan) och b) hierarkisk kluster: algoritmens mål är att producera en hierarki så att önskad klusterbildning är någon beskärning av detta träd (som en användare kan navigera). Vi utvecklar en uppfattning om hur komplex en viss egenskap är (analogt med begreppen kapacitet i inlärningsteorin), som kännetecknar dess informationsteoretiska användbarhet för klusterbildning. Vi analyserar denna kvantitet för flera naturliga spel-teoretiska och lärande-teoretiska egenskaper, samt design * Stöds delvis av National Science Foundation under bidrag CCF-0514922, och av ett Google Research Grant. † Stöds delvis av den nationella vetenskapsstiftelsen genom bidrag CCF-0721503, och av en Raytheon-stipendiat. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift.
Begreppet lista decodable learning infördes av Balcan et al. REF för klusterproblem.
A discriminative framework for clustering via similarity functions
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}