Pytania otagowane jako lg.learning

Uczenie maszynowe i teoria uczenia się: uczenie się PAC, algorytmiczna teoria uczenia się i obliczeniowe aspekty wnioskowania bayesowskiego i modele graficzne.

4
Czy znalezienie minimalnego wyrażenia regularnego jest problemem NP-zupełnym?
Mam na myśli następujący problem: Chcę znaleźć wyrażenie regularne, które pasuje do określonego zestawu ciągów (np. Prawidłowe adresy e-mail) i nie pasuje do innych (nieprawidłowe adresy e-mail). Załóżmy, że przez wyrażenie regularne rozumiemy dobrze zdefiniowaną maszynę skończoną, nie znam dokładnej terminologii, ale uzgodnijmy pewną klasę dozwolonych wyrażeń. Zamiast ręcznie tworzyć …
1
Funkcje, które nie są wydajnie obliczalne, ale można się ich nauczyć
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można się go nauczyć z wielomianową złożonością próbki …
2
Jaka jest złożoność odróżnienia prawdziwego widma Fouriera od fałszywego?
PHPHPH urządzenie ma dostęp oracle losowej logicznej funkcji f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} , a dwa Fouriera widma ggg i hhh . Widma Fouriera funkcji fff są zdefiniowane jako F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R : F(s)=∑x∈{0,1}n(−1)(s⋅xmod 2)f(x)F(s)=∑x∈{0,1}n(−1)(s⋅xmod 2)f(x)F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x) Jedno z ggg lub hhh to prawdziwe …
2
Przybliżenie rangi znaku macierzy
Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.AijBij>0AijBij>0A_{ij}B_{ij}>0i,ji,ji,j Moje pytanie brzmi: czy są jakieś znane algorytmy …
3
Testowanie właściwości w innych metrykach?
Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest -far z każdej funkcji w klasie .εε\varepsilonCC\mathcal{C} Zakres funkcji jest czasem wartością logiczną: , ale nie …
1
Problem Warrena Buffetta
Oto streszczenie problemu nauki online / bandyty, nad którym pracowałem latem. Nie widziałem wcześniej takiego problemu i wygląda całkiem interesująco. Jeśli znasz jakieś powiązane prace, byłbym wdzięczny za referencje. Problem Ustawienie dotyczy wielorękich bandytów. Masz N. broni. Każde ramię ma nieznany, ale stały rozkład prawdopodobieństwa nad nagrodami, które można zdobyć, …
2
Żal wewnętrzny w Online Convex Optimization
„Optymalizacja wypukła” Zinkevicha ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) uogólnia algorytmy uczenia się „minimalizacji żalu” od ustawień liniowych do wypukłych i daje dobre „zewnętrzne pożałowanie” . Czy istnieje podobne uogólnienie wewnętrznego żalu? (Nie jestem do końca pewien, co to właściwie znaczy.)
2
O statusie zdolności uczenia się w
Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w T C 0 , ponieważ nie jestem ekspertem w tej dziedzinie.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 Do tej pory odkryłem: Wszystkie można wyciągnąć w quasipolynomial czasie w jednorodnym rozkładzie …
4
Najgorsza liczba pytań potrzebna do nauczenia się monotonicznego orzeczenia nad zestawem
Rozważmy skończoną posetę ponad elementów, a nieznany monotoniczny predykat nad (tj. Dla dowolnego , , jeśli i to ) . Mogę ocenić , podając jeden węzeł i sprawdzając, czy utrzymuje, czy nie. Moim celem jest określenie dokładnie zestawu węzłów tak, że P (x) utrzymuje, przy użyciu jak najmniejszej liczby ocen …
3
Kombinatoryczna charakterystyka nauki ścisłej z zapytaniami członkowskimi
Edycja: Ponieważ od tygodnia nie otrzymałem żadnych odpowiedzi / komentarzy, chciałbym dodać, że cieszę się, że słyszę cokolwiek o problemie. Nie pracuję w okolicy, więc nawet jeśli jest to prosta obserwacja, mogę tego nie wiedzieć. Pomocny byłby nawet komentarz typu „Pracuję w okolicy, ale nie widziałem takiej charakterystyki”! Tło: Istnieje …
1
Najlepsza złożoność zapytań algorytmu uczenia się Goldreich-Levin / Kushilevitz-Mansour
Jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Goldreich-Levin? Notatki z bloga Luca Trevisan , Lemma 3, stwierdza się jako . Czy jest to najlepiej znane pod względem zależności od n ? Będę szczególnie wdzięczny za odniesienie do źródła cytowanego!O ( 1 / ϵ4n logn )O(1/ϵ4nlog⁡n)O(1/\epsilon^4 n \log n)nnn …
2
Nauka trójkątów w płaszczyźnie
I przypisany Moi studenci problem znalezienia trójkąt spójne z kolekcją punktów w R 2 , oznaczonego ± 1 . (Trójkąt T jest zgodny z próbką oznaczoną, jeśli T zawiera wszystkie punkty dodatnie i żaden z punktów ujemnych; z założenia próbka przyjmuje co najmniej 1 spójny trójkąt).mmmR2R2\mathbb{R}^2±1±1\pm1TTTTTT Najlepsze, co mogliby zrobić …
3
Algorytmy modelu statystycznego zapytania?
Zadałem to pytanie w sprawdzonych krzyżowo pytaniach i odpowiedziach, ale wydaje się, że jest ono bardziej związane z CS niż ze statystykami. Czy możesz podać mi przykłady algorytmów uczenia maszynowego, które uczą się na podstawie właściwości statystycznych zestawu danych, a nie samych indywidualnych obserwacji, tj. Wykorzystują statystyczny model zapytań ?
1
Żądanie referencji: minimalizacja submodularna i monotoniczne funkcje boolowskie
Tło: W uczeniu maszynowym często pracujemy z modelami graficznymi reprezentującymi funkcje gęstości prawdopodobieństwa o wysokim wymiarze. Jeśli odrzucimy ograniczenie, które gęstość całkuje (sumuje) do 1, otrzymujemy nienormalizowaną funkcję energii o strukturze grafowej . Załóżmy, że mamy taką funkcję energetyczną zdefiniowaną na wykresie . Na każdy wierzchołek wykresu przypada jedna zmienna …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.