{"id":"W1990948892","doi":"10.1016/j.jcss.2007.04.011","title":"The complexity of properly learning simple concept classes","year":2007,"lang":"en","type":"article","venue":"Journal of Computer and System Sciences","topic":"Machine Learning and Algorithms","field":"Computer Science","cited_by":45,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Toronto","funders":"","keywords":"Mathematics; Combinatorics; Hypergraph; Intersection (aeronautics); Simple (philosophy); Constant (computer programming); DTIME; Time complexity; Upper and lower bounds; Discrete mathematics; Running time; Graph; Turing machine; Computer science; Algorithm","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.003961141,0.00009077917,0.0002451553,0.00009998227,0.000588121,0.0003392402,0.0009070801,0.00002462793,9.926999e-7],"category_scores_gemma":[0.00003627391,0.00004709903,0.00007431176,0.0003120632,0.0006122293,0.00034489,0.0001466173,0.0002156567,9.020799e-7],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00001432309,"about_ca_system_score_gemma":0.00009078826,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00002648083,"about_ca_topic_score_gemma":0.000002909097,"domain_scores_codex":[0.9983314,0.0002180792,0.0005401747,0.000144796,0.00054137,0.0002241922],"domain_scores_gemma":[0.9985339,0.0004387634,0.0005823701,0.0001185261,0.0002330456,0.00009341569],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.00003357925,0.0000890095,0.03058156,0.0001541613,0.000089241,0.00008585884,0.006820813,0.0129594,0.0002810592,0.326444,0.001575191,0.6208861],"study_design_scores_gemma":[0.0007565341,0.002790557,0.04661013,0.0003378686,0.00001507325,0.001582757,0.003109512,0.9243274,0.0005844685,0.00253802,0.0170598,0.0002878958],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1207088,0.001049135,0.8750828,0.0005438912,0.001017443,0.00006453434,2.372305e-7,0.00002818044,0.001505037],"genre_scores_gemma":[0.972503,0.00001096189,0.02710779,0.00002817735,0.000312338,1.517859e-7,4.55396e-8,0.000002089677,0.00003541271],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.911368,"threshold_uncertainty_score":0.452341,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03143958742733738,"score_gpt":0.2867763757400699,"score_spread":0.2553367883127325,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}